Algoritmo de Levenberg-Marquardt

O algoritmo de Levenberg-Marquardt , ou algoritmo LM , permite obter uma solução numérica para o problema de minimização de uma função , muitas vezes não linear e dependente de várias variáveis . O algoritmo é baseado nos métodos por trás do algoritmo de Gauss-Newton e do algoritmo de gradiente . Mais estável do que o de Gauss-Newton, ele encontra uma solução mesmo que seja iniciado muito longe do mínimo. No entanto, para algumas funções muito regulares, pode convergir um pouco menos rapidamente. O algoritmo foi desenvolvido por Kenneth Levenberg , então publicado por Donald Marquardt .

Este é um problema que freqüentemente surge na regressão linear e não linear .

Aplicação ao método dos mínimos quadrados

Estados

Sua principal aplicação é a regressão através do método dos mínimos quadrados: dado um certo número de pares de dados $( t i , y i )$ , procuramos o parâmetro $a$ da função $f ( t | a )$ para que a soma dos quadrados do desvios:

S ({\ boldsymbol a}) = \ sum _ {{i = 1}} ^ {m} [y_ {i} -f (t_ {i} | {\ boldsymbol a})] ^ {2} \,

é mínimo.

Solução

O procedimento do algoritmo é iterativo . Partimos de um parâmetro inicial, que supomos estar “suficientemente próximo” de um mínimo, e que constituirá o vetor inicial $p$ . Em muitos casos, um parâmetro inicial “padrão”, como $p T = (1,1,\dots, 1)$ funcionará sem problemas. Em certos casos, há convergência apenas se o vetor inicial não estiver muito longe da solução.

A cada iteração, substituímos $p$ por uma nova estimativa $p + q$ . Para determinar $q$ , as funções $f i ( p + q )$ são aproximadas por serem linearizadas:

{\ displaystyle f (\ mathbf {p} + \ mathbf {q}) \ approx f (\ mathbf {p}) + \ mathbf {Jq},}

onde notamos $J$ o Jacobiano de $f$ na $p$ .

No mínimo da soma dos quadrados $S$ , temos $\nabla q S = 0$ . Derivando o quadrado da expressão à direita, que portanto desaparece, e definindo $y = f ( p + q )$ , obtemos:

{\ displaystyle (\ mathbf {J} ^ {T} \ mathbf {J}) \ mathbf {q} \ approx \ mathbf {J} ^ {T} (\ mathbf {y} -f (\ mathbf {p}) ),}

onde você puxa facilmente $q$ reverter $J T J$ .

Na inversão da matriz, tudo dependerá da razão entre o maior autovalor em norma e o menor autovalor; esta razão, chamada de condicionamento de matriz , refletirá concretamente a robustez do algoritmo diante do ruído.

O ponto essencial do algoritmo de Levenberg-Marquardt é abordar essa equação, “amortecendo-a” um pouco. Fala-se então de “carregamento da diagonal” para contornar se necessário o mau condicionamento, problema que se encontra com o algoritmo de Capon e que se pode resolver por decomposição em valores singulares :

{\ displaystyle \ left (\ mathbf {J} ^ {T} \ mathbf {J} + \ lambda \, {\ textrm {diag}} (\ mathbf {J} ^ {T} \ mathbf {J}) \ right ) \ mathbf {q} \ aprox \ mathbf {J} ^ {T} (\ mathbf {y} -f (\ mathbf {p})),}

O fator de amortecimento positivo λ é ajustado a cada nova iteração. Se a diminuição em $S$ for rápida, podemos usar um valor menor - o que aproxima o algoritmo do de Gauss-Newton. Se, por outro lado, uma iteração não for muito eficiente, podemos aumentar λ, o que desta vez aproxima o algoritmo do gradiente . Esse fator de amortecimento é usado, por exemplo, na regularização de Tikhonov , usado para resolver certos problemas lineares.

Se mais de um certo número de iterações foram realizadas, ou se uma se aproximou de um mínimo suficientemente, o procedimento termina e retorna o parâmetro $p$ como uma estimativa da solução.

Escolha do parâmetro de amortecimento

Muitos argumentos, mais ou menos heurísticos, têm sido propostos para determinar o melhor fator de amortecimento $λ$ . As provas teóricas mostram que certas escolhas garantem a convergência local - mas podem apresentar uma convergência fraca perto do ótimo.

O valor absoluto de qualquer escolha depende da escala do problema. Marquardt recomendou partir de $λ 0$ e com fator $ν > 1$ . Em seguida, definimos no início $λ = λ 0$ e calculamos a soma dos quadrados dos desvios $S ( p )$ após uma iteração, usando o fator de amortecimento $λ = λ 0 e$ , em seguida, usando $λ / ν$ . Se os dois últimos retornarem um ponto pior do que o ponto inicial, aumentamos $λ$ multiplicando-o por $ν$ , até chegarmos a um ponto melhor com um novo fator $λ ν k$ para um certo $k$ .

Se o uso do fator $λ / ν$ resulta em uma soma menor, então ele é considerado como o novo valor de $λ$ e o algoritmo continua. Se usar $λ / ν$ resulta em uma soma maior, mas usar $λ$ fornece uma soma menor, então $λ$ é mantido.

Referências

(pt) Este artigo foi retirado parcial ou totalmente do artigo da Wikipedia em inglês intitulado “ Algoritmo de Levenberg-Marquardt ” ( veja a lista de autores ) .
(en) K. Levenberg, "Um Método para a Solução de Certos Problemas em Mínimos Quadrados", em Quart. Appl. Matemática. 2 , 1944, p. 164-168
(en) D. Marquardt, "An Algorithm for Least-Squares Estimation of Nonlinear Parameters", em SIAM J. Appl. Matemática. 11 , 1963, p. 431-441
(en) PE Gill e W. Murray , " Algorithms for the solution of the nonlinear mínimos-quadrados problem " , SIAM J. Numer. Anal. , vol. 15, n o 5,1978, p. 977-992

links externos

Descrições de algoritmos

(pt) Receitas numéricas em C , Capítulo 15.5: Modelos não lineares (com uma descrição do algoritmo)
(pt) Métodos de Levenberg-Marquart e estimativa não linear (história deste algoritmo)
(pt) O Algoritmo Levenberg-Marquardt (tutorial escrito por Ananth Ranganathan)

Implementado

(en) lmdif , implementação Fortran clássica , domínio público.
(en) lmfit , biblioteca para uso em programas C ou C ++, licença: domínio público.
(fr) A GNU Scientific Library (GSL) faz parte do projeto GNU, é uma biblioteca escrita em C, licença: GPL .
(en) levmar , implementação GPL em C ++ , Perl e Python .
(en) idiom.com e users.utu.fi : implementações Java .
(pt) gnuplot tem uma implementação.
(pt) ALGLIB , implementações em C #, C ++, Delphi, Visual Basic.
FitOO , modelo e implementação de macro para OpenOffice.org .
IMSL , implementação para Fortran , C / C ++ , Java e C # .
(pt) The MathWorks : LMFsolve.m / LMFnlsq.m , implementação para Matlab .