Levenberg-Marquardt-algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 29. elokuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 6 muokkausta .

Levenberg-Marquardt-algoritmi on optimointimenetelmä, jonka tarkoituksena on ratkaista pienimmän neliösumman tehtäviä . Se on vaihtoehto Newtonin menetelmälle . Voidaan nähdä jälkimmäisen yhdistelmänä gradienttilaskeutumisen kanssa tai luottamusalueen menetelmänä [1] (Marquard, s. 492). Algoritmin muotoilivat itsenäisesti Levenberg ( 1944 ) ja Marquardt ( 1963 ).

Ongelman selvitys

Olkoon muodon pienimmän neliösumman tehtävä:

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

Tälle ongelmalle on ominaista erityinen gradientti ja Hessenin matriisi :

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

missä on vektorifunktion Jacobi-matriisi , on sen komponentin Hessen-matriisi . $J({\vec {x)))$ ${\vec {f))({\vec {x)))$ $H_{i}({\vec {x)))$ $f_{i}({\vec {x)))$

Sitten Gauss-Newton-menetelmän mukaan, olettaen, että termin yli on hallitseva rooli (eli jos normi on merkittävästi pienempi kuin matriisin maksimiominaisarvo ), seuraava suunta määritetään järjestelmästä: $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}}).

Algoritmi

Levenberg-Marquardt-hakusuunta määritetään järjestelmästä:

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

jossa on jokin ei-negatiivinen vakio, joka on spesifinen kullekin vaiheelle, on identiteettimatriisi. $\lambda_k$ $minä$

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

Valinta voidaan tehdä tekemällä siitä riittävä monotoniseen laskeutumiseen jäännösfunktiota pitkin , eli nostamalla parametria, kunnes ehto saavutetaan . Parametri voidaan myös asettaa koevaiheiden tuloksena saavutettujen funktion todellisten muutosten ja näiden muutosten odotettujen arvojen välisen suhteen perusteella interpoloinnin aikana . Fletcher rakensi samanlaisen menettelyn. $\lambda_k$ $F({\vec {x)))$ $F({\vec {x}}_{{k+1}})<F({\vec {x}}_{k})$ $\lambda_k$ ${\vec {f}}({\vec {x}}),$

Voidaan myös osoittaa, että se täyttää ehdon: ${\vec {p}}_{k}$

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

missä on parametriin . $\Delta$ $\lambda_k$

Yhdistelmä gradienttilaskua ja Gauss-Newton-menetelmää

On helppo nähdä, että , algoritmi degeneroituu Gauss-Newton-menetelmäksi ja riittävän suurelle , suunta poikkeaa hieman jyrkimmän laskeutumisen suunnasta. Siten parametrin oikealla valinnalla saavutetaan monotoninen vähennys minimoituun toimintoon. Epätasa -arvoa voidaan aina toteuttaa valitsemalla riittävän suuri. Tässä tapauksessa ensimmäiseen termiin sisältyvät tiedot kaarevuudesta kuitenkin menetetään ja kaikki gradienttilaskeutumismenetelmän haitat tulevat näkyviin : paikoissa, joissa on loiva kaltevuus, antigradientti on pieni ja paikoissa, joissa on kaltevuus. jyrkkä rinne, se on suuri, kun taas ensimmäisessä tapauksessa on toivottavaa ottaa suuria askeleita ja toisessa - pieniä. Joten toisaalta, jos pinnalla on pitkä ja kapea syvennys, jonka määrittelee jäännösfunktio , niin syvennyksen pohjaa pitkin gradientin komponentit ovat pieniä ja seiniä kohti suuria, kun taas se on toivottavaa kulkea rotkon pohjaa pitkin. Marquardt ehdotti menetelmää kaarevuutta koskevien tietojen huomioon ottamiseksi. Hän huomasi, että jos korvaamme identiteettimatriisin Hessenin matriisin diagonaalilla, voimme saavuttaa askeleen kasvun loivilla osuuksilla ja laskun jyrkkiä laskuja pitkin: $\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}).

Luottamusvälimenetelmä

Kun tarkastellaan Levenberg-Marquardt-algoritmia luottamusvälien menetelmänä, heuristiikkaa käyttäen valitaan intervalli , jolle funktion approksimaatio rakennetaan : $\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}}.

Tässä tapauksessa vaihe määräytyy minimointiongelman perusteella : ${\vec {p}}_{k}$

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

Muistiinpanot

↑ B. T. Polyak. Newtonin menetelmä ja sen rooli optimoinnissa ja laskennallisessa matematiikassa // Proceedings of Institute of System Analysis of the Russian Sciences Academy. - 2006. - T. 28 . — S. 44–62 . Arkistoitu alkuperäisestä 24. lokakuuta 2018.

Kirjallisuus

Gill F., Murray W., Wright M. Käytännön optimointi = Käytännön optimointi. - M .: Mir, 1985. - 509 s.

Linkit

Levenberg-Marquardt-menetelmä ALGLIB-kirjastossa on menetelmän toteutus OpenSource ALGLIB -kirjastossa. Useita ohjelmointikieliä.

Optimointimenetelmät _
Yksiulotteinen	kultaisen leikkauksen menetelmä Dikotomia Paraabeli menetelmä Verkkohaku Yhtenäinen lohkohakumenetelmä Fibonaccin menetelmä Kolminkertainen haku Piyavsky menetelmä Vahva menetelmä
Nolla järjestys	Gaussin menetelmä Nelder-Meadin menetelmä Hook-Jeeves -menetelmä Rosenbrockin menetelmä Powellin menetelmä
Ensimmäinen tilaus	gradienttilasku Zeutendijkin menetelmä Koordinaattilasku Konjugaattigradienttimenetelmä Kvasi-Newtonilaiset menetelmät Levenberg-Marquardt-algoritmi
toinen tilaus	Newtonin menetelmä Newton-Raphsonin menetelmä Broyden-Fletcher-Goldfarb-Shanno-algoritmi (BFGS)
Stokastinen	Monte Carlon menetelmä Simuloitu hehkutus Evoluutioalgoritmit differentiaalinen evoluutio Ant algoritmi Hiukkasparvimenetelmä Mehiläisyhdyskunnan algoritmi Satunnainen kävelymenetelmä
Lineaariset ohjelmointimenetelmät _	Yksinkertainen menetelmä Gomorin algoritmi Ellipsoidi menetelmä Potentiaalinen menetelmä
Epälineaariset ohjelmointimenetelmät	Jaksottainen neliöllinen ohjelmointi