Gauss-Newtonův algoritmus

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 25. ledna 2021; ověření vyžaduje 1 úpravu .

Gauss-Newtonův algoritmus se používá k řešení problémů nelineární metodou nejmenších čtverců . Algoritmus je modifikací Newtonovy metody pro nalezení minima funkce . Na rozdíl od Newtonovy metody lze Gauss-Newtonův algoritmus použít pouze k minimalizaci součtu čtverců, ale jeho výhodou je, že metoda nevyžaduje výpočet sekundových derivací, což může být značný problém.

Problémy, pro které je aplikována nelineární metoda nejmenších čtverců, vznikají např. u nelineární regrese , při které se hledají parametry modelu, které nejvíce odpovídají pozorovaným hodnotám.

Metoda je pojmenována podle matematiků Carla Friedricha Gausse a Isaaca Newtona .

Popis

Je dáno m funkcí r = ( r 1 , …, r m ) (často nazývaných rezidua) n proměnných β = ( β 1 , …, β n ), pro m ≥ n . Gauss-Newtonův algoritmus iterativně najde hodnoty proměnných, které minimalizují součet čtverců [1]

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

Počínaje nějakou počáteční aproximací metoda iteruje ${\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)})

Pokud zde považujeme r a β za sloupcové vektory, prvky jakobiánské matice jsou

(\mathbf {J_{r)) )_{ij}={\frac {\částečné r_{i}({\boldsymbol {\beta }}^{(s)})}{\částečné \beta _{j}}}

a symbol znamená maticovou transpozici . $^{\mathsf {T}}$

Pokud m = n , iterace se zjednoduší na

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

což je přímé zobecnění Newtonovy jednorozměrné metody .

Při dosazování dat, kde je cílem najít parametry β takové, aby daný model funkcí y = f ( x , β ) nejlépe aproximoval datové body ( x i , y i ), jsou funkce r i zbytkové chyby

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

Potom lze Gaussovu-Newtonovu metodu vyjádřit pomocí jakobiánu J f funkce f

{\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)}).

Všimněte si, že jde o pseudo -inverzní matici k . $\left(\mathbf {J_{f}} ^{\mathsf {T}}\mathbf {J_{f}} \right)^{-1}\mathbf {J_{f}} ^{\mathsf {T}}$ $\mathbf {J_{f))$

Poznámky

Požadavek m ≥ n v algoritmu je nutný, protože jinak matice J r T J r nemá inverzní hodnotu a normální rovnice nelze řešit (alespoň jednoznačně).

Gauss-Newtonův algoritmus lze získat pomocí lineární aproximace funkčního vektoru r i . Pomocí Taylorovy věty můžeme pro každou iteraci napsat:

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

kde . Problém najít Δ minimalizující součet čtverců na pravé straně, tzn. $\Delta ={\boldsymbol {\beta }}-{\boldsymbol {\beta }}^{s}$

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

je lineární problém nejmenších čtverců , který lze řešit explicitně a dává normální rovnice.

Normální rovnice jsou m lineárních rovnic v neznámých přírůstcích Δ. Rovnice lze řešit v jednom kroku pomocí Choleského rozkladu nebo lépe QR rozkladu matice J r . U velkých systémů může být iterační metoda účinnější, pokud se použijí metody, jako je metoda konjugovaného gradientu . Pokud existuje lineární závislost sloupců matice J r , iterační metoda selhává, protože J r T J r se stává degenerovaným.

Příklad

Tento příklad používá Gauss-Newtonův algoritmus k vytvoření datového modelu minimalizací součtu čtverců odchylek dat a modelu.

V experimentální biologii, studiu vztahu mezi koncentrací substrátu [ S ] a reakční rychlostí v enzymové modulační reakci, byly získány následující údaje.

i	jeden	2	3	čtyři	5	6	7
[ S ]	0,038	0,194	0,425	0,626	1,253	2 500	3,740
Rychlost	0,050	0,127	0,094	0,2122	0,2729	0,2665	0,3317

Je nutné najít křivku (funkční model) formuláře

rychlost ,

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

který nejlépe aproximuje data ve smyslu nejmenších čtverců s parametry a k nalezení. $V_{\text{max))$ ${\displaystyle K_{M))$

Označte pomocí a hodnoty [ S ] a rychlost z tabulky, . Nechte a . Budeme hledat a , takové, že součet čtverců odchylek $x_{i}$ $y_{i}$ $i=1,\tečky ,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,\ tečky ,7)

minimální.

Jacobiánem vektoru reziduí nad neznámými je matice s -tým řádkem obsahujícím prvky $\mathbf {J_{r}}$ $r_{i}$ ${\displaystyle \beta _{j))$ $7\times 2$ $i$

{\frac {\partial r_{i}}{\partial \beta _{1}}}=-{\frac {x_{i}}{\beta _{2}+x_{i}}} ,\ {\frac {\částečné r_{i}}{\částečné \beta _{2}}}={\frac {\beta _{1}x_{i}}{\left(\beta _{2} +x_{i}\right)^{2}}}.

Počínaje počáteční aproximací a po pěti iteracích poskytuje Gauss-Newtonův algoritmus optimální hodnoty a . Součet kvadrátů reziduí klesá z počáteční hodnoty 1,445 na 0,00784 při páté iteraci. Graf vpravo ukazuje křivku s optimálními parametry. $\beta _{1}=0,9$ $\beta _{2}=0,2$ ${\klobouček {\beta ))_{1}=0,362$ ${\klobouček {\beta }}_{2}=0,556$

Konvergence

Lze ukázat [2] , že směr růstu Δ je směrem sestupu pro S , a pokud bude algoritmus konvergovat, limita bude stacionární bod pro S . Konvergence však není zaručena ani tehdy, když je počáteční bod blízko řešení , což se děje v Newtonově metodě nebo BFGS za normálních Volfeho podmínek [3] .

Rychlost konvergence Gauss-Newtonova algoritmu se blíží kvadratické [4] . Algoritmus může konvergovat pomaleji nebo vůbec ne, pokud je počáteční odhad daleko od minima nebo pokud je matice špatně podmíněná . Představte si například problém s rovnicemi a proměnnou $\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.\ konec{aligned}}

Výsledné optimální řešení je . (Skutečné optimum je pro , since , while .) Jestliže , pak je problém ve skutečnosti lineární a metoda najde řešení v jedné iteraci. Pokud |λ| < 1, pak metoda lineárně konverguje a chyba klesá rychlostí |λ| při každé iteraci. Pokud však |λ| > 1, pak metoda nekonverguje ani lokálně [5] . $\beta =0$ $\beta =-1$ $\lambda =2$ $S(0)=1^{2}+(-1)^{2}=2$ $S(-1)=0$ $\lambda=0$

Algoritmus založený na Newtonově metodě

Následující předpokládá, že Gauss-Newtonův algoritmus je založen na Newtonově metodě pro minimalizaci funkcí aproximací. V důsledku toho může být rychlost konvergence Gauss-Newtonova algoritmu kvadratická, pokud jsou splněny určité podmínky. V obecném případě (za slabších podmínek) může být rychlost konvergence lineární [6] .

Rekurentní vztah Newtonovy metody pro minimalizaci funkce S parametrů ${\boldsymbol {\beta ))$

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

kde g označuje gradientový vektor funkce S a H označuje Hessián funkce S. Protože je gradient dán rovností ${\displaystyle S=\sum _{i=1}^{m}r_{i}^{2))$

g_{j}=2\sum _{i=1}^{m}r_{i}{\frac {\částečné r_{i}}{\částečné \beta _{j}}}.

Hessovské prvky jsou počítány diferencováním gradientních prvků vzhledem k ${\displaystyle g_{j))$ ${\displaystyle \beta _{k))$

H_{jk}=2\sum _{i=1}^{m}\left({\frac {\částečné r_{i)){\částečné \beta _{j))}{\frac { \částečné r_{i}}{\částečné \beta _{k}}}+r_{i}{\frac {\částečné ^{2}r_{i}}{\částečné \beta _{j}\částečné \ beta _{k}}}\right).

Gauss-Newtonova metoda se získá vyřazením druhé derivace (druhého členu ve výrazu). To znamená, že Hessian je aproximovaný

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

kde jsou prvky jakobiánského J r . Gradient a přibližný Hessian lze zapsat v maticovém zápisu $J_{ij}={\frac {\částečné r_{i}}{\částečné \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}} .\,

Tyto výrazy se dosadí do výše uvedeného rekurzního vztahu, aby se získaly provozní rovnice

{\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} .

Konvergence Gauss-Newtonovy metody obecně není zaručena. Přiblížení

\left|r_{i}{\frac {\částečné ^{2}r_{i}}{\částečné \beta _{j}\částečné \beta _{k}}}\pravé|\ll \ vlevo|{\frac {\částečné r_{i}}{\částečné \beta _{j}}}{\frac {\částečné r_{i}}{\částečné \beta _{k}}}\vpravo|

který musí platit, aby bylo možné vyřadit členy s druhou derivací, lze získat ve dvou případech, u kterých se očekává konvergence [7]

Hodnoty funkcí mají malou velikost, alespoň blízko minima. $r_{i}$
Funkce jsou jen "mírně" nelineární, tedy relativně malé velikosti. ${\displaystyle {\frac {\partial ^{2}r_{i}}{\partial \beta _{j}\partial \beta _{k))))$

Vylepšené verze

V Gauss-Newtonových metodách se součet druhých mocnin zbytků S nemusí snižovat při každé iteraci. Protože však Δ směřuje ve směru klesající funkce, pokud se nejedná o stacionární bod, platí nerovnost pro dostatečně malé . Pokud je tedy nalezena divergence, lze v aktualizačním vzorci použít zlomek vektoru přírůstku Δ: $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

Jinými slovy, vektor přírůstku je příliš dlouhý, ale ukazuje směr „sestupu“, takže pokud půjdete jen část cesty, můžete snížit hodnotu funkce S . Optimální hodnotu lze nalézt pomocí jednorozměrného vyhledávacího , to znamená, že hodnota je určena nalezením hodnoty, která minimalizuje S pomocí jednorozměrného vyhledávání na intervalu . $\alpha$ $\alpha$ $0<\alpha<1$

V případech, kdy se optimální zlomek blíží nule ve směru vektoru přírůstku, je alternativní metodou pro vypracování divergence použití Levenberg-Marquardtova algoritmu , známého také jako „metoda oblasti spolehlivosti“ [1] . Normální rovnice upraveny tak, že vektor klesání se otáčí ve směru nejstrmějšího klesání , $\alpha$

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

kde D je kladná diagonální matice. Všimněte si, že pokud D je matice identity E a , pak . Směr Δ se tedy blíží směru záporného gradientu . $\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}$

Takzvaný Marquardtův parametr lze optimalizovat i lineárním vyhledáváním, ale to nedává moc smysl, protože vektor posunu je potřeba při každé změně přepočítat . Efektivnější strategie je tato. Pokud je zjištěna nesrovnalost, zvyšte Marquardtův parametr, když S klesá. Poté hodnotu mezi iteracemi ponecháme, ale pokud možno ji snížíme, dokud nedosáhneme hodnoty, kdy nelze Marquardtův parametr vynulovat. Minimalizace S se pak stává standardní Gauss-Newtonovou minimalizací. $\lambda$ $\lambda$

Optimalizace velkých úloh

Pro velké optimalizace je Gauss-Newtonova metoda obzvláště zajímavá, protože často (i když určitě ne vždy) je matice řidší než přibližná Hessova . V takových případech samotný krok výpočtu obvykle vyžaduje použití metody iterativní aproximace, jako je metoda konjugovaného gradientu . ${\displaystyle \mathbf {J} _{\mathbf {r} ))$ $\mathbf {J} _{\mathbf {r} }^{\mathsf {T}}\mathbf {J_{r}}$

Aby tento přístup fungoval, potřebujete alespoň efektivní metodu výpočtu produktu

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

pro nějaký vektor p . Pro uložení řídké matice je praktické ukládat řádky matice ve stlačené podobě (tj. bez nulových prvků), což ztěžuje přímý výpočet výše uvedeného součinu (kvůli transpozici). Pokud je však c i definováno jako řádek i matice , platí následující vztah: ${\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} )

takže jakýkoli řádek přispívá k produktu aditivně a nezávisle. Kromě toho je tento výraz dobře studován pro aplikaci paralelních výpočtů . Všimněte si, že libovolný řádek c i je gradientem odpovídajícího zbytkového r i . S ohledem na tuto okolnost výše uvedený vzorec zdůrazňuje skutečnost, že rezidua přispívají k výsledku nezávisle na sobě.

Související algoritmy

V kvazi-newtonských metodách , jako jsou metody Davidona, Fletchera a Powella nebo Broyden-Fletcher-Goldfarb-Shanno ( metoda BFGSh ), je úplná Hessova aproximace konstruována pomocí prvních derivací , takže po n upřesněních je metoda výkonem se blíží Newtonově metodě. Všimněte si, že kvazi-newtonské metody mohou minimalizovat reálné funkce obecné formy, zatímco metody Gauss-Newton, Levenberg-Marquardt atd. jsou použitelné pouze pro nelineární problémy nejmenších čtverců. ${\displaystyle {\frac {\partial ^{2}S}{\partial \beta _{j}\partial \beta _{k))))$ ${\frac {\částečné r_{i}}{\částečné \beta _{j}}}$

Další metodou pro řešení problémů minimalizace pomocí pouze prvních derivací je metoda sestupu gradientu . Tato metoda však nebere v úvahu druhé derivace, a to ani přibližné. V důsledku toho je metoda pro řadu funkcí krajně neefektivní, zejména v případě silného vzájemného ovlivňování parametrů.

Poznámky

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

Literatura

A. Björck. Numerické metody pro úlohy nejmenších čtverců. - Philadelphia: SIAM, 1996. - ISBN 0-89871-360-9 .
Roger Fletcher. Praktické metody optimalizace . — 2. - New York: John Wiley & Sons , 1987. - ISBN 978-0-471-91547-8 .
Walter F. Mascarenhas. Divergence BFGS a Gauss Newtonovy metody // Matematické programování. - 2013. - T. 147 , č.p. 1 . - doi : 10.1007/s10107-013-0720-6 .
S. Gratton, AS Lawless, NK Nichols. Přibližné Gauss-Newtonovy metody pro nelineární úlohy nejmenších čtverců . ZPRÁVA O ČÍSELNÉ ANALÝZE 9/04 (anglicky) (odkaz není k dispozici) . Univerzita v Readingu (leden 2007) . Získáno 20. července 2017. Archivováno z originálu 4. srpna 2016.
Jorge Nocedal, Stephen J. Wright. Numerická optimalizace / Peter Glynn, Stephen M. Robinson. - New York: Springer, 1999. - (Springer Series v operačním výzkumu). — ISBN 0-387-98793-2 .

Odkazy

Implementace

Artelys Knitro . Systém pro řešení nelineárních problémů s implementací Gauss-Newtonovy metody. Systém je napsán v C a má rozhraní pro C++/C#/Java/Python/MATLAB/R.

Optimalizační metody
Jednorozměrný	metoda zlatého řezu Dichotomie Parabolová metoda Vyhledávání v mřížce Jednotná metoda vyhledávání bloků Fibonacciho metoda Ternární hledání Piyavského metoda Stronginovou metodou
Nulové pořadí	Gaussova metoda Metoda Nelder-Mead Hook-Jeevesova metoda Rosenbrockova metoda Powellova metoda
První objednávka	gradientní sestup Zeutendijkova metoda Souřadnicový sestup Metoda konjugovaného gradientu Kvazi-newtonské metody Levenberg-Marquardtův algoritmus
druhá objednávka	Newtonova metoda Newton-Raphsonova metoda Algoritmus Broyden-Fletcher-Goldfarb-Shanno (BFGS)
Stochastické	Metoda Monte Carlo Simulované žíhání Evoluční algoritmy diferenciální evoluce Algoritmus mravenců Metoda roje částic Algoritmus včelstva Metoda náhodné chůze
Metody lineárního programování	Simplexní metoda Gomoriho algoritmus Elipsoidní metoda Potenciální metoda
Metody nelineárního programování	Sekvenční kvadratické programování