Материал: Бородакий Нелинейное программирование в современных задачах оптимизации 2011

Рис. 1.20. Блок-схема алгоритма метода Пауэлла

51

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

Вслучае неквадратичной функции метод сопряженных направлений становится итеративным и обычно не заканчивается за n шагов. Неквадратичные функции локально аппроксимируют последовательность квадратичных функций. Направления определяются в соответствии с квадратичными аппроксимациями этих неквадратичных функций. Поэтому при функциях, локальные квадратичные аппроксимации которых быстро меняются от итерации к итерации или для которых матрица Гессе перестает быть положительно определенной, метод сопряженных направлений может не сходиться.

1.3.2.Методы первого порядка

1.3.2.1. Градиентные методы

Приемлемым направлением, т.е. направлением, в котором функция убывает, как было показано раньше, является направление S, для которого

f (x), S < 0 .

Поэтому направление S = − f (x) является приемлемым. Более

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

Градиентным называется метод, согласно которому точка xk+1 выбирается в соответствии с соотношением

xk +1 = x k − λk f ( x k ) .

Взависимости от способа выбора шага λk можно получить

различные варианты градиентного метода.

52

1-й вариант (метод наискорейшего спуска). Согласно этому методу λk определяется путем решения одномерной задачи

минимизации

min f ( xk − λk f ( x k )) .

λk

В отдельных случаях эта задача может быть решена точно, аналитически.

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

Двумерная иллюстрация метода представлена рис. 1.21. Действительно, точка xk+1 лежит на данном направлении в

точке его касания с линией уровня f (x) = f (xk +1 ) , поскольку она найдена из условия минимума на направлении − f (xk ) . Следующим направлением поиска будет − f (xk +1 ) . Известно, что

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

Рис. 1.21. Метод наискорейшего спуска

Аналитически это можно показать следующим образом. Обозначим

ϕ(λ) = f (xk − λ f (xk )) .

Поскольку шаг λ выбирается из условия минимума, то

Найдем ddϕλ по правилу дифференцирования сложной функции;

т.е. исходя из зависимости ϕ[x(λ)] значение производной определяется соотношением

= − < f (xk +1 ), f (xk ) >= 0 .

Следовательно, направления ортогональны.

Важно отметить, что эпитет «наискорейший» по отношению к спуску является исторически сложившимся, он не означает, что этот метод обладает способностью осуществлять отыскание минимальной точки за минимальное число шагов или при минимальном объеме вычислений. Существуют более эффективные в этом смысле методы.

2-й вариант градиентного метода. На практике нередко довольствуются выбором шага, обеспечивающего убывание функции в направлении антиградиента ( f (xk +1 ) < f (xk )) , вместо

того чтобы отыскивать минимум функции в данном направлении. Трудоемкость итерации при таком способе выбора шага меньше. При этом скорость сходимости обоих вариантов, в конечном счете, примерно одинакова.

Опишем способ выбора шага λk на k-й итерации.

1.Выбирается некоторое произвольное значение λ (одно и то же на всех итерациях) и определяется точка x = xk − λ f (xk ) .

2.Вычисляется f (x) = f (xk − λ f (xk )) .

3.Производится проверка неравенства

f (xk ) − f (x) ≥ ελ(< f (xk ), f (xk ) >) ,

|| f ( x )||2

54

где 0 < ε <1 – произвольно выбранная константа (одна и та же на всех итерациях).

Возможно использование более простого неравенства:

f(x) < f (xk ) .

4.Если неравенство выполняется, то значение λ и берется в качестве искомого: λk = λ . В противном случае производится

дробление λ (путем умножения λ на произвольное число α <1 ) до тех пор, пока неравенство не окажется справедливым.

Следует отметить, что если выбрать в качестве λ слишком маленький шаг, то процесс будет сходиться очень долго, поэтому время от времени можно пробовать увеличить λ , но так, чтобы не нарушить выбранное неравенство.

Направления поиска в этом варианте метода уже не будут ортогональны (рис. 1.22).

Рис. 1.22. Градиентный метод (второй вариант)

Можно предложить несколько критериев окончания итерационного процесса:

1)по разности аргументов на последовательных шагах

||x k +1−xk ||≤ ε1 ,

2)по разности значений функции

||f (x k +1) − f (xk ) ||≤ ε2 ,

3)по значению градиента

||f (xk ) ||≤ ε3 .

55