Come funziona l'algoritmo Levenberg-Marquardt in dettaglio ma in modo comprensibile?

Question

Sono un programmatore che vuole imparare come funziona l'algoritmo di curvefitting di Levenberg-Marquardt in modo da poterlo implementare da solo.Esiste un buon tutorial da qualche parte che possa spiegare come funziona in dettaglio visto che il lettore è un programmatore e non un matemago.

Il mio obiettivo è implementare questo algoritmo in opencl in modo da poterlo eseguire con accelerazione hardware.

Answer 1

• http://en.wikipedia.org/wiki/Levenberg-Marquardt_algorithm
• PDF Tutorial da Ananth Ranganathan
• JavaNumerics dispone di un'implementazione abbastanza leggibile
• L'ICS ha un rel="noreferrer"> realizzazione

Answer 2

Minimizzare una funzione è come cercare di trovare punto più basso su una superficie. Pensa a te stesso camminare su una superficie collinare e che si sta cercando di arrivare al punto più basso. Si potrebbe trovare la direzione che va in discesa e camminare fino a quando non va più in discesa. Poi si sarebbe scelto una nuova direzione che va in discesa e camminare in quella direzione fino a quando non si scende più, e così via. Alla fine (si spera) si raggiunge un punto in cui nessuna direzione va più in discesa. Si potrebbe quindi essere ad un minimo (locale).

L'algoritmo LM, e molti altri algoritmi di minimizzazione, utilizzano questo schema.

Supponiamo che la funzione sia minimizzato è F e siamo al punto x (n) nella nostra iterazione. Vogliamo trovare il prossimo iterata x (n + 1) tale che F (x (n + 1))

In primo luogo, calcolare un'approssimazione lineare a F nel punto x (n). E 'facile trovare la direzione in discesa di una funzione lineare, in modo da utilizzare la funzione lineare approssima per determinare la direzione in discesa. Quindi, abbiamo bisogno di sapere quanto lontano possiamo andare in questa direzione scelta. Se la nostra funzione lineare approssimazione è una buona approssimazione per F per una vasta area intorno x (n), allora possiamo prendere un gran passo. Se si tratta di una buona approssimazione solo molto vicino a x (n), allora possiamo prendere solo un piccolo passo.

Questo è ciò che fa LM - calcola un'approssimazione lineare a F a x (n), dando così la direzione in discesa, allora capisce come grande un passo da compiere basata su come la funzione lineare approssima F a x (n ). LM capisce come buona approssimazione la funzione è fondamentalmente da un passo nella direzione così determinato e confrontando quanto l'approssimazione lineare a F diminuita al quanto la funzione effettiva F diminuito. Se sono vicini, la funzione di approssimazione è buona e possiamo fare un piccolo passo più grande. Se non sono vicini, allora la funzione di approssimazione non è buona e dovremmo fare marcia indietro e fare un passo più piccolo.

Answer 3

Le idee di base dell'algoritmo LM possono essere spiegate in poche pagine, ma per un'implementazione di livello produttivo che sia veloce e robusta, sono necessarie molte sottili ottimizzazioni.Lo stato dell'arte è ancora l'implementazione di Minpack da parte di Moré et al., documentata in dettaglio da Moré 1978 (http://link.springer.com/content/pdf/10.1007/BFb0067700.pdf) e nella guida per l'utente di Minpack (http://www.mcs.anl.gov/~more/ANL8074b.pdf).Per studiare il codice, la mia traduzione in C (https://jugit.fz-juelich.de/mlz/lmfit) è probabilmente più accessibile del codice Fortran originale.

Answer 4

numerica Ricette (Levenberg-Marquardt è nella Sezione 15.5). E 'disponibile on-line, e trovo che spiegano gli algoritmi in un modo che è dettagliato (che hanno il codice sorgente completo, quanto più dettagliata è possibile ottenere ...), ma accessibile.

Answer 5

queste note da un corso a Purdue University per codificare un generico Levenberg-Marquardt algoritmo a curva-montaggio in MATLAB che calcola derivate numeriche e accetta quindi ogni funzione della forma f(x;p) dove p è un vettore di parametri di adattamento.