Gauss-Newton 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 2021. január 25-én felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A Gauss-Newton algoritmust a nemlineáris legkisebb négyzetek módszerével használjuk problémák megoldására . Az algoritmus a függvény minimumának meghatározására szolgáló Newton-módszer módosítása . A Gauss-Newton algoritmus a Newton módszertől eltérően csak a négyzetösszeg minimalizálására használható, előnye azonban, hogy a módszer nem igényel második derivált számítást, ami jelentős nehézséget jelenthet.

Problémák, amelyekre a nemlineáris legkisebb négyzetek módszerét alkalmazzák, például a nemlineáris regresszióban merülnek fel, amelyben a modellparamétereket keresik, amelyek a leginkább konzisztensek a megfigyelt értékekkel.

A módszer Carl Friedrich Gauss és Isaac Newton matematikusokról kapta a nevét .

Leírás

Adott m n változó β = ( β 1 , …, β n ) r = ( r 1 , …, r m ) függvénye (gyakran reziduálisnak nevezett), m ≥ n esetén . A Gauss-Newton algoritmus iteratív módon megkeresi azoknak a változóknak az értékeit, amelyek minimalizálják a négyzetösszeget [1]

S({\boldsymbol {\beta )))=\sum _{i=1}^{m}r_{i}^{2}({\boldsymbol {\beta ))).

Néhány kezdeti közelítésből kiindulva a módszer iterál ${\displaystyle {\boldsymbol {\beta }}^{(0)))$

{\boldsymbol {\beta }}^{(s+1)}={\boldsymbol {\beta }}^{(s)}-\left(\mathbf {J_{r}} ^{\mathsf {T}}\mathbf {J_{r}} \right)^{-1}\mathbf {J_{r}} ^{\mathsf {T}}\mathbf {r} ({\boldsymbol {\beta }} ^{(s)})

Itt, ha r -t és β -t oszlopvektornak tekintjük, akkor a Jacobi-mátrix elemei

(\mathbf {J_{r)) )_{ij}={\frac {\partial r_{i}({\boldsymbol {\beta }}^{(s)})}{\partial \beta _{j}}}

a szimbólum pedig mátrixtranszpozíciót jelent . $^{\mathsf {T}}$

Ha m = n , az iterációkat leegyszerűsítjük

{\boldsymbol {\beta }}^{(s+1)}={\boldsymbol {\beta }}^{(s)}-\left(\mathbf {J_{r}} \right)^ {-1}\mathbf {r} ({\boldsymbol {\beta }}^{(s)})

amely Newton egydimenziós módszerének közvetlen általánosítása .

Az adatok illesztésénél, ahol a cél olyan β paraméterek megtalálása, hogy az y = f ( x , β ) függvények adott modellje a legjobban közelítse az ( x i , y i ) adatpontokat , az r i függvények maradékhibák

r_{i}({\boldsymbol {\beta }})=y_{i}-f(x_{i},{\boldsymbol {\beta }}).

Ekkor a Gauss-Newton módszer az f függvény Jacobi J f -jével fejezhető ki

{\boldsymbol {\beta }}^{(s+1)}={\boldsymbol {\beta }}^{(s)}+\left(\mathbf {J_{f}} ^{\mathsf {T}}\mathbf {J_{f}} \right)^{-1}\mathbf {J_{f}} ^{\mathsf {T}}\mathbf {r} ({\boldsymbol {\beta }} ^{(s)}).

Ne feledje, hogy egy pszeudo -inverz mátrix . $\left(\mathbf {J_{f}} ^{\mathsf {T}}\mathbf {J_{f}} \right)^{-1}\mathbf {J_{f}} ^{\mathsf {T}}$ $\mathbf {J_{f))$

Jegyzetek

Az m ≥ n követelmény az algoritmusban szükséges, mert különben a J r T J r mátrixnak nincs inverze, és a normálegyenletek nem oldhatók meg (legalábbis egyértelműen).

A Gauss-Newton algoritmust az r i függvényvektor lineáris közelítésével kaphatjuk meg . A Taylor-tételt használva minden iterációra felírhatjuk:

\mathbf {r} ({\boldsymbol {\beta }})\approx \mathbf {r} ({\boldsymbol {\beta }}^{s})+\mathbf {J_{r}} ({ \boldsymbol {\beta }}^{s})\Delta

ahol . A Δ megtalálásának problémája minimalizálja a jobb oldali négyzetek összegét, azaz. $\Delta ={\boldsymbol {\beta }}-{\boldsymbol {\beta }}^{s}$

\mathbf {min} \|\mathbf {r} ({\boldsymbol {\beta }}^{s})+\mathbf {J_{r}} ({\boldsymbol {\beta }}^{s })\Delta \|_{2}^{2}

egy lineáris legkisebb négyzetek probléma , amely explicit módon megoldható, normál egyenleteket adva.

A normál egyenletek m lineáris egyenletek ismeretlen Δ lépésközzel. Az egyenletek egy lépésben megoldhatók a Cholesky dekompozíció , vagy jobb esetben a J r mátrix QR dekompozíciója segítségével . Nagy rendszerek esetén az iteratív módszer hatékonyabb lehet, ha olyan módszereket alkalmaznak, mint a konjugált gradiens módszer . Ha a J r mátrix oszlopai lineárisan függenek , akkor az iterációs módszer sikertelen, mert J r T J r degenerált lesz.

Példa

Ez a példa a Gauss-Newton algoritmust használja az adatmodell felépítéséhez az adatok és a modell eltéréseinek négyzetes összegének minimalizálásával.

A kísérleti biológiában, a szubsztrát koncentrációja [ S ] és a reakciósebesség közötti összefüggés vizsgálata során az enzimmodulációs reakcióban a következő adatokat kaptuk.

én	egy	2	3	négy	5	6	7
[ S ]	0,038	0,194	0,425	0,626	1.253	2.500	3.740
sebesség	0,050	0,127	0,094	0,2122	0,2729	0,2665	0,3317

Meg kell találni az űrlap görbéjét (függvénymodelljét).

sebesség ,

={\frac {V_{\text{max}}[S]}{K_{M}+[S]}}

amely a legjobban közelíti az adatokat a legkisebb négyzetek értelmében a paraméterekkel és a keresendő. $V_{\text{max))$ ${\displaystyle K_{M))$

Jelölje az [ S ] értékeit és a sebességet a táblázatból, . Hagyjuk és . Meg fogjuk keresni és , így az eltérések négyzetes összegét $x_{i}$ $y_{i}$ $i=1,\pontok ,7$ $\beta _{1}=V_{\text{max))$ ${\displaystyle \beta _{2}=K_{M))$ $\beta_{1}$ $\beta _{2}$

r_{i}=y_{i}-{\frac {\beta _{1}x_{i}}{\beta _{2}+x_{i}}}\;(i=1,\ pontok ,7)

minimális.

Az ismeretlenek feletti maradékok vektorának Jacobi -féle mátrixa, amelynek -edik sora tartalmazza az elemeket $\mathbf {J_{r}}$ $r_{i}$ ${\displaystyle \beta _{j))$ $7\times 2$ $én$

{\frac {\partial r_{i}}{\partial \beta _{1}}}=-{\frac {x_{i}}{\beta _{2}+x_{i}}} ,\ {\frac {\partial r_{i}}{\partial \beta _{2}}}={\frac {\beta _{1}x_{i}}{\left(\beta _{2} +x_{i}\jobbra)^{2}}}.

A kezdeti közelítésből kiindulva és öt iteráció után a Gauss-Newton algoritmus megadja és optimális értékeit . A négyzetes maradékok összege a kezdeti 1,445-ről 0,00784-re csökken az ötödik iterációval. A jobb oldali grafikon a görbét mutatja optimális paraméterekkel. $\beta _{1}=0,9$ $\beta _{2}=0,2$ ${\hat {\beta ))_{1}=0,362$ ${\hat {\beta }}_{2}=0,556$

Konvergencia

Megmutatható [2] , hogy Δ növekedési iránya S esetén a csökkenő iránya , és ha az algoritmus konvergál, akkor a határ az S stacionárius pontja lesz . A konvergencia azonban még akkor sem garantált, ha a kiindulási pont közel van a megoldáshoz , ami a Newton-módszerben vagy a BFGS- módszerben történik normál Volfe-feltételek mellett [3] .

A Gauss-Newton algoritmus konvergenciájának sebessége közel áll a kvadratikushoz [4] . Az algoritmus lassabban vagy egyáltalán nem konvergálhat, ha a kezdeti sejtés messze van a minimumtól, vagy ha a mátrix nem kondicionált . Például képzeljünk el egy problémát egyenletekkel és egy változóval $\mathbf {J_{r}^{\mathsf {T}}J_{r}}$ $m=2$ $n=1$

{\begin{aligned}r_{1}(\beta )&=\beta +1\\r_{2}(\beta )&=\lambda \beta ^{2}+\beta -1.\ vége{igazított}}

Az így kapott optimális megoldás a . (Az igazi optimum , mivel , while .) Ha , akkor a probléma valójában lineáris, és a módszer egy iterációban talál megoldást. Ha |λ| < 1, akkor a módszer lineárisan konvergál és a hiba |λ| sebességgel csökken minden iterációnál. Ha azonban |λ| > 1, akkor a módszer még lokálisan sem konvergál [5] . $\beta =0$ $\beta =-1$ $\lambda =2$ $S(0)=1^{2}+(-1)^{2}=2$ $S(-1)=0$ $\lambda=0$

Newton-módszeren alapuló algoritmus

A következőkben feltételezzük, hogy a Gauss-Newton algoritmus a Newton-módszeren alapul a függvény közelítéssel történő minimalizálására. Következésképpen a Gauss-Newton algoritmus konvergenciája négyzetes lehet, ha bizonyos feltételek teljesülnek. Általános esetben (gyengébb körülmények között) a konvergencia mértéke lineáris lehet [6] .

A Newton-módszer ismétlődési relációja a paraméterek S függvényének minimalizálására ${\boldsymbol {\beta ))$

{\boldsymbol {\beta }}^{(s+1)}={\boldsymbol {\beta }}^{(s)}-\mathbf {H} ^{-1}\mathbf {g} \,

ahol g az S függvény gradiensvektorát , H pedig az S függvény Hess-vektorát jelöli . Mivel , a gradienst az egyenlőség adja $S=\sum _{i=1}^{m}r_{i}^{2}$

g_{j}=2\sum _{i=1}^{m}r_{i}{\frac {\partial r_{i}}{\partial \beta _{j}}}.

A Hess-elemek kiszámítása a gradiens elemek megkülönböztetésével történik ${\displaystyle g_{j))$ ${\displaystyle \beta _{k))$

H_{jk}=2\sum _{i=1}^{m}\left({\frac {\partial r_{i)){\partial \beta _{j))}{\frac { \partial r_{i}}{\partial \beta _{k}}}+r_{i}{\frac {\partial ^{2}r_{i}}{\partial \beta _{j}\partial \ béta _{k}}}\jobbra).

A Gauss-Newton módszert a második derivált (a kifejezés második tagjának) elvetésével kapjuk meg. Vagyis a hesseni közelítő

{\displaystyle H_{jk}\approx 2\sum _{i=1}^{m}J_{ij}J_{ik))

hol vannak a jakobi J r elemei . A gradiens és a közelítő Hess-féle mátrixjelöléssel írható fel $J_{ij}={\frac {\partial r_{i}}{\partial \beta _{j}}}$

\mathbf {g} =2\mathbf {J} _{\mathbf {r} }^{\mathsf {T}}\mathbf {r} ,\quad \mathbf {H} \approx 2\mathbf { J} _{\mathbf {r} }^{\mathsf {T}}\mathbf {J_{r}} .\,

Ezeket a kifejezéseket behelyettesítjük a fenti rekurziós relációba, hogy megkapjuk a működési egyenleteket

{\boldsymbol {\beta }}^{(s+1)}={\boldsymbol {\beta }}^{(s)}+\Delta ;\quad \Delta =-\left(\mathbf { J_{r)) ^{\mathsf {T}}\mathbf {J_{r}} \right)^{-1}\mathbf {J_{r}} ^{\mathsf {T}}\mathbf {r} .

A Gauss-Newton módszer konvergenciája általában nem garantált. Közelítés

\left|r_{i}{\frac {\partial ^{2}r_{i}}{\partial \beta _{j}\partial \beta _{k}}}\right|\ll \ bal|{\frac {\partial r_{i}}{\partial \beta _{j}}}{\frac {\partial r_{i}}{\partial \beta _{k}}}\right|

amelyeknek teljesülniük kell ahhoz, hogy a második származékkal rendelkező kifejezéseket el lehessen vetni, két olyan esetben is beszerezhető, amelyeknél konvergencia várható [7]

A függvényértékek kicsik, legalábbis a minimum közelében vannak. $r_{i}$
A függvények csak "kissé" nemlineárisak, azaz viszonylag kicsik. ${\displaystyle {\frac {\partial ^{2}r_{i}}{\partial \beta _{j}\partial \beta _{k))))$

Továbbfejlesztett verziók

A Gauss-Newton módszerekben előfordulhat, hogy az S négyzetes maradékok összege nem csökken minden iterációnál. Mivel azonban Δ a függvény csökkenésének irányába irányul, ha nem stacionárius pontról van szó, az egyenlőtlenség kellően kicsire érvényes . Így, ha eltérést találunk, használhatjuk a Δ növekményvektor törtrészét a frissítési képletben: $S({\boldsymbol {\beta }}^{s})$ $S({\boldsymbol {\beta }}^{s}+\alpha \Delta )<S({\boldsymbol {\beta }}^{s})$ $\alpha >0$ $\alpha$

{\boldsymbol {\beta }}^{s+1}={\boldsymbol {\beta }}^{s}+\alpha \ \Delta

Vagyis a növekményvektor túl hosszú, de az "ereszkedés" irányát jelzi, így ha csak az út egy részét haladod, csökkentheted az S függvény értékét . Az optimális értéket egy egydimenziós keresési segítségével találhatjuk meg , vagyis az értéket úgy határozzuk meg, hogy megtaláljuk az S - t minimalizáló értéket egydimenziós kereséssel az intervallumon . $\alpha$ $\alpha$ $0<\alpha<1$

Azokban az esetekben, amikor az optimális tört a növekményvektor irányában nullához közeli, a divergencia kiszámításának alternatív módszere a Levenberg-Marquardt algoritmus , más néven „bizalmi régió módszer” [1] . Normál egyenletek úgy módosítva, hogy az ereszkedési vektor a legmeredekebb süllyedés irányába forog , $\alpha$

\left(\mathbf {J^{T}J+\lambda D} \right)\Delta =-\mathbf {J} ^{T}\mathbf {r}

ahol D egy pozitív átlós mátrix. Vegye figyelembe, hogy ha D az E és az azonosságmátrixa , akkor . Így a Δ irány közelíti a negatív gradiens irányát . $\lambda \to +\infty$ $\lambda \Delta =\lambda \left(\mathbf {J^{E}J} +\lambda \mathbf {E} \right)^{-1}\left(-\mathbf {J} ^{ T}\mathbf {r} \right)=\left(\mathbf {E} -\mathbf {J^{T}J} /\lambda +\cdots \right)\left(-\mathbf {J} ^{ T}\mathbf {r} \right)\to -\mathbf {J} ^{T}\mathbf {r}$ $-\mathbf {J} ^{T}\mathbf {r}$

Az úgynevezett Marquardt paramétert lineáris kereséssel is lehet optimalizálni, de ennek nincs sok értelme, hiszen az eltolásvektort minden változáskor újra kell számolni . Hatékonyabb stratégia ez. Ha eltérést talál, növelje a Marquardt-paramétert, ahogy S csökken. Ezután megtartjuk az értéket az iterációk között, de lehetőség szerint csökkentjük, amíg el nem érjük azt az értéket, ahol a Marquardt paraméter nem nullázható. Az S minimalizálása ezután a standard Gauss–Newton minimalizálássá válik. $\lambda$ $\lambda$

Nagy feladatok optimalizálása

Nagy méretű optimalizálás esetén a Gauss-Newton módszer különösen érdekes, mert gyakran (bár biztosan nem mindig) a mátrix ritka , mint a hozzávetőleges Hess-féle . Ilyen esetekben maga a számítási lépés általában iteratív közelítési módszert, például konjugált gradiens módszert igényel . ${\displaystyle \mathbf {J} _{\mathbf {r} ))$ $\mathbf {J} _{\mathbf {r} }^{\mathsf {T}}\mathbf {J_{r}}$

Ahhoz, hogy ez a megközelítés működjön, legalább egy hatékony módszerre van szüksége a termék kiszámításához

\mathbf {J} _{\mathbf {r} }^{\mathsf {T}}\mathbf {J_{r}} \mathbf {p}

valamilyen p vektorra . Ritka mátrix tárolásához célszerű a mátrix sorait tömörített formában (tehát nulla elemek nélkül) tárolni, ami megnehezíti a fenti szorzat közvetlen kiszámítását (transzpozíció miatt). Ha azonban c i a mátrix i soraként van definiálva , a következő összefüggés áll fenn: ${\displaystyle \mathbf {J} _{\mathbf {r} ))$ ${\displaystyle \mathbf {J} _{\mathbf {r} ))$

\mathbf {J} _{\mathbf {r} }^{\mathsf {T}}\mathbf {J_{r}} \mathbf {p} =\sum _{i}\mathbf {c} _ {i}(\mathbf {c} _{i}\cdot \mathbf {p} )

így bármely sor additív módon és függetlenül járul hozzá a termékhez. Ezenkívül ez a kifejezés jól tanulmányozott a párhuzamos számítások alkalmazására . Figyeljük meg, hogy bármelyik c i sor a megfelelő r i maradék gradiense . Ezt a körülményt figyelembe véve a fenti képlet azt a tényt hangsúlyozza, hogy a maradékok egymástól függetlenül járulnak hozzá az eredményhez.

Kapcsolódó algoritmusok

A kvázi-newtoni módszerekben , mint például Davidon, Fletcher és Powell vagy Broyden-Fletcher-Goldfarb-Shanno módszere ( BFGSh módszer ), a teljes Hess-közelítést az első deriváltok felhasználásával állítják össze úgy, hogy n finomítás után a módszer teljesítményében közel áll a Newton-módszerhez. Megjegyezzük, hogy a kvázi-newtoni módszerek minimalizálhatják az általános formájú valós függvényeket, míg a Gauss-Newton, Levenberg-Marquardt stb. csak nemlineáris legkisebb négyzetek problémáira alkalmazhatók. ${\displaystyle {\frac {\partial ^{2}S}{\partial \beta _{j}\partial \beta _{k))))$ ${\frac {\partial r_{i}}{\partial \beta _{j}}}$

Egy másik módszer a minimalizálási problémák megoldására csak az első deriváltokkal a gradiens süllyedés módszer . Ez a módszer azonban nem veszi figyelembe a második deriváltokat, még a közelítőket sem. Ebből kifolyólag a módszer rendkívül hatástalan számos funkciónál, különösen a paraméterek erős kölcsönös befolyásolása esetén.

Jegyzetek

↑ 1 2 Björck, 1996 .
↑ Björck, 1996 , p. 260.
↑ Mascarenhas, 2013 , p. 253–276.
↑ Björck, 1996 , p. 341, 342.
↑ Fletcher, 1987 , p. 113.
↑ Gratton, Lawless, Nichols .
↑ Nocedal, Wright, 1999 , p. 259-262.

Irodalom

A. Björck. Numerikus módszerek a legkisebb négyzetek problémáira. - Philadelphia: SIAM, 1996. - ISBN 0-89871-360-9 .
Roger Fletcher. Az optimalizálás gyakorlati módszerei . — 2. - New York: John Wiley & Sons , 1987. - ISBN 978-0-471-91547-8 .
Walter F. Mascarenhas. A BFGS és a Gauss Newton módszer eltérése // Matematikai programozás. - 2013. - T. 147 , sz. 1 . - doi : 10.1007/s10107-013-0720-6 .
S. Gratton, AS Lawless, NK Nichols. Hozzávetőleges Gauss-Newton módszerek nemlineáris legkisebb négyzetek problémáihoz . SZÁMÚ ELEMZŐ JELENTÉS 9/04 (angol) (hivatkozás nem érhető el) . A Readingi Egyetem (2007. január) . Letöltve: 2017. július 20. Az eredetiből archiválva : 2016. augusztus 4..
Jorge Nocedal, Stephen J. Wright. Numerikus optimalizálás / Peter Glynn, Stephen M. Robinson. - New York: Springer, 1999. - (Springer sorozat az operatív kutatásban). — ISBN 0-387-98793-2 .

Linkek

Megvalósítások

Artelys Knitro Nemlineáris problémák megoldására szolgáló rendszer a Gauss-Newton módszer megvalósításával. A rendszer C nyelven íródott, és C++/C#/Java/Python/MATLAB/R interfészekkel rendelkezik.

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