Основы теории оптимизации (стр. 37 )

где λ1 и λп — наименьшее и наибольшее собственные значения А. Поэтому

Поскольку

Ми­нимизируя q по γ получаем (15).

Покажем, что оценка скорости сходимости, даваемая теоре­мой 3, точная, она достигается для любой квадратичной функцией. Пусть

где λі — сооственные числа матрицы А. Возьмем произвольное Предположим, что Выберем х0=х*+е1, где е1 — собственный вектор, от­вечающий

Анало­гичным образом, если то выберем

— собственный вектор, отвечающий и получим так же

Таким образом, для всякого 0<γ 2/L найдется х0 такое, что

Оценку

нельзя улучшить, даже если выбирать γ оптимальным образом для каждого х0. Действительно, возьмем х0=х*+е1+еп (обозна­чения те же, что и выше). Тогда пои любом

Поэтому, если либо либото

||xk — х*|| убывает медленнее, чем (q*)k. Но q=max {|1-γl|, |1-γL|}≤q* лишь при γ = γ*, при этом

Аналогичное расуждение справедливо для любой точки х0 такой, что

Локальный аналог теоремы 3 справедлив и для невыпуклых функций.

Теорема 4. Пусть х* — невырожденная точка локального минимума f(x). Тогда при метод (5) локально сходится к х* со скоростью геометрической прогрессии, т. е. для всякого δ > 0 найдется ε > 0 такое, что при будет

(16)

Величина q минимальна и равна при

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

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

f(x[k] –akf’(x[k])) = f(x[k] – af'(x[k])).

Это условие означает, что движение вдоль антиградиента происходит до тех пор, пока значение функции f(x) убывает. С математической точки зрения на каждой итерации необходимо решать задачу одномерной минимизации по а функции
j(a) = f(x[k] - af′(x[k])) .

Алгоритм метода наискорейшего спуска состоит в следующем.

1. Задаются координаты начальной точки х[0].

2. В точке х[k], k = 0, 1, 2, ... вычисляется значение градиента f′ (x[k]).

3. Определяется величина шага ak, путем одномерной минимизации по а функции j(a) = f(x[k] - af′(x[k])).

4. Определяются координаты точки х[k+1]:

хi[k+1] = xi[k] – аkf′i(х[k]), i = 1 ,..., п.

5. Проверяются условия останова итерационного процесса. Если они выполняются, то вычисления прекращаются. В противном случае осуществляется переход к п. 1.

В рассматриваемом методе направление движения из точки х[k] касается линии уровня в точке x[k+1] (рис. 1). Траектория спуска зигзагообразная, причем соседние звенья зигзага ортогональны друг другу. Действительно, шаг ak выбирается путем минимизации по а функции f(a) = f(x[k] - af'(x[k])). Необходимое условие минимума функции dj(a)/da=0. Вычислив производную сложной функции, получим условие ортогональности векторов направлений спуска в соседних точках:

dj(a)/da = - f′(x[k+1]f′(x[k]) = 0.

Рис. 1. Геометрическая интерпретация метода наискорейшего спуска

Градиентные методы сходятся к минимуму с высокой скоростью (со скоростью геометрической прогрессии) для гладких выпуклых функций. У таких функций наибольшее М и наименьшее m собственные значения матрицы вторых производных (матрицы Гессе)

мало отличаются друг от друга, т. е. матрица Н(х) хорошо обусловлена. Напомним, что собственными значениями li, i =1, …, n, матрицы являются корни характеристического уравнения

Однако на практике, как правило, минимизируемые функции имеют плохо обусловленные матрицы вторых производных (т/М<<1). Значения таких функций вдоль некоторых направлений изменяются гораздо быстрее (иногда на несколько порядков), чем в других направлениях. Их поверхности уровня в простейшем случае сильно вытягиваются (рис. 2), а в более сложных случаях изгибаются и представляют собой овраги. Функции, обладающие такими свойствами, называют овражными. Направление антиградиента этих функций (см. рис. 2) существенно отклоняется от направления в точку минимума, что приводит к замедлению скорости сходимости.

Рис. 2. Овражная функция

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

4.5. Метод градиентного спуска

if (window. showTocToggle) { var tocShowText = "показать"; var tocHideText = "убрать"; showTocToggle(); } Введение

В разделе рассматривается задача поиска минимума функции , записываемая в виде:

(1)

Пусть функция f(x) такова, что можно вычислить ее градиент. Тогда можно применить метод градиентного спуска, описанный ниже.

В разделе приведены теоремы сходимости метода градиентного спуска, а также рассмотрена его варианты:

Градиентный метод с постоянным шагом.

Идея метода

Основная идея метода заключается в том, чтобы осуществлять оптимизацию в направлении наискорейшего спуска, а это направление задаётся антиградиентом -f:

где λ[k] выбирается

·  постоянной, в этом случае метод может расходиться;

·  дробным шагом, т. е. длина шага в процессе спуска делится на некое число;

·  наискорейшим спуском:

Алгоритм

Вход: функция

Выход: найденная точка оптимума x

Повторять: , где λ[k] выбирается одним из описанных выше способов если выполен критерий останова, то возвращаем текущее значение x[k+1]

Критерий останова

Критерии остановки процесса приближенного нахождения минимума могут быть основаны на различных соображениях. Некоторые из них: