Основні теоретичні відомості

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. Блок-схема алгоритму пошуку мінімуму за методом Нелдера-Міда