パウエルのドッグレッグ法

パウエルのドッグレッグ法は、パウエルのハイブリッド法とも呼ばれ、非線形最小二乗問題を解くための反復 最適化アルゴリズムであり、1970年にマイケル・J・D・パウエルによって導入されました。^[1]レーベンバーグ・マルカート法と同様に、ガウス・ニュートン法と勾配降下法を組み合わせたものですが、明示的な信頼領域を使用します。各反復で、ガウス・ニュートン法からのステップが信頼領域内にある場合は、それを使用して現在のソリューションを更新します。そうでない場合、アルゴリズムは、コーシー点と呼ばれる最急降下方向に沿って目的関数の最小値を検索します。コーシー点が信頼領域の外側にある場合は、後者の境界で切り捨てられ、新しいソリューションとして採用されます。コーシー点が信頼領域内にある場合は、コーシー点とガウス・ニュートンステップ（ドッグレッグステップ）を結ぶ線と信頼領域の境界との交点で新しいソリューションが採用されます。^[2]

この方法の名前は、ドッグレッグステップの構造とゴルフのドッグレッグホールの形状の類似性に由来しています。^[2]

次のような 最小二乗問題を考える。

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

の場合、パウエルのドッグレッグ法はに収束するシーケンスを構築することで最適点を見つけます。与えられた反復において、ガウス・ニュートンステップは次のように与えられます。 ${\displaystyle f_{i}:\mathbb {R} ^{n}\to \mathbb {R} }$${\displaystyle {\boldsymbol {x}}^{*}=\operatorname {argmin} _{\boldsymbol {x}}F({\boldsymbol {x}})}$ ${\displaystyle {\boldsymbol {x}}_{k}={\boldsymbol {x}}_{k-1}+\delta _{k}}$${\displaystyle {\boldsymbol {x}}^{*}}$

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

ここでヤコビ行列であり、最急降下方向は次のように与えられる。 ${\displaystyle {\boldsymbol {J}}=\left({\frac {\partial {f_{i}}}{\partial {x_{j}}}}\right)}$

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

目的関数は最急降下方向に沿って線形化される

${\displaystyle {\begin{aligned}F({\boldsymbol {x}}+t{\boldsymbol {\delta _{sd}}})&\approx {\frac {1}{2}}\left\|{\boldsymbol {f}}({\boldsymbol {x}})+t{\boldsymbol {J}}({\boldsymbol {x}}){\boldsymbol {\delta _{sd}}}\right\|^{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}}}\right\|^{2}.\end{aligned}}}$

コーシー点におけるパラメータの値を計算するには、最後の式の に対する導関数がゼロになるように課され、 ${\displaystyle t}$${\displaystyle t}$

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

半径 の信頼領域が与えられた場合、パウエルのドッグレッグ法は次のように 更新ステップを選択します。${\displaystyle \Delta }$${\displaystyle {\boldsymbol {\delta _{k}}}}$

• ${\displaystyle {\boldsymbol {\delta _{gn}}}}$ガウス・ニュートンステップが信頼領域（）内にある場合；${\displaystyle \left\|{\boldsymbol {\delta _{gn}}}\right\|\leq \Delta }$
• ${\displaystyle {\frac {\Delta }{\left\|{\boldsymbol {\delta _{sd}}}\right\|}}{\boldsymbol {\delta _{sd}}}}$ガウス・ニュートン法と最急降下法の両方のステップが信頼領域（）の外にある場合；${\displaystyle t\left\|{\boldsymbol {\delta _{sd}}}\right\|>\Delta }$
• ${\displaystyle t{\boldsymbol {\delta _{sd}}}+s\left({\boldsymbol {\delta _{gn}}}-t{\boldsymbol {\delta _{sd}}}\right)}$ガウス・ニュートンステップが信頼領域外にあるが最急降下ステップが信頼領域内にある場合（ドッグレッグステップ）は、となる。^[1]${\displaystyle s}$${\displaystyle \left\|{\boldsymbol {\delta }}\right\|=\Delta }$

• Lourakis, MLA; Argyros, AA (2005)。「Levenberg-Marquardt はバンドル調整を実装するための最も効率的な最適化アルゴリズムか?」第 10 回 IEEE 国際コンピュータ ビジョン会議 (ICCV'05) 第 1 巻。pp . 1526–1531。doi :10.1109/ ICCV.2005.128。ISBN 0-7695-2334-X.S2CID 16542484  。
• Yuan, Ya-xiang (2000)。「最適化のための信頼領域アルゴリズムのレビュー」。Iciam 。第 99 巻。
• Powell, MJD (1970)。「制約のない最適化のための新しいアルゴリズム」。Rosen, JB、Mangasarian, OL、Ritter, K. (編)。非線形プログラミング。ニューヨーク: Academic Press。pp. 31–66。
• Powell, MJD (1970)。「非線形方程式のハイブリッド法」。Robinowitz, P. (編)。非線形代数方程式の数値法。ロンドン: Gordon and Breach Science。pp. 87–144。

• 「方程式を解くアルゴリズム」。MathWorks。