Levenberg-Marquardt algoritmus

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2019. augusztus 29-én felülvizsgált verziótól ; az ellenőrzések 6 szerkesztést igényelnek .

A Levenberg-Marquardt algoritmus egy optimalizálási módszer , amely a legkisebb négyzetek problémáinak megoldására irányul. Ez a Newton-módszer alternatívája . Ez utóbbi kombinációjaként gradiens süllyedéssel vagy konfidenciarégió módszerként [1] tekinthető (Marquard, 492. o.). Az algoritmust egymástól függetlenül Levenberg ( 1944 ) és Marquardt ( 1963 ) fogalmazta meg .

A probléma leírása

Legyen a formának egy legkisebb négyzetek problémája:

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 \!.

Ezt a problémát egy speciális gradiens és Hess-mátrix különbözteti meg :

\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}}) ,

ahol a vektorfüggvény Jacobi - mátrixa , komponensének Hess -mátrixa . $J({\vec {x)))$ ${\vec {f))({\vec {x)))$ $H_{i}({\vec {x)))$ $f_{i}({\vec {x)))$

Ekkor a Gauss-Newton módszer szerint, feltételezve az over tag domináns szerepét (vagyis ha a norma lényegesen kisebb, mint a mátrix maximális sajátértéke ), a rendszerből meghatározzuk a következő irányt : $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}}).

Algoritmus

A Levenberg-Marquardt keresési irányt a rendszer határozza meg:

[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}),

ahol az egyes lépésekre specifikus nemnegatív állandó, az azonosságmátrix. $\lambda_k$ $én$

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

A választás úgy tehető meg, hogy elegendő a monoton leereszkedéshez a maradék függvény mentén , vagyis a paramétert a feltétel eléréséig növeljük . Ezenkívül a paraméter beállítható a próbalépések eredményeként elért függvény tényleges változásai és az interpoláció során bekövetkezett változások várható értékei közötti kapcsolat alapján . Fletcher hasonló eljárást épített ki. $\lambda_k$ $F({\vec {x)))$ $F({\vec {x}}_{{k+1}})<F({\vec {x}}_{k})$ $\lambda_k$ ${\vec {f}}({\vec {x}}),$

Az is kimutatható, hogy megfelel a feltételnek: ${\vec {p}}_{k}$

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

hol van a paraméterhez tartozó paraméter . $\Delta$ $\lambda_k$

A gradiens süllyedés és a Gauss-Newton módszer kombinációja

Könnyen belátható, hogy , esetén az algoritmus Gauss-Newton módszerré degenerálódik , és elég nagy esetén az irány kissé eltér a legmeredekebb süllyedés irányától. Így a paraméter helyes kiválasztásával a minimalizált függvény monoton csökkenése érhető el. Az egyenlőtlenség mindig érvényesíthető, ha elég nagyot választunk. Ebben az esetben azonban az első tagban található görbületi információ elveszik, és megjelenik a gradiens süllyedés módszerének minden hátránya : enyhe lejtős helyeken kicsi az antigradiens, olyan helyeken, ahol meredek lejtőn nagy, míg az első esetben kívánatos nagy lépéseket tenni, a másodikban pedig kicsi. Tehát egyrészt, ha a maradék függvény által meghatározott felületen egy hosszú és keskeny mélyedés van , akkor a mélyedés alapja mentén a gradiens összetevői kicsik, a falak felé pedig nagyok, míg kívánatos a szakadék tövében haladni. Marquardt javasolta a görbületre vonatkozó információk figyelembevételének módszerét. Észrevette, hogy ha az identitásmátrixot a hesseni mátrix átlójával helyettesítjük, akkor enyhe szakaszokon lépésnövekedést, meredek lejtőkön pedig csökkenést érhetünk el: $\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}).

Konfidencia intervallum módszer

Ha a Levenberg-Marquardt algoritmust a konfidenciaintervallumok módszerének tekintjük, heurisztikát használva , kiválasztunk egy intervallumot , amelyre a függvény közelítése épül : $\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}}.

Ebben az esetben a lépést a minimalizálási probléma alapján határozzuk meg : ${\vec {p}}_{k}$

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

Jegyzetek

↑ B. T. Polyak. Newton módszere és szerepe az optimalizálásban és a számítási matematikában // Az Orosz Tudományos Akadémia Rendszerelemző Intézetének közleménye. - 2006. - T. 28 . – S. 44–62 . Archiválva az eredetiből 2018. október 24-én.

Irodalom

Gill F., Murray W., Wright M. Gyakorlati optimalizálás = Practical optimization. — M .: Mir, 1985. — 509 p.

Linkek

Az ALGLIB könyvtár Levenberg-Marquardt metódusa az OpenSource ALGLIB könyvtárban lévő metódus megvalósítása. Több programozási nyelv.

Optimalizálási módszerek
Egydimenziós	aranymetszet módszer Kettősség Parabola módszer Rács keresés Egységes blokkkeresési módszer Fibonacci módszer Háromszoros keresés Piyavsky módszer Strongin módszer
Nulla sorrend	Gauss módszer Nelder-Mead módszer Hook-Jeeves módszer Rosenbrock módszer Powell-módszer
Első rendelés	gradiens süllyedés Zeutendijk módszer Koordináta süllyedés Konjugált gradiens módszer Kvázi-Newtoni módszerek Levenberg-Marquardt algoritmus
másodrendű	Newton módszere Newton-Raphson módszer Broyden-Fletcher-Goldfarb-Shanno algoritmus (BFGS)
Sztochasztikus	Monte Carlo módszer Szimulált lágyítás Evolúciós algoritmusok differenciális evolúció Hangya algoritmus Részecskeraj módszer Méhtelep algoritmus Véletlenszerű séta módszer
Lineáris programozási módszerek	Simplex módszer Gomori algoritmusa Ellipszoid módszer Potenciális módszer
Nemlineáris programozási módszerek	Szekvenciális kvadratikus programozás