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

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

i:=0 k:=0 r:=-f'(x)// антиградиент целевой функции d := r // начальное направление спуска совпадает с антиградиентом Sigmanew:=rT*r// квадрат модуля антиградиента Sigma0:=Sigmanew // Цикл поиска (выход по счетчику или ошибке) while i<imax and Sigmanew>Eps2*Sigma0 begin  j:=0  Sigmad:=dT*d // Цикл одномерной минимизации (спуск по направлению d)  repeat  a : =  x : = x + a  j : = j + 1  until (j >= jmax) or (a2 * Sigmad <= Eps2)  r : = - f'(x) // антиградиент целевой функции в новой точке  Sigmaold : = Sigmanew  Sigmanew : = rT * r  beta : = Sigmanew / Sigmaold  d : = r + beta * d // Вычисление сопряженного направления  k : = k + 1  if (k = n) or (rT * d <= 0) then // Рестарт алгоритма  begin  d : = r  k : = 0  end  i : = i + 1 end

Метод сопряженных градиентов является методом первого порядка, в то же время скорость его сходимости квадратична. Этим он выгодно отличается от обычных градиентных методов. Например, метод наискорейшего спуска и метод координатного спуска для квадратичной функции сходятся лишь в пределе, в то время как метод сопряженных градиентов оптимизирует квадратичную функцию за конечное число итераций. При оптимизации функций общего вида, метод сопряженных направлений сходится в 4-5 раз быстрее метода наискорейшего спуска. При этом, в отличие от методов второго порядка, не требуется трудоемких вычислений вторых частных производных.

4.8. Методы оврагов

 Градиентные методы медленно сходятся в тех случаях, когда поверхности уровня целевой функции f(x) сильно вытянуты. Этот факт известен в литературе как «эффект оврагов». Суть эффекта в том, что небольшие изменения одних переменных приводят к резкому изменению значений функции – эта группа переменных характеризует «склон оврага», а по остальным переменным, задающим направление «дно оврага», функция меняется незначительно. На рис. 1 зображены линии уровня «овражной» функции. Траектория градиентного метода характеризуется довольно быстрым спуском на «дно оврага», и затем медленным зигзагообразным движением в точку минимума.

Рис. 1. Линии уровня овражной функции.

 Существуют различные подходы для определения точки минимума функции f(x) в овражной ситуации. Большинство из них основаны на эвристических (то есть интуитивных, не обоснованных строго) соображениях. Их можно применять, когда более совершенные методы нецелесообразны, например, когда значение целевой функции вычисляется со значительными погрешностями, информации о ее свойствах недостаточно и т. д. Эти методы просты в реализации и довольно часто применяются на практике, позволяя в ряде случаев получить удовлетворительное решение задачи.

Эвристический алгоритм

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

Первая эвристическая схема содержит два основных этапа. Оба этапа представляют собой аналоги градиентного спуска с постоянным шагом. Только вместо градиента  f′(xk) используется вектор g(x), формируемый из координат f′(xk) , но на каждом из этапов по разным правилам.

На первом этапе задается малое число d1<<1, и используется градиентный спуск, где вместо градиента f′(xk) берется вектор g(x)={g(1)(x),…,g(n)(x)}, который определяется следующим образом:

 

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

На втором этапе задается некоторое большое число d2>>1 и используется процедура спуска, где вместо градиента f′(xk) берется вектор g(x)={g(1)(x),…,g(n)(x)}, который определяется следующим образом:

В этом случае перемещение происходит по «берегу» оврага вдоль его «дна». Как и на первом этапе, спуск продолжается до тех пор, пока метод не зациклится.

После выполнения первого и второго этапов принимается решение о завершении работы или продолжении. Для этого сравнивается норма разности предыдущей точки, то есть точки, которую мы имели до применения первого и второго этапов, с текущей точкой, то есть полученной после применения с точностью решения задачи e1. Если эта норма меньше e1 и норма градиента в текущей точке меньше e3, то поиск заканчивается и последняя вычисленная точка принимается за приближенное решение задачи. Иначе для текущей точки вновь повторяем первый и второй этапы и т. д.

Алгоритм

Шаг 1. Задаются х0, e1, e3,d1,d2,a1 – постоянный шаг пункта 1 и a2 – постоянный шаг пункта 2 (a1<a2). Присваивается k=0.

Шаг 2. (Первый этап). Из точки хk осуществляется спуск на «дно оврага» с постоянным шагом  a1. При спуске вычисление очередной точки осуществляется с использованием  формул:

xj+1 = xj - a1g(xj), где  g(x)={g(1)(x),…,g(n)(x)},

Пусть этот процесс остановится в точке xl.

Шаг 3. (Второй этап). Из точки xl осуществляется спуск вдоль «дна оврага» с постоянным шагом a2. При спуске используются формулы:  xj+1 = xj - a2g(xj), где  g(x)={g(1)(x),…,g(n)(x)},

Пусть этот процесс остановился в точке xm.

Шаг 4. Если ||xk – xm|| £ e1 и || || £ e3, то полагаем:

и поиск минимума заканчивается. Иначе k=m и переходим к шагу 2.

4.9. Метод Флетчера-Ривса

Метод Флетчера-Ривса основан на том, что для квадратичной функции n переменных n одномерных поисков вдоль взаимно сопряженных направлений позволяют найти минимум.

Рассмотрим функцию

f ( x) = a+ bTx+ xTGx.

Одномерный поиск будем вести вдоль направлений, взаимно сопряженных по отношению к матрице G.

В качестве первого направления поиска из первой точки x1 возьмем направление наискорейшего спуска

d1= - g1  (1)

и найдем значение l1, минимизирующее функцию

f ( x1+ l d1).

Положим

x2= x1+ l 1d1  (2)

и произведем поиск в направлении d2, сопряженном направлению d1 (выберем вектор d2 как линейную комбинацию векторов d1 и - g2), и найдем

x3= x2+ l 2d2  (3)

минимизацией функции f ( x2+ l d2). Направление поиска d2 из точки x3 выбирается сопряженным направлениям d1 и d2. На (k + 1 ) - м шаге выбираем dk + 1 в виде линейной комбинации - gk + 1 , d1, d2,...,dk , сопряженной всем направлениям d1, d2,...,dk .

kr=1 Таким образом, dk+1=-gk+1+ ar dr, k = 1, 2 . . . Оказывается, все ar равны нулю, за исключением ak, так что

dk+1=-gk+1+a kdk   (4)

и

a k=g2k+1/g2k.  (5)

Прежде чем перейти к индуктивным рассуждениям, докажем справедливость соотношений (4) и (5) при k=1. Поскольку f(x2)=f (x1+ l1d1) является минимумом функции f(x1+ l1d1) на прямой, то