Algoritme de Levenberg-Marquardt

En matemàtiques i computació, el algoritme de Levenberg-Marquardt (LMA o simplement LM), també conegut com el método de mínims quadrats amortiguados (DLS), s'utilisa per a resoldre problemes de mínims quadrats no llineals. Estos problemes de minimisació sorgixen especialment en l'ajust de curves de mínims quadrats.

El LMA s'usa en moltes aplicacions de software per a resoldre problemes genèrics d'ajust de curves. No obstant, com ocorre en molts algoritmes d'ajust, el LMA solament troba un mínim local, que no és necessàriament el mínim global. El LMA interpola entre l'algoritme de Gauss-Newton (GNA) i el método de descens de gradient. El LMA és més robust que el GNA, lo que significa que en molts casos troba una solució inclús si comença molt llunt del mínim final. Per a funcions de bon comportament i paràmetros d'inici raonables, el LMA tendix a ser una miqueta més llent que el GNA. El LMA també es pot vore com Gauss-Newton utilisant un enfocament de regió de confiança.

L'algoritme va ser publicat per primera volta en 1944 per Kenneth Levenberg, mentres treballava en l'Atarassana de l'Eixèrcit de Frankford. Va ser redescubierto en 1963 per Donald Marquardt, qui va treballar com estadístic en DuPont, i independentment per Girard Wynne i Morrison.

El problema

L'aplicació principal de l'algoritme de Levenberg-Marquardt es troba en el problema d'ajust de curves de mínims quadrats: donat un conjunt de $m$ parells de senyes empíriques ( x _i , i _i ) de variables independents i dependents, trobe els paràmetros β de la curva del modele f ( x , β ) de modo que la suma dels quadrats de les desviacions S ( β ) es minimise:

$\widehat{𝜷}\in \underset{𝜷}{\mathrm{argmin}}S(𝜷)\equiv \underset{𝜷}{\mathrm{argmin}}\sum _{i=1}^m[y_i-f(x_i,𝜷){]}^2,$ que se supon que no està buit.

La solució

De la mateixa manera que atres algoritmes de minimisació numèrica, l'algoritme de Levenberg-Marquardt és un procediment iterativo. Per a iniciar una minimisació, l'usuari deu proporcionar una estimació inicial del vector de paràmetros β. En els casos en solament un mínim, una conjectura estàndar no informada com β ^T = (1, 1, ..., 1) funcionarà be; en els casos en múltiples mínims, l'algoritme convergix al mínim global solament si l'estimació inicial ya és alguna cosa propenca a la solució final.

En cada pas de iteración, el vector paràmetro β es reemplaça per una nova estimació β + δ. Per a determinar δ , la funció $f(x_i,𝜷+𝜹)$s'aproxima per la seua linealización:

$f(x_i,𝜷+𝜹)\approx f(x_i,𝜷)+{𝐉}_i𝜹,$

a on

${𝐉}_i=\frac{\partial f(x_i,𝜷)}{\partial 𝜷}$

és el gradient (fila-vector en este cas) de f sobre β .

La suma $S(𝜷)$de desviacions quadrades té el seu mínim en un gradient de zero sobre β . L'anterior aproximació de primer orde de $f(x_i,𝜷+𝜹)$dona

$S(𝜷+𝜹)\approx \sum _{i=1}^m[y_i-f(x_i,𝜷)-{𝐉}_i𝜹{]}^2,$

o en notació vectorial,

$\begin{array}{cc}S(𝜷+𝜹)& \approx \Vert 𝐲-𝐟(𝜷)-𝐉𝜹{\Vert }^2\\ & =[𝐲-𝐟(𝜷)-𝐉𝜹{]}^{\mathrm{T}}[𝐲-𝐟(𝜷)-𝐉𝜹]\\ & =[𝐲-𝐟(𝜷){]}^{\mathrm{T}}[𝐲-𝐟(𝜷)]-[𝐲-𝐟(𝜷){]}^{\mathrm{T}}𝐉𝜹-(𝐉𝜹{)}^{\mathrm{T}}[𝐲-𝐟(𝜷)]+{𝜹}^{\mathrm{T}}{𝐉}^{\mathrm{T}}𝐉𝜹\\ & =[𝐲-𝐟(𝜷){]}^{\mathrm{T}}[𝐲-𝐟(𝜷)]-2[𝐲-𝐟(𝜷){]}^{\mathrm{T}}𝐉𝜹+{𝜹}^{\mathrm{T}}{𝐉}^{\mathrm{T}}𝐉𝜹.\end{array}$

Prenent la derivada de $S(𝜷+𝜹)$sobre δ i establir el resultat a zero dona

$({𝐉}^{\mathrm{T}}𝐉)𝜹={𝐉}^{\mathrm{T}}[𝐲-𝐟(𝜷)],$

a on $𝐉$ és la matriu jacobiana, la fila de la qual i és igual a ${𝐉}_i$, i a on $𝐟$i $𝐲$són vectores en i-component $f(x_i,𝜷)$i $y_i$respectivament. Est és un conjunt d'equacions llineals, que es poden resoldre para δ .

La contribució de Levenberg és reemplaçar esta equació per una "versió amortiguada":

$({𝐉}^{\mathrm{T}}𝐉+\lambda 𝐈)𝜹={𝐉}^{\mathrm{T}}[𝐲-𝐟(𝜷)],$

a on I és la matriu d'identitat, donant com a increment δ al vector de paràmetros estimat β.

El factor de amortiguamiento (no negatiu) λ s'ajusta en cada iteración. Si la reducció de S és ràpida, es pot usar un valor més menut, acostant l'algoritme a l'algoritme de Gauss-Newton, mentres que si una iteración produïx una reducció insuficient del residual, λ pot aumentar-se, donant un pas més prop del descens del gradient direcció. Tinga en conte que el gradient de S sobre β és igual a $-2({𝐉}^{\mathrm{T}}[𝐲-𝐟(𝜷)]{)}^{\mathrm{T}}$. Per lo tant, per a valors grans de λ, el pas es prendrà aproximadament en la direcció del gradient. Si la llongitut del pas calculat δ o la reducció de la suma de quadrats de l'últim vector de paràmetros β + δ cau per baix dels llímits predefinits, la iteración es deté, i l'últim vector de paràmetros β es considera la solució.

Si el valor del factor de amortiguamiento λ és gran en relació en la norma de J^TJ, no és necessari resoldre el sistema en matriu J^TJ + λI , ya que esta matriu es pot aproximar per mig de λI. En este cas l'algoritme realisa una actualisació en la direcció del gradient, en un pas menut: $\delta =\frac{1}{\lambda }{𝐉}^{\mathrm{T}}[𝐲-𝐟(𝜷)].$

R. Fletcher va proporcionar l'idea de que podem escalar cada component del gradient segons la curvatura, de modo que hi haja un moviment més gran a lo llarc de les direccions a on el gradient és més menut. Açò evita la convergència llenta en la direcció del gradient menut. Per lo tant, Fletcher en el seu artícul de 1971 "Una subrutina de Marquardt modificada per a mínims quadrats no llineals", va reemplaçar la matriu d'identitat I en la matriu diagonal que consistix en els elements diagonals de J^TJ, lo que fa que l'escala de la solució siga invariante:

$[{𝐉}^{\mathrm{T}}𝐉+\lambda \mathrm{diag}({𝐉}^{\mathrm{T}}𝐉)]𝜹={𝐉}^{\mathrm{T}}[𝐲-𝐟(𝜷)].$

Un factor de amortiguación similar apareix en la regularisació de Tikhonov, que s'utilisa per a resoldre problemes llineals mal plantejats, aixina com en la regressió de crestes, una tècnica d'estimació en estadística.

Elecció del paràmetro de amortiguación

S'han presentat varis arguments més o menys heurístics per a la millor opció per al paràmetro de amortiguación λ. Existixen arguments teòrics que mostren per qué algunes d'estes opcions garantisen la convergència local de l'algoritme; no obstant, estes eleccions poden fer que la convergència global de l'algoritme sofrixca de les propietats indesijables del descens més pronunciat, en particular, una convergència molt llenta prop de l'òptim.

Els valors absoluts de qualsevol elecció depenen de quina tan escalada estiga el problema inicial. Marquardt va recomanar començar en un valor λ ₀ i un factor ν>1. Configurant inicialment λ = λ₀ i calculant la suma residual de quadrats S (β) despuix d'un pas des del punt d'inici en el factor de amortiguamiento de λ = λ₀ i en segon lloc en λ₀/ν. Si abdós d'estos són pijors que el punt inicial, llavors la amortiguación s'incrementa per multiplicació successiva per ν fins que es troba un punt millor en un nou factor de amortiguación de λ₀ν^k per a alguns k .

Si l'us del factor de amortiguación λ / ν dona com resultat una reducció en el residu al quadrat, açò es pren com el nou valor de λ (i la nova ubicació òptima es pren com l'obtinguda en este factor de amortiguación) i el procés continua; si l'us de λ/ν va resultar en un pijor residu, pero l'us de λ va resultar en un millor residual, llavors λ es manté sense canvis i el nou òptim es pren com el valor obtingut en λ com a factor de amortiguamiento.

Vore també

• Regió de confiança
• Método Nelder – Pixeu (també conegut com simplex)
• Les variants de l'algoritme de Levenberg-Marquardt també s'han utilisat per a resoldre sistemes d'equacions no llineals.