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

В этом методе в качестве поискового направления выбирается направление антиградиента в текущей поисковой точке X _k, т.е.

P _k = - g (X _k). (1.5.1)

Антиградиент указывает направление наибольшего уменьшения целевой функции при движении из точки X _k.

Рис.1.5.1

Поиск минимума методом наискорейшего спуска

Алгоритм этого метода следующий.

{{{ Начало алгоритма.

1) Полагаем k=1, X _k= X _init и рассчитываем значение целевой функции J(X _k).

2) Рассчитываем градиент g (X _k) и поисковое направление P _k по формуле (1.5.1).

3) Определяем минимум в направлении P _k: a_k: min_a(J(X _k+a_k× P _k). Рассчитываем новое приближение вектора поисковых параметров X _k+1= X _k+a_k× P _k.

4) Если |a_k× P _k|>e, то увеличиваем k на единицу - k=k+1 и идем опять к пункту 2), иначе поиск закончен.

}}} Конец алгоритма.

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

Метод Вольфа

Метод Вольфа [35] основывается на построении начального n+1 - мерного симплекса, расчета в вершинах симплекса значений целевой функции и градиента и вычисления новой вершины симплекса по квадратичной аппроксимации целевой функции. Алгоритм метода Вольфа следующий.

{{{ Начало алгоритма.

1) Относительно начальной точки X _init случайным образом определяются n+1 вершины симплекса в гиперкубе с ребром D X _init. В вершинах этого симплекса вычисляются значения целевой функции и градиента: J(X _k), P_xJ(X _k), k=1..n+1.

2) Решается относительно параметров l_k следующая система линейных алгебраических уравнений n+1 порядка:

(1.5.2)

Определяется новая вершина симплекса

(1.5.3)

Среди всех старых вершин симплекса находится такая с номером j в которой значение целевой функции максимально, т.е.

J(X _j)>J(X _k), k=1..n+1. (1.5.4)

Если J(X _new)>J(X _j), то полагаем и переходим к пункту 1), иначе заменяем j-ю вершину на новую X _j= X _new и переходим к следующему пункту.

3) Если , то переходим к пункту 2), иначе поиск заканчивается.

}}} Конец алгоритма.

Для доказательства правомерности формулы (1.5.3), представим квадратичную целевую функцию в виде следующего ряда Тейлора относительно точки X_new, в которой мы предполагаем находится минимум целевой функции:

J(X _k)=J(X _new)+(X _k- X _new)^TG(X _k- X _new)/2. (1.5.5)

Градиент в точке X _k определяется как

P_xJ(X _k)=G×(X _k- X _new). (1.5.6)

Подставив (1.5.6) в (1.5.2) получим:

Считая, что G ненулевая матрица и учитывая соотношение (1.5.2), получаем искомую формулу (1.5.3), которая указывает на точку минимума квадратичной целевой функции.

Метод Вольфа хорошо сходится, как и метод Ньютона, на функциях близких к квадратичным, на не квадратичных функциях метод Вольфа неустойчив. Его можно, как и метод Ньютона, модифицировать, введя процедуру поиска минимума вдоль направления P = X _new- X _j в пункт 2) алгоритма метода Вольфа. Можно ожидать, что такое дополнение улучшит устойчивость метода Вольфа, как это наблюдается в методе Ньютона-Рафсона.

Дата добавления: 2015-11-14