Метод сполучених напрямків Пауелла

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

Визначення. нехай

- симетрична матриця порядку. векториназиваються- сполученими, якщо вони лінійно незалежні і виконується умовапри.

Приклад. Розглянемо функцію

.

В якості матриці

можна взяти матрицю Гессе

.

В якості одного з напрямків виберемо

. тоді напрямокмає задовольняти рівності

.

Слід зауважити, що пов'язані напрямки вибираються неоднозначно. Однак якщо додати умова нормування, то їх можна визначити однозначно:

.

Затвердження. Будь-яка квадратична функція

змінних, що має мінімум, може бути мінімізована закроків, за умови, що пошук ведеться уздовж пов'язаних щодо матриці Гессе напрямків.

Довільна функція може бути досить добре представлена ​​в околиці оптимальної точки її квадратичної аппроксимацией. Тому пов'язані напряму можуть бути корисні для її оптимізації. Однак потрібно більш ніж

кроків. Для визначення пов'язаних напрямків застосовується метод, заснований на наступному твердженні.

Затвердження. Нехай задана квадратична функція

, дві довільні точкиі направленіеS..Еслі точка є точкою мінімуму функціївздовж направленіяSіз точки , а- точкою мінімуму функції вздовж направленіяSіз точки , то напрямокпов'язане з направленіемS.

Крок 1. Задати початкову точку

і систему лінійно незалежних напрямків (Вони спочатку можуть збігатися з напрямками координатних осей). мінімізувати функцію при послідовному русі по напрямками; використовуючи будь-якої одновимірний пошук; і отриману раніше точку мінімуму взяти в якості вихідної.

Крок 2. Виконати додатковий крок

, відповідний повного переміщенню на кроці 1. Обчислити точку(Рис 12). Перевірити критерій (*) включення нового напряму в систему сполучених напрямків.

Крок 3. Нехай

- максимальне зменшення цільової функції в одному з напрямків:

і

є напрямом, відповідним.

Якщо виконуються умови

(*)

то пошук продовжити уздовж первинних напрямків

з точкиабо(З тієї точки, де менше значення функції).

Крок 4. Якщо умови

не виконуються, то мінімізувати функціювздовж напрямку. Крапку цього мінімуму взяти в якості початкової на наступному етапі. На цьому етапі використовувати систему напрямків

,

тобто напрямок

замінити на, яке помістити в останній стовпець матриці напрямків.

Крок 5. Якщо

, то мінімум знайдений. В іншому випадку виконати крок 1.

Приклад. Клацнувши по значку, відкриється Mathcad документ методу сполучених напрямків, в якому можна виконати обчислення.

методом сполучених напрямків

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

Пауелл довів, що визначник матриці напрямків приймає максимальне значення тоді і тільки тоді, коли напрямки

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

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