Metoda Nelder-Mead

Metoda Nelder-Mead , cunoscută și sub numele de metoda simplex (nu trebuie confundată cu metoda omonimă de programare liniară ) sau metoda amoeba , este o metodă de optimizare neliniară a funcțiilor definite pe un domeniu n- dimensional. Este o metodă euristică de căutare care poate converge către puncte nestacionare ^[1] în cazul problemelor care pot fi rezolvate cu metode alternative. ^[2] Metoda poartă numele matematicienilor John Nelder și Roger Mead, care au publicat-o în 1965. ^[3]

Considerent general

Aplicarea metodei Nelder-Mead la funcția Rosenbrock .

Aplicarea metodei Nelder-Mead la funcția Himmelblau .

Metoda nu folosește derivate și se bazează pe conceptul de simplex , un anumit tip de politop cu n + 1 vârfuri într-un spațiu n-dimensional; exemple de simplex sunt un segment într-o linie, un triunghi în plan, un tetraedru în spațiu etc. Metoda aproximează optimul local al unei probleme în n variabile atunci când funcția obiectivă este netedă și unimodală.

Metoda generează o nouă poziție de test prin extrapolarea comportamentului funcției obiective evaluate în fiecare punct al domeniului la vârfurile unui simplex. Algoritmul alege apoi unul dintre aceste puncte, pentru a fi înlocuit cu un punct nou. Cel mai simplu pas este înlocuirea punctului cel mai îndepărtat de optim cu centroidul celor n puncte rămase: dacă evaluarea în noul punct este mai bună decât punctul curent, căutarea se continuă cu tendința exponențială în direcția identificată de punct, în caz contrar, este căutat în direcția unui punct care oferă o evaluare mai bună.

Spre deosebire de metodele moderne de optimizare, metoda Nelder - Mead poate converge pe puncte nestacionare dacă problema nu satisface condiții mai puternice. ^[1] Metoda a fost îmbunătățită semnificativ din 1979. ^[2]

Există mai multe variante ale metodei, în funcție de natura problemei de rezolvat. O tehnică comună implică utilizarea unui mic simplex de amplitudine constantă care urmează aproximativ direcția gradientului (care reprezintă direcția de variație maximă a funcției).

Formularea posibilă a metodei Nelder-Mead

1. Sortarea în funcție de valoarea funcției în vârfurile simplexului:

f({\textbf {x}}_{1})\leq f({\textbf {x}}_{2})\leq \cdots \leq f({\textbf {x}}_{n+1})

{\ displaystyle f ({\ textbf {x}} _ {1}) \ leq f ({\ textbf {x}} _ {2}) \ leq \ cdots \ leq f ({\ textbf {x}} _ { n + 1})}

f ({\ textbf {x}} _ {{1}}) \ leq f ({\ textbf {x}} _ {{2}}) \ leq \ cdots \ leq f ({\ textbf {x}} _ {{n + 1}})

2. Calculul centrului de greutate ${\textbf {x}}_{o}$ ${\ displaystyle {\ textbf {x}} _ {o}}$ ${\ textbf {x}} _ {{o}}$ a vârfurilor excluse ${\textbf {x}}_{n+1}$ ${\ displaystyle {\ textbf {x}} _ {n + 1}}$ ${\ textbf {x}} _ {{n + 1}}$ .
3. Reflecție

Se calculează al doilea punct reflex

{\textbf {x}}_{r}={\textbf {x}}_{o}+\alpha ({\textbf {x}}_{o}-{\textbf {x}}_{n+1})

{\ displaystyle {\ textbf {x}} _ {r} = {\ textbf {x}} _ {o} + \ alpha ({\ textbf {x}} _ {o} - {\ textbf {x}} _ {n + 1})}

{\ textbf {x}} _ {r} = {\ textbf {x}} _ {o} + \ alpha ({\ textbf {x}} _ {o} - {\ textbf {x}} _ {{n +1}})

Dacă punctul reflex este mai bun decât penultimul cel mai rău punct, dar nu mai valabil decât cel mai bun punct, de exemplu:

f({\textbf {x}}_{1})\leq f({\textbf {x}}_{r})<f({\textbf {x}}_{n})

{\ displaystyle f ({\ textbf {x}} _ {1}) \ leq f ({\ textbf {x}} _ {r}) <f ({\ textbf {x}} _ {n})}

f ({\ textbf {x}} _ {{1}}) \ leq f ({\ textbf {x}} _ {{r}}) <f ({\ textbf {x}} _ {{n}} )

,

atunci se determină un nou simplex prin înlocuirea celui mai rău punct

{\textbf {x}}_{n+1}

{\ displaystyle {\ textbf {x}} _ {n + 1}}

{\ textbf {x}} _ {{n + 1}}

cu punctul reflex

{\textbf {x}}_{r}

{\ displaystyle {\ textbf {x}} _ {r}}

{\ textbf {x}} _ {{r}}

, și reveniți la pasul 1.

4. Extindere

Dacă punctul care a fost reflectat este cel mai bun, con

f({\textbf {x}}_{r})<f({\textbf {x}}_{1}),

{\ displaystyle f ({\ textbf {x}} _ {r}) <f ({\ textbf {x}} _ {1}),}

f ({\ textbf {x}} _ {{r}}) <f ({\ textbf {x}} _ {{1}}),

atunci se calculează al doilea punct extins

{\textbf {x}}_{e}={\textbf {x}}_{o}+\gamma ({\textbf {x}}_{r}-{\textbf {x}}_{o})

{\ displaystyle {\ textbf {x}} _ {e} = {\ textbf {x}} _ {o} + \ gamma ({\ textbf {x}} _ {r} - {\ textbf {x}} _ {sau})}

{\ displaystyle {\ textbf {x}} _ {e} = {\ textbf {x}} _ {o} + \ gamma ({\ textbf {x}} _ {r} - {\ textbf {x}} _ {sau})}

Dacă punctul extins astfel găsit este mai bun decât punctul reflectat, al doilea

f({\textbf {x}}_{e})<f({\textbf {x}}_{r})

{\ displaystyle f ({\ textbf {x}} _ {e}) <f ({\ textbf {x}} _ {r})}

f ({\ textbf {x}} _ {{e}}) <f ({\ textbf {x}} _ {{r}})

, atunci un nou simplex este determinat prin înlocuirea celui mai rău punct

{\textbf {x}}_{n+1}

{\ displaystyle {\ textbf {x}} _ {n + 1}}

{\ textbf {x}} _ {{n + 1}}

cu punctul obținut în expansiune

{\textbf {x}}_{e}

{\ displaystyle {\ textbf {x}} _ {e}}

{\ textbf {x}} _ {{e}}

și reveniți la pasul 1.

În caz contrar, un nou simplex este determinat prin înlocuirea celui mai rău punct

{\textbf {x}}_{n+1}

{\ displaystyle {\ textbf {x}} _ {n + 1}}

{\ textbf {x}} _ {{n + 1}}

cu punctul reflex

{\textbf {x}}_{r}

{\ displaystyle {\ textbf {x}} _ {r}}

{\ textbf {x}} _ {{r}}

, și reveniți la pasul 1.

În cazul rămas, când, de exemplu, punctul obținut din reflexie nu este mai bun decât penultimul punct cel mai rău, treceți la pasul 5.

5. Contracția

Cu siguranță am ajuns la acest punct

f({\textbf {x}}_{r})\geq f({\textbf {x}}_{n})

{\ displaystyle f ({\ textbf {x}} _ {r}) \ geq f ({\ textbf {x}} _ {n})}

f ({\ textbf {x}} _ {{r}}) \ geq f ({\ textbf {x}} _ {{n}})

Se determină un punct de contracție

{\textbf {x}}_{c}={\textbf {x}}_{o}+\rho ({\textbf {x}}_{o}-{\textbf {x}}_{n+1})

{\ displaystyle {\ textbf {x}} _ {c} = {\ textbf {x}} _ {o} + \ rho ({\ textbf {x}} _ {o} - {\ textbf {x}} _ {n + 1})}

{\ textbf {x}} _ {{c}} = {\ textbf {x}} _ {o} + \ rho ({\ textbf {x}} _ {{o}} - {\ textbf {x}} _ {{n + 1}})

Dacă punctul de contracție este mai bun decât cel mai rău punct, de ex.

f({\textbf {x}}_{c})<f({\textbf {x}}_{n+1})

{\ displaystyle f ({\ textbf {x}} _ {c}) <f ({\ textbf {x}} _ {n + 1})}

f ({\ textbf {x}} _ {{c}}) <f ({\ textbf {x}} _ {{n + 1}})

, atunci un nou simplex este determinat prin înlocuirea celui mai rău punct

{\textbf {x}}_{n+1}

{\ displaystyle {\ textbf {x}} _ {n + 1}}

{\ textbf {x}} _ {{n + 1}}

cu punctul de contracție

{\textbf {x}}_{c}

{\ displaystyle {\ textbf {x}} _ {c}}

{\ textbf {x}} _ {{c}}

, și reveniți la pasul 1.

În caz contrar, continuați cu pasul 6.

6. Reducere

Toate punctele, cu excepția celor mai bune, sunt înlocuite cu

{\textbf {x}}_{i}={\textbf {x}}_{1}+\sigma ({\textbf {x}}_{i}-{\textbf {x}}_{1})\;\forall i\in \{2,\dots ,n+1\}

{\ displaystyle {\ textbf {x}} _ {i} = {\ textbf {x}} _ {1} + \ sigma ({\ textbf {x}} _ {i} - {\ textbf {x}} _ {1}) \; \ forall i \ in \ {2, \ dots, n + 1 \}}

{\ textbf {x}} _ {{i}} = {\ textbf {x}} _ {{1}} + \ sigma ({\ textbf {x}} _ {{i}} - {\ textbf {x }} _ {{1}}) \; \ forall i \ in \ {2, \ dots, n + 1 \}

apoi reveniți la pasul 1.

Notă : $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$ , $\gamma$ ${\ displaystyle \ gamma}$ $\gamă$ , $\rho$ ${\ displaystyle \ rho}$ $\ rho$ Și $\sigma$ ${\ displaystyle \ sigma}$ $\ sigma$ sunt respectiv coeficienții de reflexie, expansiune, contracție și reducere. Valorile cele mai des utilizate sunt $\alpha =1$ ${\ displaystyle \ alpha = 1}$ $\ alfa = 1$ , $\gamma =2$ ${\ displaystyle \ gamma = 2}$ $\ gamma = 2$ , $\rho =-1/2$ ${\ displaystyle \ rho = -1 / 2}$ $\ rho = -1 / 2$ Și $\sigma =1/2$ ${\ displaystyle \ sigma = 1/2}$ $\ sigma = 1/2$ .

Pentru reflecție, a fi ${\textbf {x}}_{n+1}$ ${\ displaystyle {\ textbf {x}} _ {n + 1}}$ ${\ textbf {x}} _ {{n + 1}}$ vârful asociat cu valoarea mai mare, ne așteptăm să găsim o valoare mai mică în reflectarea lui ${\textbf {x}}_{n+1}$ ${\ displaystyle {\ textbf {x}} _ {n + 1}}$ ${\ textbf {x}} _ {{n + 1}}$ în fața opusă formată din toate vârfurile ${\textbf {x}}_{i}$ ${\ displaystyle {\ textbf {x}} _ {i}}$ ${\ textbf {x}} _ {{i}}$ excluzând ${\textbf {x}}_{n+1}$ ${\ displaystyle {\ textbf {x}} _ {n + 1}}$ ${\ textbf {x}} _ {{n + 1}}$ . Pentru expansiune, dacă punctul reflex ${\textbf {x}}_{r}$ ${\ displaystyle {\ textbf {x}} _ {r}}$ ${\ textbf {x}} _ {{r}}$ este noul minim dintre vârfurile din care ne așteptăm să găsim valori interesante în direcția de la ${\textbf {x}}_{o}$ ${\ displaystyle {\ textbf {x}} _ {o}}$ ${\ textbf {x}} _ {{o}}$ la ${\textbf {x}}_{r}$ ${\ displaystyle {\ textbf {x}} _ {r}}$ ${\ textbf {x}} _ {{r}}$ . În ceea ce privește contracția, dacă $f({\textbf {x}}_{r})>f({\textbf {x}}_{n})$ ${\ displaystyle f ({\ textbf {x}} _ {r})> f ({\ textbf {x}} _ {n})}$ $f ({\ textbf {x}} _ {{r}})> f ({\ textbf {x}} _ {{n}})$ se așteaptă o valoare mai bună în cadrul simplexului format de vârfuri ${\textbf {x}}_{i}$ ${\ displaystyle {\ textbf {x}} _ {i}}$ ${\ textbf {x}} _ {{i}}$ . În cele din urmă, reducerea tratează cazul rar în care contracția crește valoarea $f$ ${\ displaystyle f}$ $f$ , ceea ce nu este probabil să se întâmple atunci când cineva este suficient de aproape de un punct minim non-singular. Determinarea simplexului inițial este importantă, deoarece un simplex inițial prea mic poate duce la o căutare locală, crescând riscul de eșec. Din acest motiv, simplexul inițial trebuie construit cu atenție și acordând atenție naturii problemei.

Notă

^ ^a ^b
- Michael JD Powell , On Search Directions for Minimization Algorithms , în Mathematical Programming , vol. 4, 1973, pp. 193–201, DOI : 10.1007 / bf01584660 .
- KIM McKinnon, Convergența metodei Nelder - Mead simplex la un punct nestacionar , în SIAM J Optimization , vol. 9, 1999, pp. 148–158, DOI : 10.1137 / S1052623496303482 . (rezumat algoritm online).
^ ^a ^b
- Yu, Wen Ci. 1979. „Baza pozitivă și o clasă de tehnici de căutare directă”. Scientia Sinica [ Zhongguo Kexue ]: 53—68.
- Yu, Wen Ci. 1979. „Proprietatea convergentă a tehnicii evolutive simplex”. Scientia Sinica [ Zhongguo Kexue ]: 69–77.
- Tamara G. Kolda, Lewis, Robert Michael; Torczon, Virginia, Optimizarea prin căutare directă: noi perspective asupra unor metode clasice și moderne , în SIAM Rev. , vol. 45, 2003, pp. 385–482, DOI : 10.1137 / S003614450242889 .
- Robert Michael Lewis, Shepherd, Anne; Torczon, Virginia, Implementarea metodelor de căutare a setului de generare pentru minimizarea constrânsită liniar , în SIAM J. Sci. Comput. , vol. 29, 2007, pp. 2507-2530, DOI : 10.1137 / 050635432 .
^ John A. Nelder, R. Mead, O metodă simplex pentru minimizarea funcției , în Computer Journal , vol. 7, 1965, pp. 308-313, DOI : 10.1093 / comjnl / 7.4.308 .

Bibliografie

Avriel, Mordecai (2003). Programare neliniară: analiză și metode. Editura Dover. ISBN 0-486-43227-0 .
Coope, ID; CJ Price, 2002. „Bazele pozitive în optimizarea numerică”, Computational Optimization & Applications , Vol. 21, No. 2, pp. 169–176, 2002.
WH Press, SA Teukolsky, WT Vetterling și BP Flannery, secțiunea 10.5. Downhill Simplex Method in Multidimensions , in Numerical Recipes: The Art of Scientific Computing , 3rd, New York, Cambridge University Press, 2007, ISBN 978-0-521-88068-8 .

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere despre metoda Nelder-Mead

linkuri externe

(EN) Metoda Nelder-Mead (Simplex) , a boomer.org. Adus la 21 iunie 2014 (arhivat din original la 24 aprilie 2005) .
( EN ) Nelder - Mead (Downhill Simplex): Explicație și exemple grafice cu funcția Rosenbrock , pe brnt.eu.
(EN) Nelder-Mead Search for a Minimum , pe math.fullerton.edu.
(EN) John Burkardt: cod Nelder-Mead în Matlab - o variantă a metodei Nelder-Mead este implementată în funcția fminsearch Matlab
(EN) Nelder-Mead online pentru calibrarea modelului SABR - Cerere de finanțare.
( EN ) SOVA 1.0 (freeware) , pe people.fsv.cvut.cz .

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[PM-1] 
Michael JD Powell , On Search Directions for Minimization Algorithms , în Mathematical Programming , vol. 4, 1973, pp. 193–201, DOI : 10.1007 / bf01584660 .
KIM McKinnon, Convergența metodei Nelder - Mead simplex la un punct nestacionar , în SIAM J Optimization , vol. 9, 1999, pp. 148–158, DOI : 10.1137 / S1052623496303482 . (rezumat algoritm online).

[2] Michael JD Powell , On Search Directions for Minimization Algorithms , în Mathematical Programming , vol. 4, 1973, pp. 193–201, DOI : 10.1007 / bf01584660 .

[3] KIM McKinnon, Convergența metodei Nelder - Mead simplex la un punct nestacionar , în SIAM J Optimization , vol. 9, 1999, pp. 148–158, DOI : 10.1137 / S1052623496303482 . (rezumat algoritm online).

[YKL-2] 
Yu, Wen Ci. 1979. „Baza pozitivă și o clasă de tehnici de căutare directă”. Scientia Sinica [ Zhongguo Kexue ]: 53—68.
Yu, Wen Ci. 1979. „Proprietatea convergentă a tehnicii evolutive simplex”. Scientia Sinica [ Zhongguo Kexue ]: 69–77.
Tamara G. Kolda, Lewis, Robert Michael; Torczon, Virginia, Optimizarea prin căutare directă: noi perspective asupra unor metode clasice și moderne , în SIAM Rev. , vol. 45, 2003, pp. 385–482, DOI : 10.1137 / S003614450242889 .
Robert Michael Lewis, Shepherd, Anne; Torczon, Virginia, Implementarea metodelor de căutare a setului de generare pentru minimizarea constrânsită liniar , în SIAM J. Sci. Comput. , vol. 29, 2007, pp. 2507-2530, DOI : 10.1137 / 050635432 .

[5] Yu, Wen Ci. 1979. „Baza pozitivă și o clasă de tehnici de căutare directă”. Scientia Sinica [ Zhongguo Kexue ]: 53—68.

[6] Yu, Wen Ci. 1979. „Proprietatea convergentă a tehnicii evolutive simplex”. Scientia Sinica [ Zhongguo Kexue ]: 69–77.

[7] Tamara G. Kolda, Lewis, Robert Michael; Torczon, Virginia, Optimizarea prin căutare directă: noi perspective asupra unor metode clasice și moderne , în SIAM Rev. , vol. 45, 2003, pp. 385–482, DOI : 10.1137 / S003614450242889 .

[8] Robert Michael Lewis, Shepherd, Anne; Torczon, Virginia, Implementarea metodelor de căutare a setului de generare pentru minimizarea constrânsită liniar , în SIAM J. Sci. Comput. , vol. 29, 2007, pp. 2507-2530, DOI : 10.1137 / 050635432 .

[NM-3] John A. Nelder, R. Mead, O metodă simplex pentru minimizarea funcției , în Computer Journal , vol. 7, 1965, pp. 308-313, DOI : 10.1093 / comjnl / 7.4.308 .

[1]

[2]

[3]