Mетод Нелдера-Міда – це евристичний метод прямого пошуку, побудований на проведенні експериментів та визначенні (обчисленні) тільки значень критерію.
Обмеження на критерій оптимальності – унімодальність.
Метод застосовується при пошуку мінімуму критерію на реальних об’єктах та їх моделях в задачах багатопараметричної оптимізації при відсутності обмежень на параметри оптимізації.
Означення
Симплекс – це багатогранник (зразок) в просторі параметрів оптимізації з найменшою кількістю точок – вершин зразка. Для випадку двопараметричної задачі оптимізації, коли простір параметрів оптимізації є площиною, таким зразком є трикутник.
Регулярний симплекс в N -вимірному просторі параметрів оптимізації – це багатогранник, утворений з N +1 рівновіддалених одна від одної точками – вершинами багатогранника.
На площині (N = 2) регулярний симплекс – це правильний трикутник (рисунок 1, а). В тривимірному просторі параметрів оптимізації (N = 3) – тетраедр (рисунок 1, б), для N > 3 – гіпертетраедр.
На рисунках 1 а, б зображені:
1 – регулярний симплекс;
2 – деформований (скорочений) симплекс;
3 – деформований (видовжений) симплекс.
а б
Рисунок 1. Приклади регулярних та деформованих симплексів у двовимірному (а) та тривимірному (б) просторі параметрів оптимізації Х1, Х2, Х3
1.1 Послідовність пошуку мінімуму за симплексом:
1. Побудова початкового регулярного симплексу при заданій початковій точці х (0) та заданій довжині ребра регулярного симплексу α.
2. Проведення експериментів по визначенню значень критерію у всіх точках (вершинах) регулярного симплексу та вибір “найгіршої” та двох “кращих” точок симплексу.
“Найкраща” точка симплексу – це одна із вершин симплексу, в якій значення критерію є найменшим.
“Найгірша” точка симплексу – це одна із вершин симплексу, в якій значення критерію є найбільшим;
3. Побудова нового (відбитого) симплексу.
4. Проведення експерименту по визначенню критерію у новій точці відбитого симплексу та порівняння його значення з найгіршою та двома кращими точками початкового симплексу.
5. Прийняття рішення про видовження/скорочення відбитого симплексу (в залежності від результатів порівняння в п.4) та обчислення координат нової відбитої точки.
6. Перевірка умов зупинки пошуку та повернення до п.3 у випадку їх невиконання.
1.2 Побудова початкового регулярного симплексу
Для побудови початкового регулярного симплекса потрібно, щоб були задані х (0) – початкова точка і α – довжина ребра.
В методі Нелдера-Міда для початкового симплексу α = 1, а координати вершин регулярного симплексу обчислюють за формулою:
де: і – номер вершини регулярного симплекса (на площині і =1,2,3);
j – номер координати вершини в N-вимірному просторі (на площині j =1,2);
N – число параметрів оптимізації.
Приклад побудови початкового регулярного симплексу для N =2
; 
Приклад побудови початкового регулярного симплексу для N =3
, 
а б
Рисунок 2. Орієнтація регулярних початкових симплексів за методом Нелдера-Міда:
а – для N =2; б – для N =3
1.3 Проведення експериментів по визначенню значень критерію в точках (вершинах) початкового симплексу та вибір двох найкращих точок симплексу
а) Визначають значення критерію у вершинах симплексу f(1), f(2), f(3),..., 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 ) = х (0)
λ=2, то х ( H ) = 2 х (с) – х (0) – одержимо новий регулярний симплекс (симетричний до початкового).
При λ>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(H1), то приймають:
х ( h ) = х (g), f(h) = f(g);
х (g) = х (l), f(g) = f(l);
х ( l ) = х (H1), f(l) = f(H1),
інакше,
якщо f(H) < f(H1), то приймають:
х ( 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(H2)
то приймають:
х ( h ) = х (g), f(h) = f(g);
х (g) = х (l), f(g) = f(l);
х ( l ) = х (H2), f(l) =f(H2),
інакше,
якщо f(h) > f(g) > f(H2) > 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), то зменшують довжину ребра α, приймають х (0) = х ( l ) і повертаються до побудови нового регулярного сиплексу (п.1.4).
1.7 Перевірка умов зупинки пошуку
Ітерації пошуку продовжують доти, поки значення цільової функції у вершинах симплексу будуть відрізнятись незначно.
Критерієм є величина
,
де 
.
Якщо σ<ε, де ε – задана величина, то всі значення функції близькі між собою і знаходяться поблизу точки мінімуму. У цьому випадку подальший пошук мінімуму припиняється, а за мінімум приймають точку з координатами x ( l ).
Якщо σ>ε, то будують наступний відбитий симплекс.
а
б
Рисунок 4. Переміщення та деформація симплексу в полі параметрів оптимізації при пошуку екстремуму для N =2
Рисунок 5. Блок-схема алгоритму пошуку мінімуму за методом Нелдера-Міда
