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

причём, в силу условий теоремы 1, q < 1.

Итак, за один цикл спуск | fx | уменьшился в q раз. Аналогично, со сдвигом на 1/2 цикла, | fу | уменьшится в q раз. Выполнив п циклов координатного спуска получим, что

Далее, в окрестности точки экстремума х* компоненты градиента можно разложить по формуле Тейлора

Пренебрегая в разложении слагаемыми высших порядков, получаем линейную систему относительно приращений координат ∆х и ∆у. По условию теоремы 1 гессиан G(M*) > 0, тем самым полученная система совместна и можно выразить ∆х и ∆у через линейную комбинацию компонент градиента в точке М = М(п). При этом ∆х, ∆у → 0 на траектории {Мk}, Мk →М*.

Итак:

• Вблизи точки экстремума М* сходимость координатою спуска и по координатам, и по градиенту линейная (достаточно медленная, что с практической точки зрения плохо).

• По "циклам"' спусков можно делать ускорения по методу Эйткена;

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

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

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

В общем случае для траектории спуска {Мk}: fk+l<fk при минимизации достаточно гладких функций можно сформулировать достаточные условия сходимости соответствующего метода спуска, характеризующие изменение функции f и eе градиента =grad f на траектории { Мk }

Пусть очередной шаг совершается вдоль направления и приводит нас в точку Мk+1:

= + hk.

Illaг hk выбирается из условия минимальности f (М) вдоль

Сформулируем достаточные условия сходимости метода спуска Теорема 2. Пусть

1) f ( ) дважды дифференцируемая функция;

2) множество уровня

D(f ( )) = { : f( )≤ f ( )}

ограничено и замкнуто;

3) на каждой итерации

а) направление - «существенное направление спуска»

β< 0, ≤ β < 0

б) f (х) «существенно убывает», (т. е. выбрано соответствующее ограни­чение на шаг)

Тогда

||||=0; (Mk→M*)

т. е. метод спуска обладает сходимостью (как правило — линейной).

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

Метод "наискорейшего" спуска. Рассмотрим линейную аппроксимацию целе­вой функции ) f ( ) в окрестности точки . Опираясь на формулу Тейлора:

с определенной точки зрения (локально!) естественно искать направление, по кото­рому = • наибольшее по модулю отрицательное число. Это направление в первом порядке по || || обеспечивает наибольшее убывание функции f.

Итак, необходимо найти направление

Решение полученной задачи зависит от вида рассматриваемой нормы. Если выбрать С-энергетичеекую норму || ||2 = (С , ), где С > 0 и симметрична, тогда напра­вление (с точностью до нормировочной Const)

= -С-1 • .

Для евклидовой нормы - С = Е и р = — , что приводит нас к методу наискорей­шего спуска.

(1)

Замечания:

1) При таком выборе и hk (1) траектория спуска перпендикулярна линии уровня f (хk) в точке хk.

2) Но сходимости наискорейший спускав лучше, чем координатный спуск, т. е. он обладает лишь линейной сходимостью.

3) Анализ сходимости наискорейшего спуска на квдратичной функции с симме­тричной и положительно определенной матрицей (что характерно для гессиана в окрестности невырожденного минимума)

дает лишь линейную сходимость. Поскольку А>0, АТ = А следовательно все собственные значения матрицы А положительны і λі(А)>0. Сходимосгь метода наискорейшего спуска характеризуют величиной

(2)

Полученная оценка скорости сходимости, например для = 100 (хорошая обу­словленность матрицы А) даёт q ~ 0, 96(!) и нужны сотни итераций для умень­шения погрешности на порядок.

Расчетные формулы наискорейшего спуска (1) в этом случае принимают вид:

(3)

Тем не менее:

1) Необходимо бесконечное число итераций для нахождения экстремума даже в случае квадратичной функции.

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

3) Метод наискорейшею спуска невозможно адаптировать для использования ин­формации о вторых производных f ( ).

Чтобы лучше понять идею градиентных методов, более конкретно остановимся на свойствах градиентов. Рассмотрим систему независимых единичных векторов е1, е2, е3, …, еN, которые направленны вдоль осей координат x1, x2, x3, …, xN, которые есть в то же время проектными параметрами. Вектор градиента произвольной целевой функции F = (x1, x2, x3, …, xN,) имеет вид

,

где частные производные вычисляются в рассматриваемой точке. Этот вектор направлен вверх, в направлении подъема; обратный ему вектор указывает направление спуска. Единичный вектор градиента часто представляют в виде

,

  где 

  .  (4)

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

.

Здесь ∆ - небольшое смещение в направлении хi. Эту формулу часто называют “приближением секущей”. Полученную информацию о направлении градиента можно использовать различным образом для построения алгоритма поиска.

Постановка задачи оптимизации градиентными методами: минимизация функции F (x1, x2, x3, …, xN) с N проектными параметрами с помощью ЭВМ решается итерационными методами. Решение задачи начинается с выбора начальных значений хi[0] (i = 1, 2, …, N), которые как обычно определяются из условий решаемой задачи, и потом строят последовательные приближения, используя итерационную формулу :

  , (i = 1, 2, …, N; j = 0, 1, 2, …),  (5)