Модифікована система пошука по симплексу Нелдера – Міда

Хоча формула для визначення регулярного симплексу виявляється доволі зручною при побудові початкового зразка, проте вірних підстав для збереження властивостей регулярності симплексу в процесі пошуку немає. Отже, при віддзеркаленні симплексу існує можливість, як його розтягування, так і стискування. З цієї причини процедуру Нелдера- Міда інколи називають методом пошуку по деформованому багатограннику. При розрахунках по методу Нелдера- Міда використовуються вершини симплексу x_(h), яким відповідає найбільше значення цільової функції f_(h), вершина x_(g), якій відповідає наступне по величині значення цільової функції f_(g) і x_(l), якій відповідає найбільше значення цільової функції f_(е).

Віддзеркалення вершини симплексу здійснюється за прямою:

x=х_(h)+x*(x_С-x_(h)) (1.9)

x=x_(h)+(1+θ)*(x_С-x_(h)) (1.10)

При θ =1 має місце нормальне віддзеркалення симплексу, оскільки точка x_нове розташовується на відстані (x_С-x_(h))) від точки x_с, при -1< =θ < =+1 спостерігається стисле віддзеркалення або стиск симплексу. Вибір θ => 1забеспечує розтягнуте віддзеркалення або розтягування симплексу.

Різні види відображення представлені на рис. 1.1

x_h

а)

x_h

б)

x_h

в)

x_h

д)

Рисунок 1.1 - Розтягування та зжимання симплексу:

а) нормальне відображення (θ =α =1), f_(l)< f_(g.);

б) розтягування (θ =α > 1), f(x_нов)< f_(l);

в) стиск (θ =β < 0), f(x_нов)> f_(g), f(x_нов)> f_(h);

д) стиск (θ =β > 0), f^(g)< f(x_нов)< f^(h)

Три значення параметру θ, що використовуються при нормальному віддзеркаленні, стиску та розтягуванні, позначаються (λ, β, γ).

Реалізація методу починається з побудови початкового симплексу і визначення точок x_(h), x_(g), x_(е), x_с, після нормального віддзеркалення здійснюється перевірка значень цільової функції за критерієм закінчення пошуку в точках відображеного симплексу, якщо пошук не закінчений за допомогою тестів, обирається одна з операцій: нормальне віддзеркалення, розтягування або стиск. Ітерації продовжуються, поки зміни значень цільової функції в вершинах симплексу не стануть незначними. Як задовільні значення параметрів (λ, β, γ) Нелдер і Мід рекомендують використовувати λ =1, β =0, 5, γ =2.

Метод Нелдера-Міда володіє достатньою ефективністю і високою надійністю в умовах наявності випадкових збурень або помилок при визначенні значень цільової функції.

1.2 Порядок виконання роботи

1.2.1 Написати програму, що реалiзує метод пошуку Нелдера-Мiда.

1.2.2 За допомогою розробленої програми знайти мiнiмум функцiї. Функції обирати згідно варіанту з табл. 1.1.

1.2.3 Навести приклади ситуацiй, коли застосування методу Нелдера-Мiда є прийнятним та неприйнятним.

Таблиця 1.1 – Варіанти досліджуваних функцій

1.3 Зміст звіту

1.3.1 Сформульована мета роботи.

1.3.2 Алгоритм та програма, що реалізує метод Нелдера-Мiда.

1.3.3 Результати роботи програми.

1.3.4 Аналіз отриманих результатів і висновки.

1.4 Контрольні питання

1.4.1 Наведіть класифікацію методів безумовної багатовимірної оптимізації.

1.4.2 Опишіть метод пошуку за симплексом.

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

1.4.4 Охарактеризуйте ситуацію циклічного руху під час симплексного пошуку.

1.4.5 Що є критерієм закінчення симплексного пошуку?

1.4.6 Як визначаються координати вершин початкового симплексу?

1.4.7 Як визначаються координати відображеної вершини симплексу?

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

1.4.9 Коли треба використовувати симплексний метод?

1.4.10 Опишіть модифіковану процедуру пошуку за симплексом Нелдера-Міда.

ЛАБОРАТОРНА РОБОТА № 2. МЕТОД ПОШУКУ ХУКА-ДЖИВСА. МОДИФІКАЦІЇ ПРОЦЕДУРИ ХУКА-ДЖИВСА

Мета роботи - вивчити метод безумовної багатовимiрної оптимiзацiї Хука-Дживса.

2.1 Короткі теоретичні відомості

Процедура Хука-Дживса є комбінацією дослідницького пошуку і прискореного пошуку за зразком з використанням певних евристичних правил. Дослідницький пошук орієнтований на виявлення характеристик локальної поведінки цільової функції і визначення напряму уздовж «ярів». Отримана в результаті дослідницького пошуку інформація потім використовується в процесі пошуку за зразком при русі по «ярах».

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

Якщо в результаті виходить точка з меншим значенням цільової функції, чим в точці Х^(к), то вона розглядається як нова базова точка Х^(к+1). З іншого боку, якщо дослідницький пошук невдалий, необхідно повернутися в точку Х^(к) і провести дослідницький пошук з метою виявлення нового напряму мінімізації. Зрештою виникає ситуація коли такий пошук не приводить до успіху. В цьому випадку потрібно зменшити величину шагу шляхом введення деякого множника і відновити дослідницький пошук. Пошук завершується коли величина шагу стає досить малою. Послідовність точок, отриманих в процесі реалізації методу, можна записати в такому вигляді:

Х^(к) – поточна базова точка;

Х^(к-1) – попередня базова точка;

Х_р^(к+1) – точка побудови в наближенні до зразка;

Х^(к+1) – наступна нова базова точка.

Приведена послідовність характеризує логічну структуру пошуку по методу Хука-Дживса.

Алгоритм методу пошуку Хука-Дживса

Шаг 1: Визначити початкову точку Х₀, прирощення ∆ _i, i=1, …, N коефіцієнт зменшення кроку α > 1 і параметр закінчення пошуку ε > 0.

Шаг 2: Провести дослідницький пошук.

Шаг 3: Перевірити, чи був дослідницький пошук вдалий (чи знайдена точка з меншим значенням цільової функції)?

«Так»: перейти до шагу 5.

«Ні»: продовжити.

Крок 4: перевірка закінчення пошуку. Чи виконується нерівність ׀ ׀ Δ х׀ ׀ > ε?;

«Так»: припинити пошук, поточна точка апроксимує точку оптимуму Х*.

«Ні»: зменшити приріст ∆ _i = ∆ _i/α _i, i=1, …, N. Перейти до шагу 2.

Шаг 5: Провести пошук за зразком: Х_р^(к+1)= Х^(к)+ (Х^(к)- Х^(к-1))

Шаг 6: Провести дослідницький пошук, використовуючи Х_р^(к+1) як базову точку. Хай Х^(к+1) – отримана в результаті точка.

Шаг 7: Чи виконується умова f(Х^(к+1))< f(Х^(к))?.

«Так»: покласти Х^(к-1) = Х^(к); Х^(к)= Х^(к+1) . Перейти до шагу 5.

«Ні»: перейти до шагу 6.

Приклад пошуку за методом Хука-Дживса.

Знайти точку мінімуму функції f(x)=8x₁²+4x₁x₂+5x₂², використовуючи точку x⁽⁰⁾[-4; -4]^T.

Розв’язок.

Для того, щоб використати метод прямого пошуку Хука-Дживса, необхідно знати такі векторні величини:

- векторна величина прирощення ∆ x=[-1; 1]^T;

- коефіцієнт зменшення шагу α =2;

- параметр закінчення пошуку ε =10^-4.

Ітерації починаються з дослідницького пошуку навколо точки x₀, що відповідає значенню f(x⁽⁰⁾)=272.

Фіксуючи х₂, дамо приріст x₁.

х₂= -4.

x₁= -4+1 → f(-3; -4)=200< f(x⁽⁰⁾)=272 → успіх.

Це означає, що необхідно зафіксувати x₁=-3 та дати приріст змінній х_2.

х₂=-3

x₁=-4+1 → f(-3; -3)=153< 200 → успіх.

Таким чином, в результаті дослідницького пошуку знайдемо точку x⁽¹⁾=[-3; -3]^T.

f(x₁⁽¹⁾)=153.

Оскільки дослідницький пошук був успішнім, переходимо до пошуку за зразком.

X⁽²⁾=x⁽¹⁾+(x⁽¹⁾-x⁽⁰⁾)=[-2; -2]^T.

F(x_p⁽²⁾)=68.

Далі проводимо дослідницький пошук навколо точки x_p⁽²⁾, який виявляється успішним при застосуванні додатних змінних x_1, х₂.

В результаті отримуємо точку x⁽²⁾=[-1; -1]^T.

f(x₂)=17.

F(x⁽²⁾)< f(x⁽¹⁾), пошук за зразком можемо вважати успішним, x⁽²⁾ стає новою базовою точкою при проведенні нового пошуку за зразком.

Ітерації продовжуються доки зменшення величини шагу не вкаже на закінчення пошуку в околиці точки.

Модифікації процедури Хука-Дживса

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

Завдяки цьому алгоритм Хука-Дживса знаходить широке застосування на практиці.

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

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

Експерименти дозволили допрацювати іншу фазу реалізації алгоритму, яку називають використанням зразка.

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

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

2.2 Порядок виконання роботи

2.2.1 Написати програму, що реалiзує метод пошуку Хука-Дживса.

2.2.2 За допомогою розробленої програми знайти мiнiмум функцiї (табл. 1.1).

2.2.3 Навести приклади ситуацій, коли застосування методу Хука-Дживса є прийнятним та неприйнятним.

2.2.4 Порiвняти методи Нелдера-Мiда та Хука-Дживса за точнiстю знаходження оптимиму, кiлькiстю iтерацiй та часом роботи.

2.3 Зміст звіту

2.3.1 Сформульована мета роботи.

2.3.2 Алгоритм та програма, що реалізує метод Хука-Дживса.

2.3.3 Результати роботи програми.

2.3.4 Аналіз отриманих результатів і висновки.

2.4 Контрольні питання

2.4.1 Опишіть метод пошуку Хука-Дживса.

2.4.2 Яка мета дослідного пошуку в процедурі Хука-Дживса?

2.4.3 В чому полягає пошук за зразком в процедурі Хука-Дживса?

2.4.4 Які існують модифікації процедури Хука-Дживса?

ЛАБОРАТОРНА РОБОТА № 3 Метод спряжених напрямків Пауелла

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

3.1 Короткі теоретичні відомості

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

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

Завдання з квадратичними цільовими функціями займають важливе місце в теорії оптимізації з двох причин:

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

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

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

Процедура перетворення квадратичної функції

q(х) = a+b^Tх+1/2х^ТCх (3.1)

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

Q(х) = х^TCх (3.2)

шляхом перетворення

х = TZ (3.3)

приводиться до вигляду

Q(х)=Z^TT^TCTz=Z^TDZ, (3.4)

де D — діагональна матриця, тобто елементи D відмінні від нуля тільки при i=j.

Нехай t_j — j-й стовпець матриці Т. Тоді перетворення дозволяє записати кожен вектор х у вигляді лінійної комбінації стовпців t_j:

х = TZ = t₁z₁ + t₂z₂ +... + t_Nz_N (3.5).

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

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

Проілюструємо вищевикладене прикладом.

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

Розглянемо функцію:

f(x)=4х₁²+3х₂²-4х₁х₂+х₁

і перетворення: х₁=z₁+0.5*z₂; x₂=z₂

Перетворена квадратична функція набирає такого вигляду:

f(z)=4z₁²+2z₂²+z₁+0.5z₂

Це перетворення не є єдиним, зокрема перетворення

х= 1 0 z

2/3 1

також приводить матрицю квадратичної форми до діагонального вигляду.

Задаючи початкову точку х₀=[0, 0]^т і два стовпці матриці перетворення t₁=[1, 0]^Т, t₂=[0.5, 1]^Т можна знайти точку оптимуму в результаті проведення двох послідовних пошуків в напрямах t₁, t₂. Пошук у напряму t₁ по формулі:

х₍₁₎=х(0)+λ *t₁=[0, 0]^Т+ λ *[1, 0]^Т

дозволяє отримати λ =1/8 і точку х₍₁₎ =[-1/8, 0]^Т.

Далі х₍₂₎ = х₍₁₎+λ *t₂= [-1/8, 0]^Т+ λ *[0.5, 1]^Т=[-1/8, 0]^Т-1/8*[0.5, 1]^Т=

=[-3/16, -1/8]^Т.

З розглянутого прикладу виходить, що якщо система векторів t_j, j=1, …, N або система зв'язаних напрямів побудована, то точку оптимуму квадратичної функції можна знайти в результаті реалізації N одновимірних пошуків, які проводяться уздовж кожного з N напрямів t_j. Таким чином, невирішеними залишаються лише питання, пов'язані з побудовою системи векторів t_j. Якщо матриця С відома, то матрицю перетворення Т можна знайти за допомогою методу Гауса-Жордана.

Метод Гауса-Жордана дозволяє представити матрицю С у вигляді перетворення

С=Р^ТDР (3.6),

(Р^-1)^ТС(Р^-1)=D, Т=Р^-1 (3.7).

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

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