Методы оптимизации

«скалярную» меру качества – целевую функцию
Определяют набор независимых переменных и

формулируют условия,
которые характеризуют их приемлемые значения (размерность задачи и ее
ограничения).
Решение оптимизационной задачи – это приемлемый набор значений
переменных, которому отвечает оптимальное значение целевой функции.

Под оптимальностью обычно понимают минимальность целевой функции.

нулевого порядка. Формулируются они
следующим образом:
Пусть дан вектор начального приближения

, очередное
приближение рассчитывается по формуле

где - подходящим образом выбранное направление и - шаг –
положительное число, определяющее величину смещения вдоль
направления .
Направление называется направлением спуска, если

являются векторами спуска. Поскольку
рассматриваются дифференцируемые

функции, то для них всегда
существует достаточно малое , такое, что

Используя возможность разложения целевой функции в ряд Тейлора, и ее
непрерывность, можно записать:

где
Как следствие, при достаточно малых из последнего равенства
следует предыдущее неравенство для всех направлений спуска.

December 1642 – 20 March 1727 [NS: 4 January 1643 –

31 March 1727]) was an English physicist, mathematician,  astronomer,  natural philosopher,  alchemist, and theologian, has been "considered by many to be the greatest and most influential scientist who ever lived."

http://en.wikipedia.org/wiki/Isaac_Newton

экзамен на знание латинского языка, после чего сообщили, что он

принят в Тринити-колледж  (Колледж святой Троицы) Кембриджского университета. С этим учебным заведением связаны более 30 лет жизни Ньютона.
Ньютона зачислили в разряд студентов-«сайзеров» (англ. sizar), с которых не брали платы за обучение. Документальных свидетельств и воспоминаний об этом периоде его жизни сохранилось очень мало. В эти годы окончательно сложился характер Ньютона — научная дотошность, стремление дойти до сути, нетерпимость к обману, клевете и угнетению, равнодушие к публичной славе. У него по-прежнему не было друзей.
В апреле 1664 года Ньютон, сдав экзамены, перешёл в более высокую студенческую категорию «школяров» (scholars), что дало ему право на стипендию и продолжение обучения в колледже.

пережил творческий подъём, начал самостоятельную научную деятельность и составил масштабный

список (из 45 пунктов) нерешённых проблем в природе и человеческой жизни (Вопросник, лат. Questiones quaedam philosophicae).
В дальнейшем подобные списки не раз появляются в его рабочих тетрадях. В марте этого же года на недавно основанной (1663) кафедре математики колледжа начались лекции нового преподавателя, 34-летнего Исаака Барроу, крупного математика, будущего друга и учителя Ньютона. Интерес Ньютона к математике резко возрос. Он сделал первое значительное математическое открытие: биномиальное разложение для произвольного рационального показателя (включая отрицательные), а через неё пришел к своему главному математическому методу — разложению функции в бесконечный ряд. Наконец, в самом конце года Ньютон стал бакалавром.

минимизации:
Метод Ньютона, в котором направление спуска определяется по формуле


с положительно

определенной матрицей , что обеспечивает значительную область сходимости;
Приближенный метод Ньютона, в котором


где - подходящая аппроксимация матрицы ;

спуска по формуле

. Таким образом,
этот метод является приближенным методом Ньютона, в котором .
Он может рассматриваться и как градиентный метод, поскольку


Метод сопряженных градиентов, для которого


где - скалярная величина, подбираемая таким образом, чтобы
обеспечить взаимную ортогональность направлений

задания метода спуска. Ведь остается еще проблема определения

так, чтобы шаг метода был не очень мал, что замедлит скорость сходимости, но в то же время сохранял бы условие сходимости:

Обычно метод выбора параметра заключается в решении одномерной задачи минимизации:
Найти значение , минимизирующее функцию


Теорема. Если параметр является решением задачи одномерной минимизации на каждом шаге, то метод спуска обеспечивает сохранение условия ортогональности

на каждом шаге метода.

Методы спуска

невозможно, поскольку задача нелинейна. Одна
из возможных стратегий заключается в

аппроксимации функции вдоль
прямой полиномом и минимизации этого полинома по
переменной .

Квадратичная интерполяция (вдоль направления спуска) – метод Пауэлла.
Кубическая интерполяция – метод Давидона.

В общем случае процесс решения задачи одномерной минимизации для
определения шага метода носит название линейного поиска.

Методы спуска

(красн.) в случае дробного шага. Синим отмечены линии уровня.
Градиентный спуск — метод нахождения локального минимума (максимума) функции с

помощью движения вдоль градиента. Для минимизации функции в направлении градиента используются методы одномерной оптимизации, например, метод золотого сечения. Также можно искать не наилучшую точку в направлении градиента, а какую-либо лучше текущей.
Сходимость метода градиентного спуска зависит от отношения максимального и минимального собственных чисел матрицы Гессе в окрестности минимума (максимума). Чем больше это отношение, тем хуже сходимость метода.

Градиентный спуск

numpoints=3000);cont:=%:
> start:=[-1/4,1/3];ptf[0]:=Vector(start):
> steps:=15;
> for i from 0

to steps do: print(ptf[i]): pt[i]:=Vector([convert(ptf[i],list)[],z(ptf[i][1],ptf[i][2])]): dir[i]:=evalf(Normalize(evalVF(grad,ptf[i])));
par[i]:=ptf[i]+lambda*dir[i]; lambd[i]:=fsolve(diff(z(par[i][1],par[i][2]),lambda)=0,lambda=0); ptf[i+1]:=eval(par[i],lambda=lambd[i]); od:i:='i':
> display(cont,'point(convert(ptf[i],list),color=blue)'$'i'=0..steps,'plot([par[i][1], par[i][2],lambda=0..lambd[i]])'$'i'=0..steps);
> display(p3d,'point(convert(pt[i],list),color=blue,symbol=circle,symbolsize=4)'$'i'=0..steps, 'spacecurve([par[i][1],par[i][2],z(par[i][1],par[i][2])],lambda=0

Линейный поиск

used as a performance test problem for optimization algorithms introduced

by Rosenbrock (1960). It is also known as Rosenbrock's valley or Rosenbrock's banana function.
The global minimum is inside a long, narrow, parabolic shaped flat valley. To find the valley is trivial. To converge to the global minimum, however, is difficult.
It is defined by

It has a global minimum at (x,y) = (1,1) where f(x,y) = 0. A different coefficient of the second term is sometimes given, but this does not affect the position of the global minimum.
http://demonstrations.wolfram.com/MinimizingTheRosenbrockFunction/

Функция Розенброка

Метод градиентного спуска оказывается очень медленным при движении вдоль оврага. Примером такой функции является функции Розенброка. 

the minimum. The bottom of the valley is very flat.

Because of the curved flat valley the optimization is zig-zagging slowly with small stepsizes towards the minimum.

Функция Розенброка

function, used to test the performance of optimization algorithms. The

function is defined by:

The locations of all the minima can be found analytically, but the expressions are long and complicated.

http://en.wikipedia.org/wiki/Himmelblau%27s_function

It has one local maximum at and where

and four identical local minimums:

Функция Химмельблау