Metodo di Nelder-Mead

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca

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[modifica | modifica wikitesto]

Applicazione del metodo di Nelder-Mead alla funzione di Rosenbrock.
Applicazione del metodo di Nelder-Mead alla funzione di Himmelblau.

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[modifica | modifica wikitesto]

  • 1. Ordinamento secondo il valore della funzione nei vertici del simplesso:
  • 2. Calcolo del baricentro dei vertici escluso .
  • 3. Riflessione
Si calcola il punto riflesso secondo
Se il punto riflesso è migliore del penultimo punto peggiore, ma non più valido del punto migliore, es.: ,
allora si determina un nuovo simplesso sostituendo il punto peggiore con il punto riflesso , e si torna al passo 1.
  • 4. Espansione
Se il punto che è stato riflesso è il migliore, con allora si calcola il punto espanso secondo
Se il punto espanso così trovato è migliore del punto riflesso, secondo , allora si determina un nuovo simplesso sostituendo il punto peggiore con il punto ottenuto nell'espansione e si ritorna al passo 1.
Altrimenti si determina un nuovo simplesso sostituendo il punto peggiore con il punto riflesso , 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
Si determina un punto di contrazione
Se il punto di contrazione è migliore del punto peggiore, es. , allora si determina un nuovo simplesso sostituendo il punto peggiore con il punto di contrazione , e si torna al passo 1.
Altrimenti si avanza al passo 6.
  • 6. Riduzione
Tutti i punti tranne il migliore vengono rimpiazzati con
quindi si torna al passo 1.

Nota: , , e sono rispettivamente i coefficienti di riflessione, espansione, contrazione e riduzione. I valori più comunemente impiegati sono , , e .

Per la riflessione, essendo il vertice associato al maggior valore, ci si aspetta di trovare un valore più basso nella riflessione di nella faccia opposta formata da tutti i vertici escluso . Per l'espansione, se il punto riflesso è il nuovo minimo tra i vertici ci si aspetta di trovare valori interessanti nella direzione da verso . Per quanto riguarda la contrazione, se ci si aspetta un valore migliore dentro il simplesso formato dai vertici . Infine, la riduzione gestisce il raro caso nel quale la contrazione aumenta il valore di , 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[modifica | modifica wikitesto]

  1. ^ a b
  2. ^ a b
  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.

Bibliografia[modifica | modifica wikitesto]

  • 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[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

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