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

gT2d1=-gT2g1=0.  (6)

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

g2=b+Gx2, g1=b+Gx1.

Тогда, если d1 и d2=-g2+a 1d1 сопряжены, то

dT2Gd1=0,

т. е.

-gT2Gd1+a 1dT1Gd1=0,

следовательно,

(-gT2-a 1gT1)G(x2-x1)/l 1=0,

откуда

(-gT2-a 1gT1)(g2-g1)/l 1=0.

Таким образом,

-g22+a1g21=0.

Остальные члены исчезают из соотношения (6), и, следовательно

a 1=g22/g21,

что и требовалось доказать. Это как раз и есть соотношение (5) при k=1.

Теперь перейдем к доказательству соотношений (4) и (5) по индукции, полагая, что векторы d1,d2,..,dk получены описанным выше способом и являются взаимно сопряженными.

Точка xk+1=xk+lkdk является минимумом функции f (xk+ lkdk) на прямой xk+ l kdk.

Тогда

gTk+1dk=0.  (7)

Имеем

xk+1=xk+lkdk= xk-1+lk-1dk-1+l kdk и т. д.

Таким образом,

xk+1=xj+1+е ki=j+1lidi; при 1≤ j≤ k-1,   (8)

следовательно,

Gxk+1=Gxj+1+е ki=j+1l iGdi,

тогда

gTk+1=gTj+1+е ki=j+1l idTiG при при 1≤ j≤ k-1,

откуда

gTk+1dj=gTj+1dj+е ki=j+1l idTiGdj.

В результате преобразований имеем gTj+1dj=0 (в соответствии с соотношениями (6) и (7)) и из-за взаимной сопряженности dTiGdj=0 при j<i. Таким образом, каждое слагаемое в правой части равно нулю.

Следовательно

gTk+1dj=0 при j=1,2,...,k-1   (9)

и из соотношения (7) окончательно имеем

gTk+1dj=0 при j=1,2,...,k.  (10)

Таким образом, было доказано, что вектор gk+1 ортогонален каждому из векторов d1,d2,...,dk.

Можно также показать, что вектор gk+1 ортогонален векторам g1,g2,...,gk.

Из соотношения (10) имеем

gTk+1dj=0 при j=1,2,...,k.

Так как из предположения в начале доказательства по индукции

dj=-gj+a j-1dj-1,

то приведенное выше соотношение принимает вид

-gTk+1gj+aj-1gTk+1dj-1=0,

следовательно, -gk+1gj=0, поскольку gTk+1dj-1=0 из соотношения (10).

Таким образом

gTk+1gj=0 при j=1,2,...,k.  (11)

Доказательство по индукции будет закончено, если показать, что вектор dk+1, определенный в соотношении (4), сопряжен с векторами d1,d2,...,dk.

Для j=1,2,...,k-1 имеем

dTk+1Gdj=-gTk+1Gdj+a kdTk Gdj=-gTk+1Gdj

в силу взаимной сопряженности.

Тогда

-gTk+1Gdj=-gTk+1G (xj+1-xj)/l j= gTk+1G (gj+1-gj)/l j=0

с учетом соотношения (11).

Таким образом, dTkGdj=0 при j=1,2,...,k-1, и это справедливо для любого ak. Для завершения доказательства необходимо определить ak так, чтобы выполнялось равенство

dTk Gdk=0:

Следовательно,

dTk Gdk=(-g2k+1+a kg2k)/ l k,

поскольку все другие члены из правой части исчезают в силу соотношений (10) и (11).

Следовательно, направление dk+1 будет сопряжено с направлением dk, если a k=g2k+1/g2k, что и требовалось доказать.

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

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

Алгоритм метода Флетчера-Ривса.

Множество X называется выпуклым, если оно содержит всякий отрезок, концы которого принадлежат X , т. е. λ* x1 + (1 – λ)*x2 ∊ X,

x1,x2∊X, λ∊[0,1].

Функция f(x), определенная на выпуклом множестве X, называется выпуклой, если

f(λ * x1 + (1 – λ) * x2) ≤ f(λ * x1) + f((1 – λ) * x2), x1,x2 ∊ X, λ ∊ [0, 1].

Алгоритм

1.  Задаются: x0— начальное приближение, ε1 > 0, ε2> 0, M – предельное число итераций;

2.  Количество итераций n = 0 ;

3.  Вычисляется: gradf(xⁿ);

4.  Вычисляется || gradf(xⁿ) || ;

4.1) если || gradf(xⁿ) || < ε1 , то

x*= xⁿ ;

4.2) если || gradf(xⁿ) || > ε1 , то к 5);

5.  n ≥ M

5.1) если выполняется, то x*= xⁿ ;

5.2), если не выполняется, то при n = 0 к 6)

при n ≥ 1 к 7)

6.  p0 = — gradf(x0);

7.  β = (|| gradf(xⁿ)|| / ||gradf(xⁿֿ¹) ||)²;

8.  pⁿ = - gradf(xⁿ) + βn-1 * pⁿֿ¹

9.  найти минимум функции φ(tn) = f( xⁿ — tn * pⁿ);

10.  xⁿ-¹ = xⁿ — tn *pⁿ;

11.  Проверяется условие || xⁿ-¹ – xⁿ ||< ε2 и f(xⁿ-¹ ) — f(xⁿ) < ε2

11.1) если оба условия выполняются, то x*= xⁿ-¹ ;

11.2) если хотя бы одно не выполняется, то n = n+1 и к 3).

4.10. Минимизация неквадратичной целевой функции

Метод Флетчера-Ривса может применятся для минимизации и неквадратичных функций. Он является методом первого порядка и в тоже время скорость его сходимости квадратична. Разумеется, если целевая функция не квадратична, метод уже не будет конечным. Поэтому после (n+1)-й итерации процедура повторяется с заменой x0 на xn+1, а счет заканчивается при ||f '(xk+1)|| £ ε, где ε – заданное число. При минимизации неквадратичных функций обычно применяется следующая модификация метода Флетчера-Ривса.

Алгоритм метода Флетчера-Ривса для неквадратичных целевых функций

Шаг 1. При  k = 0 ввод начального приближения x0 и условия останова ε3. Вычисление антиградиента S0= –f'(x0).

Шаг 2. Решение задачи одномерной минимизации по a функции f(xk + a·Sk),  в результате чего определяется величина шага ak и точка xk+1=xk+ak·Sk.

Шаг 3. Вычисление величин f(xk+1) и f '(xk+1).

Шаг 4. Если ||f '(xk+1)|| £ ε3, то точка xk+1 – решение задачи и на этом поиск заканчивается. Иначе определяется коэффициент βk по формуле:

Шаг 5. Вычисление Sk+1 по формуле Sk+1= – f '(xk+1)+βk·Sk;  k = k + 1, переход к шагу 2.

 Здесь I – множество индексов, I = {0, n, 2n, 3n, …}. Значения k, для которых βk = 0, называют моментами обновления метода. Таким образом, обновление метода происходит через каждые n шагов.

4.11. Метод Дэвидона — Флетчера — Пауэлла (ДФП)

Первоначально метод был предложен Дэвидоном и затем развит Флетчером и Пауэллом. Метод Дэвидона-Флетчера-Пауэлла называют также и методом переменной метрики. Он попадает в общий класс квазиньютоновских процедур, в которых направления поиска задаются в виде -Dj*grad(f(y)). Направление градиента является, таким образом, отклоненным в результате умножения на -Dj, где Dj - положительно определенная симметрическая матрица порядка n×n, аппроксимирующая обратную матрицу Гессе. На следующем шаге матрица Dj+1 представляется в виде суммы Dj и двух симметрических матриц ранга один каждая. В связи с этим схема иногда называется схемой коррекции ранга два.

Алгорим метода Дэвидона - Флетчера - Пауэлла

Начальный этап. Пусть eps >0 - константа для остановки. Выбрать точку x1 и начальную симметрическую положительно определенную матрицу D1 . Положить y1 = x1, k=j=1 и перейти к основному этапу.

Основной этап.

Шаг 1. Если ||grad(f(x))|| < eps, то остановиться; в противном случае положить dj = - Dj*grad(f(yj)) и взять в качестве lymj - оптимальное решение задачи минимизации f(yj + lym*dj) при lym ≥ 0. Положить y[j+1] = yj + lymj*dj. Если j < n, то перейти к шагу 2. Если j=n, то положить y1=x[k+1]=y[n+1], заменить k на k+1, положить j=1 и повторить шаг 1.

Шаг 2. Построить Dj+1 следующим образом:

Dj+1 = Dj +

где

pj = lymj*dj,

qj = grad(f(y[j+1])) - grad(f(yj)).

Заменить j на j+1 и перети к шагу 1.

4.12. Некоторые методы первого порядка в иной интерпретации

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