Algoritmul Levenberg-Marquardt

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 29 august 2019; verificările necesită 6 modificări .

Algoritmul Levenberg-Marquardt este o metodă de optimizare care vizează rezolvarea problemelor cu cele mai mici pătrate. Este o alternativă la metoda lui Newton . Poate fi privită ca o combinație a acestora din urmă cu coborâre în gradient sau ca o metodă a regiunii de încredere [1] (Marquard, p. 492). Algoritmul a fost formulat independent de Levenberg ( 1944 ) și Marquardt ( 1963 ).

Enunțul problemei

Să existe o problemă cu cele mai mici pătrate de forma:

F({\vec {x)))=\|{\vec {f}}({\vec {x}})\|^{2}=\sum _{{i=1}}^{m} f_{i}^{2}({\vec {x)))=\sum _{{i=1}}^{m}(\varphi _{i}({\vec {x}})-{ \mathcal {F}}_{i})^{2}\to \min \!.

Această problemă se distinge printr-un tip special de gradient și matrice Hessiană :

\nabla F({\vec {x)))=2J^{T}({\vec {x))){\vec {f}}({\vec {x}}),

H({\vec {x)))=2J^{T}({\vec {x)))J({\vec {x)))+2Q({\vec {x))),\qquad Q ({\vec {x)))=\sum _{{i=1}}^{m}f_{i}({\vec {x}})H_{i}({\vec {x}}) ,

unde este matricea Jacobi a funcției vectoriale , este matricea hessiană pentru componenta sa . $J({\vec {x)))$ ${\vec {f))({\vec {x))}$ $H_{i}({\vec {x)))$ $f_{i}({\vec {x)))$

Apoi, conform metodei Gauss-Newton, asumând rolul dominant al termenului peste (adică dacă norma este semnificativ mai mică decât valoarea proprie maximă a matricei ), următoarea direcție este determinată din sistem: $J^{T}({\vec {x)))J({\vec {x)))$ $Q({\vec {x)))$ $\|{\vec {f}}({\vec {x}})\|$ $J^{T}({\vec {x)))J({\vec {x)))$ ${\vec {p}}$

J^{T}({\vec {x}})J({\vec {x}}){\vec {p}}=-J^{T}({\vec {x}}){\vec {f}}({\vec {x}}).

Algoritm

Direcția de căutare Levenberg-Marquardt este determinată din sistem:

[J^{T}({\vec {x}}_{k})J({\vec {x}}_{k})+\lambda _{k}I]{\vec {p}}_ {k}=-J^{T}({\vec {x}}_{k}){\vec {f}}({\vec {x}}_{k}),

unde este o constantă nenegativă, specifică fiecărui pas, este matricea de identitate. $\lambda_k$ $eu$

{\vec {x}}_{{k+1}}={\vec {x}}_{k}+{\vec {p}}_{k}.

Alegerea poate fi făcută făcându-l suficient pentru coborârea monotonă de-a lungul funcției reziduale , adică mărirea parametrului până la atingerea condiției . De asemenea, parametrul poate fi setat pe baza relației dintre modificările reale ale funcției realizate ca urmare a etapelor de încercare și valorile așteptate ale acestor modificări în timpul interpolării . Fletcher a construit o procedură similară. $\lambda_k$ $F({\vec {x)))$ $F({\vec {x}}_{{k+1}})<F({\vec {x}}_{k})$ $\lambda_k$ ${\vec {f}}({\vec {x}}),$

De asemenea, se poate demonstra că îndeplinește condiția: ${\vec {p}}_{k}$

{\vec {p}}_{k}={\mathrm {arg}}\min _({\|{\vec {p}}\|\leqslant \Delta }}\|J({\vec {x }}_{k}){\vec {p}}+{\vec {f}}({\vec {x}}_{k})\|,

unde este parametrul asociat cu . $\Delta$ $\lambda_k$

O combinație de coborâre a gradientului și metoda Gauss-Newton

Este ușor de observat că pentru , algoritmul degenerează în metoda Gauss-Newton , iar pentru suficient de mare , direcția diferă ușor de direcția de coborâre cea mai abruptă. Astfel, prin selectarea corectă a parametrului, se realizează o scădere monotonă a funcției minimizate. Inegalitatea poate fi întotdeauna impusă prin alegerea suficient de mare. Cu toate acestea, în acest caz, informațiile despre curbură , conținute în primul termen, se pierd și apar toate dezavantajele metodei de coborâre a gradientului : în locurile cu o pantă ușoară, anti- gradientul este mic, iar în locurile cu o pantă ușoară. pantă abruptă, este mare, în timp ce în primul caz este de dorit să se facă pași mari, iar în al doilea - mici. Deci, pe de o parte, dacă există o depresiune lungă și îngustă pe suprafața definită de funcția reziduală , atunci componentele gradientului de-a lungul bazei depresiunii sunt mici, iar spre pereți sunt mari, în timp ce este de dorit să meargă de-a lungul bazei râpei. O metodă de luare în considerare a informațiilor despre curbură a fost propusă de Marquardt. El a observat că dacă înlocuim matricea de identitate cu diagonala matricei Hessian, atunci putem obține o creștere a pasului de-a lungul secțiunilor blânde și o scădere de-a lungul coborârilor abrupte: $\lambda _{k}=0$ $\lambda_k$ ${\vec {p}}_{k}$ $\lambda_k$ $F({\vec {x}}_{{k+1}})<F({\vec {x}}_{k})$ $\lambda_k$ $F({\vec {x)))$

\left\{J^{T}({\vec {x}}_{k})J({\vec {x}}_{k})+\lambda _{k}{\mathrm {diag}} \,[J^{T}({\vec {x}}_{k})J({\vec {x}}_{k})]\right\}{\vec {p}}_{k }=-J^{T}({\vec {x}}_{k})f({\vec {x}}_{k}).

Metoda intervalului de încredere

Când se consideră algoritmul Levenberg-Marquardt ca o metodă a intervalelor de încredere, folosind euristică , se selectează un interval pe care se construiește aproximarea funcției : $\Delta$ ${\vec {f))({\vec {x))}$

m({\vec {p)))={\vec {f}}({\vec {x}}_{k})+J({\vec {x}}_{k}){\vec { p))+{\frac {1}{2}}{\vec {p}}\,^{T}H{\vec {p}}.

În acest caz, pasul este determinat pe baza problemei de minimizare : ${\vec {p}}_{k}$

\|m({\vec {p)))\|\to \min _({\|{\vec {p}}\|\leqslant \Delta }}\!.

Note

↑ B. T. Polyak. Metoda lui Newton și rolul său în optimizare și matematică computațională // Proceedings of the Institute of System Analysis of the Russian Academy of Sciences. - 2006. - T. 28 . — S. 44–62 . Arhivat din original pe 24 octombrie 2018.

Literatură

Gill F., Murray W., Wright M. Practical optimization = Practical optimization. — M .: Mir, 1985. — 509 p.

Link -uri

Metoda Levenberg-Marquardt din biblioteca ALGLIB este o implementare a metodei din biblioteca OpenSource ALGLIB. Mai multe limbaje de programare.

Metode de optimizare
Unidimensional	metoda secțiunii de aur Dihotomie Metoda parabolelor Căutare în grilă Metoda de căutare uniformă a blocurilor Metoda Fibonacci Căutare ternară metoda Piyavsky Metoda Strongin
Comanda zero	metoda Gauss Metoda Nelder-Mead Metoda Hook-Jeeves metoda Rosenbrock metoda Powell
Prima comanda	coborâre în gradient Metoda Zeutendijk Coordonarea coborârii Metoda gradientului conjugat Metode cvasi-newtoniene Algoritmul Levenberg-Marquardt
a doua comanda	metoda lui Newton Metoda Newton-Raphson Algoritmul Broyden-Fletcher-Goldfarb-Shanno (BFGS)
Stochastic	Metoda Monte Carlo Recoacere simulată Algoritmi evolutivi evolutie diferentiala Algoritmul furnicilor Metoda roiului de particule Algoritmul coloniilor de albine Metoda de mers aleatoriu
Metode de programare liniară	Metoda simplex algoritmul lui Gomori Metoda elipsoidă Metoda potențială
Metode de programare neliniară	Programare secvenţială pătratică