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

Метод Давидона-Флетчера-Пауэлла (ДФП) основан на использовании соотношений (3.23) и (3.24).

Из уравнения

f(x0+h)-f(x0) =

=h^T*С f(x0)+1/2* h^TG(x0)* h+...

следует, что при выполнении условий непрерывности любую функцию можно аппроксимировать в окрестности точки x0 функцией

j(x)=f(x)+(x-x0)T* С f(x0)+* (x-x0)T*G(x0)* (x-x0), (3.23)

где G(x0)-матрица Гессе, вычисленная в точке x0.

Разумной аппроксимацией минимума функции f(x) может быть минимум функции j(x). Если последний находится в точке xm, то

С f(x0)+G(x0)(xm-x0)=0,

откуда

xm=x0-G-1(x0)* С f(x0),

или

xm=x0-G-1* g(x0) (3.24)

В методе Давидона-Флетчера-Пауэлла не требуется на каждом шаге вычислять обратный гессиан G-1(xi) так как направление поиска на шаге i является направлением -Hig(xi), где Hi - положительно определенная симметричная матрица, которая обновляется на каждом шаге, как это будет описано ниже. В пределе матрица H становится равной обратному гессиану.

Начнем поиск из начальной точки x0, взяв в качестве начальной матрицу H0 (обычно единичную матрицу, хотя в этом случае может подойти любая симметричная положительно определенная матрица). Итерационная процедура может быть представлена следующим образом (вместо g(xi) удобнее писать gi):

На шаге i имеется точка xi и положительно определенная симметрическая матрица Hi.

В качестве направления поиска взять направление di=-Hi* gi

Чтобы найти функцию l i, минимизирующую функцию f(xi+l idi), произвести одномерный поиск вдоль прямой xi+l* di.

Положить

vi=li* di.

5. Положить

xi+1=xi+vi.

6.Найти f(xi+1) и gi+1.Завершить процедуру, если величины |gi+1| или |vi| достаточно малы. В противном случае продолжить.

Замечание. Из соотношения ( g(xi+1)^Tpi=0, где pi-направление с целью нахождения минимума в точке) следует, что

gi+1T* vi=0.

7.Положить

ui=gi+1 - gi.

8.Обновить матрицу H следующим образом:

Hi+1=Hi+Ai+Bi,

где

Ai=vi* vi^T/(vi^T* ui);

Bi=-Hi*ui ui^T*Hi/ (ui^T*Hi ui).

9.Увеличить i на единицу и вернуться на шаг 2.

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

Powered by Drupal - Design by artinet