Алгоритм методу паралельних дотичних

Метод паралельних дотичних (метод Пауэлла)

Цей метод використовує властивість квадратичної функції, що полягає в тім, що будь-яка пряма, що проходить через точку мінімуму функції х*, перетинає під рівними кутами дотичні до поверхонь рівного рівня функції в точках перетинання (рис. 8).

Цей метод використовує властивість квадратичної функції, що полягає в тім, що будь-яка пряма, що проходить через точку мінімуму функції х*, перетинає під рівними кутами дотичні до поверхонь рівного рівня функції в точках перетинання (рис. 8).

Рис.

8. Геометрична інтерпретація методу Пауэлла

Суть методу така. Вибирається деяка початкова точка х ₀ і виконується одномірний пошук уздовж довільного напрямку, що приводить у точку х ₁. Потім вибирається точка х ₂,що не лежить на прямій х ₀– х ₁, і здійснюється одномірний пошук уздовж прямій, паралельної х ₀– х ₁. Отримана в результаті точка х ₃ разом з точкою х ₁ визначає напрямок x ₁– х ₃ одномірні пошуки, що дає точку мінімуму х^*. У випадку квадратичної функції n змінних оптимальне значення знаходиться за п ітерацій. Пошук мінімуму при цьому в остаточному підсумку здійснюється у взаємно сполучених напрямках. У випадку неквадратичної цільової функції напрямки пошуку виявляються сполученими щодо матриці Гессе.

Крок 1

Задається початкова точка x ₀. За початкові напрямки пошуку р ₁, …, р ₀ приймають напрямки осей координат, тобто р_i = е_i, i= 1,..., n (тут e_i =(0,..., 0, 1, 0, …, 0)^T).

Крок 2

Виконують n одномірних пошуків уздовж ортогональних напрямків р_i, i= 1,..., п. При цьому кожний наступний пошук виконується з точки мінімуму, отриманої на попередньому кроці. Величина кроку а_k знаходиться з умови

.

Отриманий крок визначає точку

.

Крок 3

Вибирають новий напрямок p =– x_n – х ₀ і змінюють напрямки р ₁, …, р_n на р ₂, …, р_n, р. Останнім привласнюють позначення р [1],..., р [ n ].

Крок 4

Здійснюють одномірний пошук уздовж напрямку р = р_n = х_n – х ₀. Заміняють х ₀ на х_{n +1}= х_n+а_nр_п і приймають цю точку за початкову точку х ₀ для наступної ітерації. Переходять до кроку 1.

Таким чином, у результаті виконання розглянутої процедури здійснюється почергова заміна прийнятих спочатку напрямків пошуку. У підсумку після n кроків вони виявляться взаємно сполученими.

Дата добавления: 2015-05-23