Перегляд вихідного коду сторінки Метод Нелдера — Міда

{| class="infobox bordered" style="width: 22em; text-align: left; font-size: 95%;"
|-
| colspan="2" style="text-align:center;" | [[Файл:Nelder-Mead Rosenbrock.gif|320px|]]
|-
| colspan="2" style="text-align:center;" | [[Файл:Nelder-Mead Himmelblau.gif|320px|]]
Послідовні симплекси в функції Нелдера-Міда для [[Функція Розенброка|Функції Розенброка]] '''(вгорі)''' та {{Нп|Функція Хіммельблау|функції Химмельблау|en|Himmelblau's function}} (внизу)
|-
|-
|}

[[Файл:Nelder-Mead Simionescu.gif|thumb|320px|Мінімальний пошук Нелдера-Міда [[Тестові функції для оптимізації|функції Сімінеску]]. Упорядкування симплексних вершин за їх значенням, причому 1 має найменше (найкраще) значення.]]
{{не плутати2|[[симплекс-метод]]ом Данцига для задачі лінійної оптимізації}}

'''Метод Нелдера&nbsp;— Міда''' ('''метод симплексного спуску''', '''метод амеби''', або '''політопний метод''')) є популярним [[чисельні методи|чисельним методом]], що використовується для пошуку мінімуму або максимуму [[Функція втрат|цільової функції]] в багатовимірному просторі. Це ''метод прямого пошуку'' (на основі порівняння функцій) і часто застосовується до нелінійних задач [[Оптимізація (математика)|оптимізації]], для яких похідні можуть не бути відомі. Проте, підхід Нелдера-Міда є [[Евристика|евристичним]] методом пошуку, який може сходитися до нестаціонарних точок<ref name="PM">
* {{cite journal | last1 = Powell | first1 = Michael J. D. | authorlink = Michael J. D. Powell | year = 1973 | title = On Search Directions for Minimization Algorithms | url = | journal = Mathematical Programming | volume = 4 | issue = | pages = 193–201 | doi=10.1007/bf01584660}}
* {{ cite journal | last = McKinnon | first = K.I.M. | title =Convergence of the Nelder–Mead simplex method to a non-stationary point | journal =SIAM Journal on Optimization | year = 1999 | volume = 9 | pages =148–158 | doi = 10.1137/S1052623496303482| citeseerx = 10.1.1.52.3900 }} (algorithm summary online).
</ref>, стикаючись із задачами, які можуть бути розв'язані альтернативними методами<ref name="YKL">
* Yu, Wen Ci. 1979. «Positive basis and a class of direct search techniques». ''Scientia Sinica'' [''Zhongguo Kexue'']: 53—68.
* Yu, Wen Ci. 1979. «The convergent property of the simplex evolutionary technique». ''Scientia Sinica'' [''Zhongguo Kexue'']: 69–77.
* {{ cite journal | last = Kolda | first = Tamara G. |authorlink1=Tamara G. Kolda|author2=Lewis, Robert Michael |author3=Torczon, Virginia | year =2003 | title = Optimization by direct search: new perspectives on some classical and modern methods | journal = SIAM Rev. | volume =45 | issue = 3 | pages = 385–482 | doi = 10.1137/S003614450242889|citeseerx=10.1.1.96.8672 }}
* {{ cite journal | last = Lewis | first = Robert Michael |author2=Shepherd, Anne |author3=Torczon, Virginia | year = 2007 | title = Implementing generating set search methods for linearly constrained minimization | journal = SIAM J. Sci. Comput. | volume = 29 | issue = 6 | pages = 2507–2530 | doi = 10.1137/050635432| citeseerx = 10.1.1.62.8771 }}
</ref>.

Метод Нелдера&nbsp;— Міда запропонували {{Нп|Джон Нелдер|Джон Нелдер|en|John Nelder}} і {{Нп|Роджер Мід|Роджер Мід|en|Roger Mead}} у 1965 році<ref name="NM">{{cite journal | last = Nelder | first = John A. |author2=R. Mead | title = A simplex method for function minimization | journal = Computer Journal | volume = 7 | issue = 4 | year = 1965 | pages = 308–313 | doi =  10.1093/comjnl/7.4.308}}</ref>, як варіант модифікації методу Спендлі<ref name="SHH">
{{ cite journal | last1 = Spendley |  first1 = W | last2 = Hext | first2 = GR | last3 = Himsworth | first3 = FR | year = 1962 | title = Sequential Application of Simplex Designs in Optimisation and Evolutionary Operation | url = https://archive.org/details/sim_technometrics_1962-11_4_4/page/441 | journal =  Technometrics | volume = 4 |  issue = 4 | pages = 441–461 | doi = 10.1080/00401706.1962.10490033 }}</ref>.

== Загальний опис ==
У методі використовується поняття [[симплекс]]а, який є спеціальним [[політоп]]ом ''n''&nbsp;+&nbsp;1 вершин в ''n'' вимірах. Приклади симплексів включають відрізок на лінії, трикутник на площині, [[Чотиригранник|тетраедр]] у тривимірному просторі тощо.

Метод апроксимує локальний оптимум задачі з ''n'' змінними, коли цільова функція змінюється плавно і є [[унімодальність|унімодальною]]. Типові реалізації мінімізують функції, максимум <math>f(\mathbf x)</math> можна знайти за допомогою мінімізації <math>- f(\mathbf x)</math>.

Наприклад, інженер підвісного моста повинен вибрати, якою має бути товщина кожної стійки, кабелю і причалу. Ці елементи взаємозалежні, але нелегко візуалізувати вплив зміни стану будь-якого конкретного елемента. Моделювання таких складних конструкцій часто є надзвичайно обчислювально складним для запуску, можливо, тому що вони потребують більше годин на виконання. Метод Нелдера&nbsp;— Міда вимагає у вихідному варіанті не більше двох оцінок на ітерацію, за винятком описаної пізніше операції '''стягування''', що є перевагою порівняно з іншими методами оптимізації прямого пошуку. Однак загальна кількість ітерацій пропонованого оптимуму може бути великою.

Метод у ''n'' вимірах зберігає набір ''n+1'' тестових точок, розташованих як [[симплекс]]. Потім він екстраполює поведінку цільової функції, виміряної в кожній тестовій точці, щоб знайти нову тестову точку і замінити одну зі старих тестових точок на нову, це складає основний цикл методу. Найпростіший підхід полягає в тому, щоб замінити найгіршу точку точкою, відбитою через [[центроїд]] решти ''n'' точок. Якщо ця точка краща, ніж краща поточна точка, то ми можемо спробувати розтягнути експоненціально по цій лінії. З іншого боку, якщо ця нова точка не є набагато кращою, ніж попередня величина, то ми переходимо до наступного значення, тому ми стягуємо симплекс у кращу точку. Інтуїтивне пояснення алгоритму представлено в<ref name="NR">* {{Cite book | last1=Press | first1=WH | last2=Teukolsky | first2=SA | last3=Vetterling | first3=WT | last4=Flannery | first4=BP | year=2007 | title=[[Numerical Recipes: The Art of Scientific Computing]] | edition=3rd | publisher=Cambridge University Press | location=New York | isbn=978-0-521-88068-8 | chapter=Section 10.5. Downhill Simplex Method in Multidimensions }}</ref>:
<blockquote>
Метод спадання симплекса тепер виконує ряд кроків, більшість кроків просто переміщує точку симплекса, де функція набуває найбільшого значення («найвища точка») через протилежну сторону симплекса до нижньої точки. Ці кроки називаються відбиттями, і вони побудовані для збереження [[об'єм]]у симплекса (і, отже, збереження його невиродженості). Коли він може це зробити, метод розширює симплекс в тому чи іншому напрямку, щоб зробити великі кроки. Коли він досягає «найнижчої точки», метод починає рухатися в поперечному напрямку і намагається просунутися вздовж лінії спадання. У ситуації, коли симплекс намагається «пройти крізь голку», то він стискається у всіх напрямках, стягуючи себе навколо своєї найнижчої (кращої) точки.
</blockquote>

На відміну від сучасних методів оптимізації, евристика Нелдера&nbsp;— Міда може сходитися до нестаціонарної точки, якщо задача не задовольняє сильнішим умовам, ніж це необхідно для сучасних методів.<ref name="PM" /> <!-- NONALGORITHM follows: The standard approach to handle this is to restart the algorithm with a new simplex starting at the current best value. This can be extended in a similar way to [[simulated annealing]] to escape small local minima. -->Сучасні поліпшення евристики Нелдера-Мід відомі з 1979 року.<ref name="YKL" />

Існує багато варіацій залежно від фактичної природи розв'язуваної задачі. Звичайний варіант використовує невеликий симплекс постійного розміру, який приблизно відповідає напрямку градієнта (який дає [[Градієнтний спуск|найшвидший спуск]]). Візуалізуйте маленький трикутник на карті висоти, що перевертається по долині до найнижчої точки на місцевості. Цей метод також відомий «як гнучкий метод багатогранника». Це, однак, має тенденцію до поганого виконання методу, описаного в цій статті(?), оскільки він робить невеликі, непотрібні кроки в областях, що представляють малий інтерес.

== Один з можливих варіантів алгоритму Нелдера-Міда ==
(Це близько до процедури, яка описана в оригінальній статті Нелдера-Міда.)
[[Файл:Rosenbrock function Nelder-Mead.gif|thumb|text-top|right|alt=Rosenbrock function Nelder-Mead| Метод Нелдера&nbsp;— Міда, застосований до [[Функція Розенброка|функції Розенброка]]]]

Ми намагаємося мінімізувати функцію <math>f(\mathbf x)</math>, де <math>\mathbf x \in \mathbb{R}^n</math>. Наші поточні контрольні точки є <math>\mathbf x_1, \ldots, \mathbf x_{n+1}</math>.

'''1. Порядок''' відповідно до значень у вершинах:
: <math>f(\mathbf x_1) \leq f(\mathbf x_2) \leq \cdots \leq f(\mathbf x_{n+1}).</math>

: Перевірте, чи слід зупинити метод. Дивіться [[#Завершення|'''Завершення''']] нижче. Іноді неправильно називають «збіжністю».

'''2.''' Розрахуйте <math>\mathbf x_o</math>, [[центроїд]] всіх точок, окрім <math>\mathbf x_{n+1}</math>.

'''3. Відбиття'''
: Обчислити симетрично віддзеркалену або, як будемо казати далі, ''відбиту'' точку <math>\mathbf x_r = \mathbf x_o + \alpha (\mathbf x_o - \mathbf x_{n+1})</math> з <math>\alpha > 0</math>.
: Якщо відбита краща, ніж друга найгірша, але не краща, ніж краща, тобто <math>f(\mathbf x_1) \leq f(\mathbf x_r) < f(\mathbf x_n)</math>,
:: тоді отримайте новий симплекс, замінивши найгіршу точку <math>\mathbf x_{n+1}</math> симетрично віддзеркаленою точкою <math>\mathbf x_r</math>, і перейдіть до кроку 1.

'''4.Розширення'''
: Якщо відбита точка є найкращою точкою досі, <math>f(\mathbf x_r) < f(\mathbf x_1)</math>,
:: потім обчислити розширену точку <math>\mathbf x_e = \mathbf x_o + \gamma (\mathbf x_r - \mathbf x_o)</math> з <math>\gamma > 1</math>.
:: Якщо розширена точка краще відбитої точки, <math>f(\mathbf x_e) < f(\mathbf x_r)</math>,
::: отримуємо новий симплекс, замінюючи найгіршу точку <math>\mathbf x_{n+1}</math> розширеною точкою <math>\mathbf x_e</math>, і перейдіть до кроку 1;
::: інакше отримуємо новий симплекс, замінюючи найгіршу точку <math>\mathbf x_{n+1}</math> відбитою точкою <math>\mathbf x_r</math> і перейдіть до кроку 1.

'''5. Скорочення'''
: Тут напевно <math>f(\mathbf x_{r}) \geq f(\mathbf x_n)</math>. (Зауважте що <math>\mathbf x_n</math> це друге чи «наступне» після найвищого.): Обчислити контрактну точку до <math>\mathbf x_c = \mathbf x_o + \rho(\mathbf x_{n+1} - \mathbf x_o)</math> з <math>0 < \rho \leq 0.5</math>.
: Якщо контрактна точка краща, ніж найгірша точка, тобто <math>f(\mathbf x_c) < f(\mathbf x_{n+1})</math>,
:: потім отримують новий симплекс шляхом заміни найгіршої точки <math>\mathbf x_{n+1}</math> на контрактну точку <math>\mathbf x_c</math> і переходять до кроку 1;

'''6. Стягування'''
: Замініть всі точки, крім кращих (<math>\mathbf x_1</math>) з
: <math>\mathbf x_i = \mathbf x_1 + \sigma(\mathbf x_i - \mathbf x_1)</math>,і перейдіть до кроку 1.

'''Примітка''': <math>\alpha</math>, <math>\gamma</math>, <math>\rho</math> і <math>\sigma</math> відповідно коефіцієнти відбиття, розширення, скорочення і стягування. Стандартними значеннями <math>\alpha = 1</math>, <math>\gamma = 2</math>, <math>\rho = 1/2</math> та <math>\sigma = 1/2</math>.

Для '''відбиття''', оскільки <math>\mathbf x_{n+1}</math> це вершина з вищою асоційованою величиною серед вершин, можливо буде менше значення при відбитті <math>\mathbf x_{n+1}</math> у бік протилежної сторони, утвореної всіма вершинами <math>\mathbf x_i</math>, крім <math>\mathbf x_{n+1}</math>.

Для '''розширення''', якщо точка відбиття <math>\mathbf x_r</math> i є новим мінімумом уздовж вершин, можна розраховувати знайти шукані значення вздовж напрямку від <math>\mathbf x_o</math> до <math>\mathbf x_r</math>.

Що стосується '''скорочення''', якщо <math>f(\mathbf x_r) > f(\mathbf x_n)</math>, то можна очікувати, що краще значення буде всередині симплекса, утвореного всіма вершинами <math>\mathbf x_i</math>.

Нарешті, '''стягування''' обробляє рідкісний випадок, коли скорочення від найбільшої точки збільшує <math>f</math>, що не може трапитись досить близько до несингулярного мінімуму. У цьому випадку ми скорочуємо у бік найнижчої точки в очікуванні знайти простіший ландшафт. Проте, Неш зазначає, що арифметика зі скінченною точністю іноді не може фактично стягнути симплекс, і виконати перевірку того, що розмір насправді зменшився.<ref name="CNM">{{Cite book | last1=Nash | first1=JC | year=1979 | title=Compact Numerical Methods: Linear Algebra and Function Minimisation | publisher=Adam Hilger |  location=Bristol | isbn=978-0-85274-330-0}}</ref>

== Початковий симплекс ==

Початковий симплекс важливий. Дійсно, занадто малий початковий симплекс може призвести до локальних пошуків, отже, метод може легше зупинитися. Отже, цей симплекс повинен залежати від природи задачі. А проте, оригінальна стаття запропонувала симплекс, де дається початкова точка <math>\mathbf x_{1}</math>, а інші генеруються з фіксованим кроком по кожному виміру по черзі. Таким чином, метод чутливий до масштабування змінних, які складають <math>\mathbf x</math>.

== Завершення ==

Для виходу з цього ітеративного циклу потрібні критерії. Нелдер і Мід використовували зразкове стандартне відхилення значень функцій поточного симплекса. Якщо вони опускаються нижче певних обмежень, то цикл зупиняється і найнижча точка в симплексі видається як запропонований оптимум. Зауважимо, що дуже «плоска» функція може мати майже однакові значення функцій над великим доменом, так що рішення буде чутливим до обмежень. Неш<ref name="CNM" /> додає тест на усадку як ще один критерій переривання роботи. Зауважте, що програми припиняються, тоді як ітерації можуть сходитися.

== Див. також ==
{{Div col|colwidth=20em}}
* [[Метод прямого пошуку]]
* {{Нп|COBYLA|COBYLA|en|COBYLA}}
* {{Нп|NEWUOA|NEWUOA|en|NEWUOA}}
* {{Нп|LINCOA|LINCOA|en|LINCOA}}
* {{Нп|Нелінійний сполучений градієнтний метод|Нелінійний сполучений градієнтний метод|en|Nonlinear conjugate gradient method}}
* [[Алгоритм Левенберга — Марквардта]]
* Бройден–Флетчер–Голдфарб-Шано або [[Алгоритм Бройдена — Флетчера — Гольдфарба — Шанно|BFGS метод]]
* [[Диференціальна еволюція]]
* [[Метод Гука — Дживса]]
* [[CMA-ES]]
{{Div col end}}

== Примітки ==
{{Reflist}}

== Література ==
* {{cite book |last=Avriel |first=Mordecai |year=2003 |title=Nonlinear Programming: Analysis and Methods |url=https://archive.org/details/nonlinearprogram0000avri_m5r2 |location= |publisher=Dover Publishing |isbn=978-0-486-43227-4 }}
* {{cite journal |last=Coope |first=I. D. |first2=C. J. |last2=Price |year=2002 |title=Positive Bases in Numerical Optimization |journal=Computational Optimization & Applications |volume=21 |issue=2 |pages=169–176 |doi=10.1023/A:1013760716801 }}
* {{cite book |first=Philip E. |last=Gill |first2=Walter |last2=Murray |first3=Margaret H. |last3=Wright |chapter=Methods for Multivariate Non-Smooth Functions |title=Practical Optimization |url=https://archive.org/details/practicaloptimiz00pgil |location=New York |publisher=Academic Press |year=1981 |isbn=978-0-12-283950-4 |pages=[https://archive.org/details/practicaloptimiz00pgil/page/n107 93]–96 }}
* {{cite book |last1=Kowalik |first=J. |last2=Osborne |first2=M. R. |title=Methods for Unconstrained Optimization Problems |location=New York |publisher=Elsevier |year=1968 |isbn=0-444-00041-0 |pages=[https://archive.org/details/methodsforuncons0000kowa/page/24 24–27] |url=https://archive.org/details/methodsforuncons0000kowa/page/24 }}
* {{cite book |first=W. H. |last=Swann |chapter=Direct Search Methods |title=Numerical Methods for Unconstrained Optimization |url=https://archive.org/details/numericalmethods0000wmur |editor-last=Murray |editor-first=W. |location=New York |publisher=Academic Press |year=1972 |pages=[https://archive.org/details/numericalmethods0000wmur/page/13 13]–28 |isbn=978-0-12-512250-4 }}

== Посилання ==
* [https://web.archive.org/web/20050424111513/http://www.boomer.org/c/p3/c11/c1106.html Nelder–Mead (Simplex) Method]
* [http://www.brnt.eu/phd/node10.html#SECTION00622200000000000000  Nelder–Mead (Downhill Simplex) explanation and visualization with the Rosenbrock banana function]
* [http://people.sc.fsu.edu/~burkardt/m_src/asa047/nelmin.m John Burkardt: Nelder–Mead code in Matlab]&nbsp;— note that a variation of the Nelder–Mead method is also implemented by the [[Matlab]] function fminsearch.
* [https://github.com/fchollet/nelder-mead nelder-mead]&nbsp;— A Python implementation of the Nelder–Mead method
* [http://people.fsv.cvut.cz/~svobodal/sova/  SOVA 1.0 (freeware)]&nbsp;— Simplex Optimization for Various Applications
* [http://www.hillstormer.es]&nbsp;— HillStormer, a practical tool for nonlinear, multivariate and linear constrained Simplex Optimization by Nelder Mead.
{{Методи оптимізації}}
[[Категорія:Алгоритми оптимізації]]
[[Категорія:Методи оптимізації]]