Метод Розенброка

 

Представляет усовершенствование метода покоординатного спуска.

 

 

Понятие сопряжённости векторов

В методе сопряженных градиентов используется понятие сопряжённости векторов.

< A, Q× B > = 0

Q – квадратная матрица того же порядка, что и вектора.

В этом случае вектора А и В будут Q сопряжёнными.

Q = [1]

< A * B > = 0

Сходимость метода сопряжённых градиентов строго обоснована для квадратичных целевых функций.

F(X) = A* X + X ^TЮ Х /2,

где Ю – матрица Гессе.

Минимизация такой функции осуществляется не более чем за n одномерных минимизаций вдоль определённым образом выбираемых сопряжённых направлений.

 

 

Метод сопряжённых градиентов (Флетчера – Ривса)

1) Задается начальная точка поиска Х: = Х ₀

2) Рассчитывается grad F(X)

3) Определяется первое направление для поиска P: = -grad F(X)

4) Производится одномерная минимизация на направлении P

F (X `) = min F(X +h P)

Получаем новую отображающую точку - X: = X `

5) Рассчитывается градиент в этой точке - grad F(X `)

6) Вычисляется коэффициент β, определяющий новое направление поиска.

7) Определяется новое сопряжённое направление

P: = - grad F(X`) +β P

8) Проверяется условие прекращения поиска, например, на близость grad F(X`) к 0 - grad F(X`) ≤ δ. Если они не выполнены, то переход к оператору 4)

9) Через n шагов поиска по сопряжённым направлениям осуществляется обновление метода, т.е. переход к оператору 2).

Предложены различные формулы для вычисления β. приведем одну из них:

 

grad F(X_i)* grad F(X_i)

β_i-1 =

grad F(X_i-1)* grad F(X_i-1)