Основні теоретичні відомості. Mетод Нелдера-Міда – це евристичний метод прямого пошуку, побудований на проведенні експериментів та визначенні (обчисленні) тільки значень критерію.

Mетод Нелдера-Міда – це евристичний метод прямого пошуку, побудований на проведенні експериментів та визначенні (обчисленні) тільки значень критерію.

Обмеження на критерій оптимальності – унімодальність.

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

Означення

Симплекс – це багатогранник (зразок) в просторі параметрів оптимізації з найменшою кількістю точок – вершин зразка. Для випадку двопараметричної задачі оптимізації, коли простір параметрів оптимізації є площиною, таким зразком є трикутник.

Регулярний симплекс в N -вимірному просторі параметрів оптимізації – це багатогранник, утворений з N +1 рівновіддалених одна від одної точками – вершинами багатогранника.

На площині (N = 2) регулярний симплекс – це правильний трикутник (рисунок 1, а). В тривимірному просторі параметрів оптимізації (N = 3) – тетраедр (рисунок 1, б), для N > 3 – гіпертетраедр.

На рисунках 1 а, б зображені:

1 – регулярний симплекс;

2 – деформований (скорочений) симплекс;

3 – деформований (видовжений) симплекс.

а б

Рисунок 1. Приклади регулярних та деформованих симплексів у двовимірному (а) та тривимірному (б) просторі параметрів оптимізації Х₁, Х₂, Х₃

1.1 Послідовність пошуку мінімуму за симплексом:

1. Побудова початкового регулярного симплексу при заданій початковій точці х ⁽⁰⁾ та заданій довжині ребра регулярного симплексу α.

2. Проведення експериментів по визначенню значень критерію у всіх точках (вершинах) регулярного симплексу та вибір “найгіршої” та двох “кращих” точок симплексу.

“Найкраща” точка симплексу – це одна із вершин симплексу, в якій значення критерію є найменшим.

“Найгірша” точка симплексу – це одна із вершин симплексу, в якій значення критерію є найбільшим;

3. Побудова нового (відбитого) симплексу.

4. Проведення експерименту по визначенню критерію у новій точці відбитого симплексу та порівняння його значення з найгіршою та двома кращими точками початкового симплексу.

5. Прийняття рішення про видовження/скорочення відбитого симплексу (в залежності від результатів порівняння в п.4) та обчислення координат нової відбитої точки.

6. Перевірка умов зупинки пошуку та повернення до п.3 у випадку їх невиконання.

1.2 Побудова початкового регулярного симплексу

Для побудови початкового регулярного симплекса потрібно, щоб були задані х ⁽⁰⁾ – початкова точка і α – довжина ребра.

В методі Нелдера-Міда для початкового симплексу α = 1, а координати вершин регулярного симплексу обчислюють за формулою:

де: і – номер вершини регулярного симплекса (на площині і =1,2,3);

j – номер координати вершини в N-вимірному просторі (на площині j =1,2);

N – число параметрів оптимізації.

Приклад побудови початкового регулярного симплексу для N =2

;

Приклад побудови початкового регулярного симплексу для N =3

а б

Рисунок 2. Орієнтація регулярних початкових симплексів за методом Нелдера-Міда:

а – для N =2; б – для N =3

1.3 Проведення експериментів по визначенню значень критерію в точках (вершинах) початкового симплексу та вибір двох найкращих точок симплексу

а) Визначають значення критерію у вершинах симплексу f⁽¹⁾, f⁽²⁾, f⁽³⁾,..., f^(N), f^(N+1), де f^(і) – значення критерію в і – тій вершині симплексу.

б) Із N +1 вершин симплексу вибирають “найгіршу” точку симплексу (k – вершину з найбільшим значенням критерію f⁽^k⁾) і позначають її як х ^(h) (присвоюють х ^(h) = х ^(k), f⁽^h⁾= f⁽^k⁾).

в) Із N +1 вершин симплексу вибирають дві вершини, в яких значення критерію є найменшими (f^(g) та f^(l), f^(g) > f^(l)) і позначають їх як х ^(g) та х ^(l) відповідно.

1.4 Побудова нового (відбитого) симплексу

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

для N>2,

де k – номер найгіршої вершини симплексу, визначений у п.1.3.б.

для N =2 (рисунок 3)

Рисунок 3. Графічне зображення нових симплексів у двовимірному просторі параметрів оптимізації

Рівняння прямої, яка проходить через х ⁽ ^h ⁾ і х ^(с):

х (λ) = х ⁽ ^h ⁾ + λ(х ^(с) – х ⁽ ^h ⁾)

де λ – довільне дійсне число.

Якщо:

– нового симплексу не одержимо

λ=1, то х ⁽ ^H ⁾ = х ^(с)

λ=0, то х ⁽ ^H ⁾ = х ⁽⁰⁾

λ=2, то х ⁽ ^H ⁾ = 2 х ^(с) – х ⁽⁰⁾ – одержимо новий регулярний симплекс (симетричний до початкового).

При λ>2 одержимо видовжений симплекс.

При 1<λ<2 одержимо скорочений симплекс.

В методі Нелдера-Міда спочатку приймають λ=2 та обчислюють координати нового симетричного симплексу x ⁽ ^h ⁾.

1.5 Проведення експерименту по визначенню критерію у новій вершині відбитого симплексу та порівняння його значення з найгіршою та двома кращими точками початкового симплексу

Проводять експеримент – визначають значення критерію f⁽^H⁾ в точці x ^(Н).

Виконують порівняння значень критерію і отримують один із варіантів:

а) f⁽^h⁾>f⁽^g⁾ > f⁽^l⁾ > f⁽^H⁾

б) f⁽^h⁾>f⁽^g⁾ > f⁽^H⁾> f⁽^l⁾

в) f⁽^h⁾>f⁽^H⁾ >f⁽^g⁾ > f⁽^l⁾

г) f⁽^H⁾ > f⁽^h⁾>f⁽^g⁾ > f⁽^l⁾

1.6 Прийняття рішення про видовження/скорочення відбитого симплексу

а) Якщо f⁽^h⁾>f⁽^g⁾ > f⁽^l⁾ > f⁽^H⁾, то приймають λ=3 та обчислюють координати нового видовженого симплексу X^(Н1).

Якщо f⁽^H⁾ >f⁽^H¹⁾, то приймають:

х ⁽ ^h ⁾ = х ^(g), f⁽^h⁾⁼f⁽^g⁾;

х ^(g) = х ^(l), f⁽^g⁾ ⁼ f⁽^l⁾;

х ⁽ ^l ⁾ = х ^(H1), f⁽^l⁾ = f⁽^H¹⁾,

інакше,

якщо f⁽^H⁾ < f⁽^H¹⁾, то приймають:

х ⁽ ^h ⁾ = х ^(g), f⁽^h^{) =}f⁽^g⁾;

х ^(g) = х ^(l), f⁽^g⁾ ⁼ f⁽^l⁾;

х ⁽ ^l ⁾ = х ^(H), f⁽^l⁾ ⁼f⁽^H⁾.

б) Якщо f⁽^h⁾>f⁽^g⁾ > f⁽^H⁾> f⁽^l⁾, то приймають λ=1,5 та обчислюють координати нового стиснутого симплексу x ^(Н2).

Якщо f⁽^h⁾>f⁽^g⁾ > f⁽^H^{) >} f⁽^l⁾> f⁽^H²⁾

то приймають:

х ⁽ ^h ⁾ = х ^(g), f⁽^h⁾⁼f⁽^g⁾;

х ^(g) = х ^(l), f⁽^g⁾ ⁼ f⁽^l⁾;

х ⁽ ^l ⁾ = х ^(H2), f⁽^l⁾ ⁼f⁽^H²⁾,

інакше,

якщо f⁽^h⁾> f⁽^g⁾ > f⁽^H²⁾ > f⁽^H⁾> f⁽^l⁾, то приймають:

х ⁽ ^h ⁾ = х ^(g), f⁽^h⁾⁼f⁽^g⁾;

х ^(g) = х ^(Н), f⁽^g⁾ ⁼ f⁽^Н⁾;

х ⁽ ^l ⁾ = х ⁽ ^l ⁾, f⁽^l⁾ = f⁽^l⁾.

в) Якщо f⁽^h⁾>f⁽^H⁾ >f⁽^g⁾ > f⁽^l⁾, або якщо f⁽^H⁾ >f⁽^h⁾>f⁽^g⁾ > f⁽^l⁾, то зменшують довжину ребра α, приймають х ⁽⁰⁾ = х ⁽ ^l ⁾ і повертаються до побудови нового регулярного сиплексу (п.1.4).

1.7 Перевірка умов зупинки пошуку

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

Критерієм є величина

де .

Якщо σ<ε, де ε – задана величина, то всі значення функції близькі між собою і знаходяться поблизу точки мінімуму. У цьому випадку подальший пошук мінімуму припиняється, а за мінімум приймають точку з координатами x ⁽ ^l ⁾.

Якщо σ>ε, то будують наступний відбитий симплекс.

Рисунок 4. Переміщення та деформація симплексу в полі параметрів оптимізації при пошуку екстремуму для N =2

Рисунок 5. Блок-схема алгоритму пошуку мінімуму за методом Нелдера-Міда