Levenberg-Marquardt

Nelle sezioni precedenti sono stati introdotti due approcci fondamentali per l'ottimizzazione non lineare: la discesa del gradiente e il metodo di Gauss-Newton. Per una trattazione più approfondita si rimanda a (MBT04).

Il metodo di Gauss-Newton sfrutta una linearizzazione locale del problema e, in prossimità della soluzione, presenta generalmente una convergenza molto rapida. Tuttavia la matrice $\mathbf{J}_r^\top \mathbf{J}_r$ può risultare mal condizionata o quasi singolare, causando instabilità numeriche e passi di aggiornamento eccessivamente aggressivi.

L'algoritmo di Levenberg-Marquardt (LM) introduce un termine di regolarizzazione che combina le proprietà di robustezza della discesa del gradiente con la rapidità di convergenza di Gauss-Newton. Per questo motivo rappresenta uno dei metodi più utilizzati nella risoluzione di problemi non lineari ai minimi quadrati. Una trattazione dettagliata dell'algoritmo è disponibile in (Lou05).

Partendo dal sistema di Gauss-Newton

$$\mathbf{J}_r^\top \mathbf{J}_r \, \boldsymbol\delta_\beta = -\mathbf{J}_r^\top \mathbf r,$$ (4.61)

LM introduce un parametro di attenuazione (damping factor) $\mu > 0$ ottenendo il sistema

$$\left( \mathbf{J}_r^\top \mathbf{J}_r + \mu \mathbf I \right) \boldsymbol\delta_\beta = -\mathbf{J}_r^\top \mathbf r .$$ (4.62)

La matrice

$$\mathbf N = \mathbf{J}_r^\top \mathbf{J}_r + \mu \mathbf I$$

risulta definita positiva per $\mu > 0$ e può quindi essere invertita in modo stabile anche in presenza di problemi mal condizionati.

Quando $\mu$ assume valori elevati, il contributo della diagonale domina la matrice del sistema e l'aggiornamento tende ad assumere il comportamento di una discesa del gradiente.

Al contrario, per $\mu \rightarrow 0$, l'equazione (4.62) si riduce al passo di Gauss-Newton.

A differenza delle tecniche di line search, il metodo LM può essere interpretato come una tecnica di trust region: il parametro $\mu$ controlla implicitamente quanto ci si possa allontanare dal punto corrente prima che la linearizzazione locale perda validità.

Come per il metodo di Gauss-Newton, l'algoritmo sfrutta l'approssimazione

$$\mathbf H_S(\boldsymbol\beta) \approx \mathbf J_r^\top \mathbf J_r$$ (4.63)

che risulta accurata quando i residui sono piccoli oppure quando il modello è localmente quasi lineare.

La scelta iniziale e l'aggiornamento del parametro $\mu$ sono lasciati al risolutore e diverse strategie sono proposte in letteratura. Una delle strategie maggiormente utilizzate (Nie99) inizializza il parametro come

$$\mu_0 = \tau \max_i H_{ii}$$ (4.64)

dove $H_{ii}$ sono gli elementi diagonali della matrice $\mathbf H \approx \mathbf J_r^\top \mathbf J_r$ e $\tau$ è una costante positiva scelta dall'utente.

La qualità dell'aggiornamento viene valutata mediante il gain ratio

$$\rho = \frac{ S(\boldsymbol\beta) - S(\boldsymbol\beta+\boldsymbol\delta_\beta) } { L(\mathbf 0)-L(\boldsymbol\delta_\beta) }$$ (4.65)

dove il numeratore rappresenta la riduzione effettivamente osservata della funzione costo e il denominatore la riduzione prevista dal modello quadratico locale.

Un valore elevato di $\rho$ indica che la linearizzazione locale approssima correttamente il comportamento della funzione costo e che il passo proposto può essere accettato riducendo il valore di $\mu$.

Viceversa, valori piccoli o negativi di $\rho$ indicano che il modello locale non descrive adeguatamente il problema e che il parametro $\mu$ deve essere aumentato, rendendo il metodo più conservativo e più simile a una discesa del gradiente.

Una possibile strategia di aggiornamento è

che costituisce una delle scelte comunemente adottate nelle implementazioni moderne dell'algoritmo.