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

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

Например, для функции f (x1 , x2 )

∂f (xk ) = f (x1k + δ1 , x2k ) − f (x1k , x2k ) ,

∂x1 δ1

∂f (x k ) = f (x1k , x2k + δ2 ) − f (x1k , x2k ) .

∂x2 δ2

Сходимость градиентных методов. Тот факт, что градиентные методы при определенных условиях сходятся, отражается в теореме [2], которую приведем без доказательства.

Теорема. Если функция f (x) ограничена снизу, ее градиент

f (x) удовлетворяет условию Липшица

||f (x) − f ( y) ||≤ R || x − y ||

при любых x, y E n , а выбор шага λk производится указанными ранее способами, то для любой начальной точки x0 градиентный метод сходится, т.е. || f (xk ) || → 0 при k → ∞ .

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

|| xk +1 − x* ||≤ q || xk − x* ||, 0 < q <1

(такая скорость сходимости называется линейной).

Величина знаменателя прогрессии q зависит от соотношения наибольшего М и наименьшего m собственных значений матрицы вторых производных f (x) . Достаточно малым знаменатель q будет

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

с высокой скоростью. Чем меньше отношение Mm , тем ближе к

единице знаменатель q и тем медленнее сходятся градиентные методы.

56

Можно дать геометрическую интерпретацию этого факта

(рис. 1.23).

а

б

Рис. 1.23. Типы линий уровня:

а – линии уровня, близкие к окружности; б – линии уровня «овражного типа»

Когда отношение Mm близко к единице линии уровня функции

f (x) = const близки к окружности. Для таких линий уровня градиентный метод сходится быстро (рис. 1.23, а).

С уменьшением отношения Mm линии уровня становятся все

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

(рис. 1.23, б).

57

Особенно медленно градиентные методы сходятся, когда функция имеет «овражный» характер. Это означает, что небольшое изменение некоторых переменных приводит к резкому изменению значений функции – эта группа характеризует «склон оврага», а по остальным переменным, задающим направление «дна оврага», функция меняется незначительно. Если линии уровня у такой функции сильно вытянуты, то градиентные методы сходятся медленно.

Это происходит из-за того, что кривая поиска для таких функций обычно быстро спускается на «дно оврага», а затем начинает медленное перемещение к экстремуму, так как градиент оказывается почти перпендикулярным к оси оврага (рис. 1.24).

Рис. 1.24. Использование градиентного метода в случае функции «овражного» типа

Для ускорения сходимости при поиске минимума «овражной» функции существуют специальные методы – они называются «овражными».

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

Пример. Рассмотрим функцию f (x) = x12 + 25x22 .

Очевидно, что линии уровня данной функции вытянуты вдоль оси х1. Если ввести замену переменных: у1 = х1, у2 = 5х2, то функция

58

f ( y) = y12 + y22 будет иметь линии уровня в виде окружностей, и в

результате градиентный метод сходится за один шаг.

В реальной задаче подобрать нужные преобразования, как правило, оказывается достаточно сложно.

Блок-схема градиентного метода (2-й вариант) изображена на рис. 1.25.

Рис. 1.25. Блок-схема градиентного метода, где x0 – аргумент в начале итерации;

В данном методе окончание итерационного процесса осуществляется по условию – || f ′(xk ) ||≤ ε.

Задача. Найти методом наискорейшего спуска минимум

Решение. Очевидно, что нетрудно найти точное решение данной задачи:

Решим задачу с использованием градиентного метода. В результате получим следующую последовательность действий.

1-я итерация:

f (x0 ) ≈1,4 > ε.

Окончательно получаем для первой итерации:

60