Metodo di Nelder-Mead

Il metodo Nelder-Mead, noto anche come metodo del simplesso (da non confondere con l'omonimo metodo di programmazione lineare) o metodo ameba, è un metodo di ottimizzazione non lineare di funzioni definite su un dominio a n dimensioni. È un metodo di ricerca euristica che può convergere a punti non stazionari^[1] nel caso di problemi risolubili con metodi alternativi.^[2] Il metodo prende il nome dai matematici John Nelder e Roger Mead, che l'hanno pubblicato nel 1965.^[3]

Considerazioni generali

Il metodo non fa uso delle derivate e si basa sul concetto di simplesso, un particolare tipo di politopo con n+1 vertici in uno spazio ad n dimensioni; esempi di simplesso sono un segmento in una retta, un triangolo nel piano, un tetraedro nello spazio etc. Il metodo approssima il punto di ottimo locale di un problema in n variabili quando la funzione obiettivo è liscia ed unimodale.

Il metodo genera una nuova posizione di test estrapolando il comportamento della funzione obiettivo valutata in ogni punto del dominio ai vertici di un simplesso. L'algoritmo quindi sceglie uno di questi punti, da rimpiazzare con un nuovo punto. Il passo più semplice è rimpiazzare il punto più lontano dall'ottimo con il centroide dei restanti n punti: se la valutazione nel nuovo punto è migliore rispetto al punto corrente, si continua la ricerca con andamento esponenziale nella direzione individuata dal punto, altrimenti si cerca in direzione di un punto che fornisca una valutazione migliore.

A differenza dei moderni metodi di ottimizzazione, il metodo di Nelder–Mead può convergere su punti non stazionari se il problema non soddisfa condizioni più forti.^[1] Il metodo è stato migliorato significativamente già dal 1979.^[2]

Esistono diverse varianti del metodo, a seconda della natura del problema da risolvere. Una tecnica comune prevede l'impiego di un piccolo simplesso di ampiezza costante che segue in maniera approssimativa la direzione del gradiente (che rappresenta la direzione di massima variazione della funzione).

Possibile formulazione del metodo Nelder-Mead

1. Ordinamento secondo il valore della funzione nei vertici del simplesso:

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

2. Calcolo del baricentro ${\textbf {x}}_{o}$ dei vertici escluso ${\textbf {x}}_{n+1}$ .
3. Riflessione

Si calcola il punto riflesso secondo

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

Se il punto riflesso è migliore del penultimo punto peggiore, ma non più valido del punto migliore, es.:

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

,

allora si determina un nuovo simplesso sostituendo il punto peggiore

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

con il punto riflesso

{\textbf {x}}_{r}

, e si torna al passo 1.

4. Espansione

Se il punto che è stato riflesso è il migliore, con

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

allora si calcola il punto espanso secondo

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

Se il punto espanso così trovato è migliore del punto riflesso, secondo

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

, allora si determina un nuovo simplesso sostituendo il punto peggiore

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

con il punto ottenuto nell'espansione

{\textbf {x}}_{e}

e si ritorna al passo 1.

Altrimenti si determina un nuovo simplesso sostituendo il punto peggiore

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

con il punto riflesso

{\textbf {x}}_{r}

, e si torna al passo 1.

Nel caso restante, quando ad esempio il punto ottenuto dalla riflessione non è migliore del penultimo punto peggiore, si avanza al passo 5.

5. Contrazione

Raggiunto questo punto si ha certamente

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

Si determina un punto di contrazione

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

Se il punto di contrazione è migliore del punto peggiore, es.

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

, allora si determina un nuovo simplesso sostituendo il punto peggiore

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

con il punto di contrazione

{\textbf {x}}_{c}

, e si torna al passo 1.

Altrimenti si avanza al passo 6.

6. Riduzione

Tutti i punti tranne il migliore vengono rimpiazzati con

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

quindi si torna al passo 1.

Nota: $\alpha$ , $\gamma$ , $\rho$ e $\sigma$ sono rispettivamente i coefficienti di riflessione, espansione, contrazione e riduzione. I valori più comunemente impiegati sono $\alpha =1$ , $\gamma =2$ , $\rho =-1/2$ e $\sigma =1/2$ .

Per la riflessione, essendo ${\textbf {x}}_{n+1}$ il vertice associato al maggior valore, ci si aspetta di trovare un valore più basso nella riflessione di ${\textbf {x}}_{n+1}$ nella faccia opposta formata da tutti i vertici ${\textbf {x}}_{i}$ escluso ${\textbf {x}}_{n+1}$ . Per l'espansione, se il punto riflesso ${\textbf {x}}_{r}$ è il nuovo minimo tra i vertici ci si aspetta di trovare valori interessanti nella direzione da ${\textbf {x}}_{o}$ verso ${\textbf {x}}_{r}$ . Per quanto riguarda la contrazione, se $f({\textbf {x}}_{r})>f({\textbf {x}}_{n})$ ci si aspetta un valore migliore dentro il simplesso formato dai vertici ${\textbf {x}}_{i}$ . Infine, la riduzione gestisce il raro caso nel quale la contrazione aumenta il valore di $f$ , cosa che non succede verosimilmente quando si è sufficientemente vicino ad un punto di minimo non singolare. La determinazione del simplesso iniziale è importante, in quanto un simplesso iniziale troppo piccolo può portare ad una ricerca locale, aumentando il rischio di insuccesso. Per tale motivo, il simplesso iniziale deve essere costruito accuratamente e facendo attenzione alla natura del problema.

Note

^ ^a ^b
- Michael J. D. Powell, On Search Directions for Minimization Algorithms, in Mathematical Programming, vol. 4, 1973, pp. 193–201, DOI:10.1007/bf01584660.
- K.I.M. McKinnon, Convergence of the Nelder–Mead simplex method to a non-stationary point, in SIAM J Optimization, vol. 9, 1999, pp. 148–158, DOI:10.1137/S1052623496303482. (algorithm summary online).
^ ^a ^b
- 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.
- Tamara G. Kolda, Lewis, Robert Michael; Torczon, Virginia, Optimization by direct search: new perspectives on some classical and modern methods, in SIAM Rev., vol. 45, 2003, pp. 385–482, DOI:10.1137/S003614450242889.
- Robert Michael Lewis, Shepherd, Anne; Torczon, Virginia, Implementing generating set search methods for linearly constrained minimization, in SIAM J. Sci. Comput., vol. 29, 2007, pp. 2507–2530, DOI:10.1137/050635432.
^ John A. Nelder, R. Mead, A simplex method for function minimization, in Computer Journal, vol. 7, 1965, pp. 308–313, DOI:10.1093/comjnl/7.4.308.

Bibliografia

Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0-486-43227-0.
Coope, I. D.; C.J. Price, 2002. “Positive bases in numerical optimization”, Computational Optimization & Applications, Vol. 21, No. 2, pp. 169–176, 2002.
WH Press, SA Teukolsky, WT Vetterling e BP Flannery, Section 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. URL consultato il 21 giugno 2014 (archiviato dall'url originale l'11 agosto 2011).

Altri progetti

Wikimedia Commons contiene immagini o altri file sul metodo di Nelder-Mead

Collegamenti esterni

(EN) Eric W. Weisstein, Nelder-Mead Method, su MathWorld, Wolfram Research.
(EN) Nelder–Mead (Simplex) Method, su boomer.org. URL consultato il 21 giugno 2014 (archiviato dall'url originale il 24 aprile 2005).
(EN) Nelder–Mead (Downhill Simplex): spiegazione ed esempi grafici con la funzione di Rosenbrock, su brnt.eu.
(EN) Nelder–Mead Search for a Minimum, su math.fullerton.edu.
(EN) John Burkardt: Nelder–Mead code in Matlab - una variante del metodo di Nelder–Mead è implementata nella funzione fminsearch di Matlab
(EN) Nelder–Mead online for the calibration of the SABR model - Applicazione alla finanza.
(EN) SOVA 1.0 (freeware), su people.fsv.cvut.cz. URL consultato il 21 giugno 2014 (archiviato dall'url originale il 6 giugno 2013).

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica

[PM-1] 
Michael J. D. Powell, On Search Directions for Minimization Algorithms, in Mathematical Programming, vol. 4, 1973, pp. 193–201, DOI:10.1007/bf01584660.

K.I.M. McKinnon, Convergence of the Nelder–Mead simplex method to a non-stationary point, in SIAM J Optimization, vol. 9, 1999, pp. 148–158, DOI:10.1137/S1052623496303482. (algorithm summary online).

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

[3] K.I.M. McKinnon, Convergence of the Nelder–Mead simplex method to a non-stationary point, in SIAM J Optimization, vol. 9, 1999, pp. 148–158, DOI:10.1137/S1052623496303482. (algorithm summary online).

[YKL-2] 
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.

Tamara G. Kolda, Lewis, Robert Michael; Torczon, Virginia, Optimization by direct search: new perspectives on some classical and modern methods, in SIAM Rev., vol. 45, 2003, pp. 385–482, DOI:10.1137/S003614450242889.

Robert Michael Lewis, Shepherd, Anne; Torczon, Virginia, Implementing generating set search methods for linearly constrained minimization, in SIAM J. Sci. Comput., vol. 29, 2007, pp. 2507–2530, DOI:10.1137/050635432.

[5] Yu, Wen Ci. 1979. “Positive basis and a class of direct search techniques”. Scientia Sinica [Zhongguo Kexue]: 53—68.

[6] Yu, Wen Ci. 1979. “The convergent property of the simplex evolutionary technique”. Scientia Sinica [Zhongguo Kexue]: 69–77.

[7] Tamara G. Kolda, Lewis, Robert Michael; Torczon, Virginia, Optimization by direct search: new perspectives on some classical and modern methods, in SIAM Rev., vol. 45, 2003, pp. 385–482, DOI:10.1137/S003614450242889.

[8] Robert Michael Lewis, Shepherd, Anne; Torczon, Virginia, Implementing generating set search methods for linearly constrained minimization, in SIAM J. Sci. Comput., vol. 29, 2007, pp. 2507–2530, DOI:10.1137/050635432.

[NM-3] John A. Nelder, R. Mead, A simplex method for function minimization, in Computer Journal, vol. 7, 1965, pp. 308–313, DOI:10.1093/comjnl/7.4.308.

[1]

[2]

[3]