Powellsova metoda psích nohou - Powells dog leg method - Wikipedia

Powellova metoda psích nohou je iterativní optimalizace algoritmus pro řešení nelineární nejmenší čtverce problémy, zavedené v roce 1970 Michael J. D. Powell.^[1] Podobně jako Algoritmus Levenberg – Marquardt kombinuje Gauss – Newtonův algoritmus s klesání, ale používá explicitní důvěryhodný region. Pokud je v každé iteraci krok z algoritmu Gauss – Newton v oblasti důvěryhodnosti, použije se k aktualizaci aktuálního řešení. Pokud ne, vyhledá algoritmus minimum z Objektivní funkce podél nejstrmějšího směru klesání, známého jako Cauchyův bod. Pokud je bod Cauchy mimo oblast důvěryhodnosti, je zkrácen na hranici druhé a je považován za nové řešení. Pokud je Cauchyho bod uvnitř oblasti důvěryhodnosti, nové řešení je přijato na křižovatce mezi hranicí oblasti důvěryhodnosti a přímkou ​​spojující Cauchyho bod s Gauss-Newtonovým krokem (krok psí nohy).^[2]

Název metody je odvozen od podobnosti mezi konstrukcí kroku nohy psa a tvarem a psí díra v golf.^[2]

Formulace

Konstrukce kroku psa

Vzhledem k nejmenší čtverce problém ve formě

${ displaystyle F ({ boldsymbol {x}}) = { frac {1} {2}} vlevo | { boldsymbol {f}} ({ boldsymbol {x}}) vpravo | ^ { 2} = { frac {1} {2}} sum _ {i = 1} ^ {m} left (f_ {i} ({ boldsymbol {x}}) right) ^ {2}}$

s ${ displaystyle f_ {i}: mathbb {R} ^ {n} to mathbb {R}}$, Powellova metoda psích nohou najde optimální bod ${ displaystyle { boldsymbol {x}} ^ {*} = operatorname {argmin} _ { boldsymbol {x}} F ({ boldsymbol {x}})}$ vytvořením a sekvence ${ displaystyle { boldsymbol {x}} _ {k} = { boldsymbol {x}} _ {k-1} + delta _ {k}}$ který konverguje k ${ displaystyle { boldsymbol {x}} ^ {*}}$. Při dané iteraci se Gauss – Newton krok je dán

${ displaystyle { boldsymbol { delta _ {gn}}} = - left ({ boldsymbol {J}} ^ { top} { boldsymbol {J}} right) ^ {- 1} { boldsymbol {J}} ^ { top} { boldsymbol {f}} ({ boldsymbol {x}})}$

kde ${ displaystyle { boldsymbol {J}} = vlevo ({ frac { částečné {f_ {i}}} { částečné {x_ {j}}}} vpravo)}$ je Jacobian matrix, zatímco nejstrmější sestup směr je dán

${ displaystyle { boldsymbol { delta _ {sd}}} = - { boldsymbol {J}} ^ { top} { boldsymbol {f}} ({ boldsymbol {x}}).}$

Funkce cíle je linearizována podél nejstrmějšího směru sestupu

${ displaystyle { begin {zarovnáno} F ({ boldsymbol {x}} + t { boldsymbol { delta _ {sd}}}) & cca { frac {1} {2}} vlevo | { boldsymbol {f}} ({ boldsymbol {x}}) + t { boldsymbol {J}} ({ boldsymbol {x}}) { boldsymbol { delta _ {sd}}} vpravo | ^ {2} & = F ({ boldsymbol {x}}) + t { boldsymbol { delta _ {sd}}} ^ { top} { boldsymbol {J}} ^ { top} { boldsymbol {f}} ({ boldsymbol {x}}) + { frac {1} {2}} t ^ {2} left | { boldsymbol {J}} { boldsymbol { delta _ { sd}}} doprava | ^ {2}. end {zarovnáno}}}$

Vypočítat hodnotu parametru ${ displaystyle t}$ v bodě Cauchy, derivát posledního výrazu s ohledem na ${ displaystyle t}$ je stanoveno, že se rovná nule, dávat

${ displaystyle t = - { frac { delta _ {sd} ^ { top} { boldsymbol {J}} ^ { top} { boldsymbol {f}} ({ boldsymbol {x}})} { left | { boldsymbol {J}} { boldsymbol { delta _ {sd}}} right | ^ {2}}}.}$

Vzhledem k oblasti důvěryhodnosti o poloměru ${ displaystyle Delta}$, Powellova metoda psích nohou vybírá krok aktualizace ${ displaystyle { boldsymbol { delta _ {k}}}}$ stejně jako:

• ${ displaystyle { boldsymbol { delta _ {gn}}}}$, pokud je krok Gauss – Newton v oblasti důvěryhodnosti (${ displaystyle left | { boldsymbol { delta _ {gn}}} right | leq Delta}$);
• ${ displaystyle { frac { Delta} { vlevo | { boldsymbol { delta _ {sd}}} vpravo |}} { boldsymbol { delta _ {sd}}}}$ pokud jsou Gauss – Newtonovy i nejstrmější kroky sestupu mimo oblast důvěryhodnosti (${ displaystyle t left | { boldsymbol { delta _ {sd}}} right |}$);
• ${ displaystyle t { boldsymbol { delta _ {sd}}} + s left ({ boldsymbol { delta _ {gn}}} - t { boldsymbol { delta _ {sd}}} right) }$ s ${ displaystyle s}$ takhle ${ displaystyle left | { boldsymbol { delta}} right | = Delta}$, pokud je Gauss – Newtonův krok mimo důvěryhodnou oblast, ale nejstrmější sestupný krok je uvnitř (krok psí nohy).^[1]

Reference

Zdroje

• Lourakis, M.L.A .; Argyros, A.A. (2005). „Je Levenberg-Marquardt nejúčinnějším optimalizačním algoritmem pro implementaci úpravy svazku?“. Desátá mezinárodní konference IEEE o počítačovém vidění (ICCV'05), svazek 1. 2: 1526–1531 sv. 2. doi:10.1109 / ICCV.2005.128.
• Yuan, Ya-xiang (2000). "Kontrola algoritmů oblasti důvěryhodnosti pro optimalizaci". Iciam. 99.
• Powell, M.J.D. (1970). Msgstr "Nový algoritmus pro neomezenou optimalizaci". In Rosen, J.B .; Mangasarian, O.L .; Ritter, K. (eds.). Nelineární programování. New York: Academic Press. 31–66.
• Powell, M.J.D. (1970). "Hybridní metoda pro nelineární rovnice". V Robinowitz, P. (ed.). Numerické metody pro nelineární algebraické rovnice. London: Gordon and Breach Science. str. 87–144.

externí odkazy

• "Algoritmy řešení rovnic". MathWorks.