Метод Девідона – Флетчера – Пауела

Метод Девідона – Флетчера – Пауела являє собою алгоритм оптимізації, пристосований для відшукання безумовного мінімуму цільової функції, яка залежить від декількох змінних і яка має вигляд

(14.21)

Необхідні часткові похідні цільової функції по незалежним змінним. Оскільки в основі методу лежить допущення про унімодальність цільової функції, в тих випадках, коли є підстави припускати, що вона не є такою, потрібно брати декілька вхідних точок. На рис. 14.9 представлена схема алгоритму методу Девідона – Флетчера – Пауела. Спочатку в просторі проектування вибирають придатну початкову точку. Після цього, обчислюючи складові вектора градієнту визначають напрямок пошуку.

, i = 1, 2, ..., N,

тут – номер ітерації, а – елементи симетричної позитивно визначеної матриці розмірності N N. В процесі ітерацій ця матриця перетворюється в матрицю, зворотну матриці Гессе, елементами якої є другі часткові похідні цільової функції. Оскільки звичайно матриця заздалегідь невідома, то в якості початкової можна скористуватися будь-якою симетричною позитивно визначеною матрицею. Як правило, беруть найпростішу з них – одиничну матрицю. В цьому випадку пошук починається вздовж лінії найшвидшого спуску.

Одномірний пошук ведеться вздовж вхідного напрямку у відповідності з співвідношенням

(14.22)

де – величина кроку в напрямку пошуку. Знайшовши одновимірний оптимум, перевіряють результат на збіжність і, якщо вона досягнута, пошук припиняють. В протилежному випадку для подальшого пошуку вибирають новий напрямок, причому використовують колишнє співвідношення і нову матрицю , що визначається формулою

(14.23)

Елементи матриць і , які мають розмірність N N обчислюються по формулам

(14.24)

(14.25)

де верхнім індексом позначені транспоновані матриці, а і – відповідно вектори - стовпці різниць значень і градієнтів в двох точках. Вектори - стовпці визначаються виразами

У відповідності з правилами матричного обчислення числівники виразів для і являють собою матриці розмірності N N, а знаменники є скалярами. Визначивши новий напрямок пошуку, проводять одномірний пошук і продовжують ітераційний процес. При виконанні алгоритму, який описується, пошук після першої спроби ведеться в тих напрямках, в яких цільова функція в найближчому околі має значення, які наближаються до оптимального.

Лише в рідких випадках ці напрямки співпадають з напрямком градієнту. Тому даний алгоритм часто називають методом «відхиленого» градієнту. Вказана властивість методу Девідона – Флетчера – Пауела дозволяє обходити труднощі, які зв'язані з розривами похідних в просторі проектування. Широко розповсюджена думка, що цей метод є найбільш ефективним з усіх градієнтних методів. На відміну від методу Флетчера – Рівса він дає повну інформацію про кривизну поверхні цільової функції в точці мінімуму, однак при цьому вимагається більший об’єм пам'яті і більший час лічби для обробки матриці .

Рисунок 14.9 - Схема алгоритму методу Девідона – Флетчера – Пауела