ドッグレッグ法

テンプレート:翻訳直後 ドッグレッグ法（ドッグレッグほう、テンプレート:Lang-en-short）またはパウエルのドッグレッグ法（パウエルのドッグレッグほう、テンプレート:Lang-en-short）は、1970年にテンプレート:Ill2によって導入された、非線形最小二乗問題を解くための反復的最適化アルゴリズムであるテンプレート:Sfn。レーベンバーグ・マルカート法と同様にガウス・ニュートン法と勾配降下法とを組み合わせた解法であるが、信頼領域を明示的に使用する。各反復において、ガウス・ニュートン法により算出されたステップが信頼領域内にある場合は、それを使用して現在の解を更新する。ガウス・ニュートン法により算出されたステップが信頼領域外に出てしまう場合、コーシー点と呼ばれる最急降下方向に沿った目的関数の最小点を探す。コーシー点が信頼領域の外側にある場合は、信頼領域の境界まで切りつめられ、新しい解として採用される。コーシー点が信頼領域内にある場合、新しい解は、信頼領域の境界と、コーシー点とガウス・ニュートン法によるステップを結ぶ線（ドッグレッグステップ）との交点を次の解とするテンプレート:Sfn。

このアルゴリズムの名前は、ドッグレッグステップの構成がゴルフのドッグレッグホールの形状に似ていることに由来するテンプレート:Sfn。

定式化

ドッグレッグステップの構成

$f_i:{ℝ}^n\to ℝ$を所与として、次の形式の最小二乗問題を考える。

$F(𝒙)=\frac{1}{2}{\Vert 𝒇(𝒙)\Vert }^2=\frac{1}{2}\sum _{i=1}^m{(f_i(𝒙))}^2$

パウエルのドッグレッグ法は最適点${𝒙}^{*}={\mathrm{argmin}}_{𝒙}F(𝒙)$に収束する点列を${𝒙}_k={𝒙}_{k-1}+{\delta }_k$により構築することでこの問題を解く。各反復において、ガウス・ニュートン法ステップは次のように与えられる。

${\mathit{\delta }}_{\mathrm{g}\mathrm{n}}=-{\left({𝑱}^{\mathrm{\top }}𝑱\right)}^{-1}{𝑱}^{\mathrm{\top }}𝒇(𝒙)$

ここで、$𝑱=\left(\frac{\partial f_i}{\partial x_j}\right)$はヤコビ行列を表わす。一方、最急降下方向は次式のように与えられる。

${\mathit{\delta }}_{\mathrm{s}\mathrm{d}}=-{𝑱}^{\mathrm{\top }}𝒇(𝒙)$

目的関数を最急降下方向に沿って線形化すると、以下を得る。

$\begin{array}{cc}F(𝒙+t{\mathit{\delta }}_{\mathrm{s}\mathrm{d}})& \approx \frac{1}{2}{\Vert 𝒇(𝒙)+t𝑱(𝒙){\mathit{\delta }}_{\mathrm{s}\mathrm{d}}\Vert }^2\\ & =F(𝒙)+t{{\mathit{\delta }}_{\mathrm{s}\mathrm{d}}}^{\mathrm{\top }}{𝑱}^{\mathrm{\top }}𝒇(𝒙)+\frac{1}{2}{t}^2{\Vert 𝑱{\mathit{\delta }}_{\mathrm{s}\mathrm{d}}\Vert }^2\end{array}$

コーシー点におけるパラメータテンプレート:Mvarの値を計算するには、最後の表式をテンプレート:Mvarに関して微分したものとゼロを結んだ等式を解けばよく、解は次の式で与えられる。

$t=-\frac{{{\mathit{\delta }}_{\mathrm{s}\mathrm{d}}}^{\mathrm{\top }}{𝑱}^{\mathrm{\top }}𝒇(𝒙)}{{\Vert 𝑱{\mathit{\delta }}_{\mathrm{s}\mathrm{d}}\Vert }^2}=\frac{{\Vert {\mathit{\delta }}_{\mathrm{s}\mathrm{d}}\Vert }^2}{{\Vert 𝑱{\mathit{\delta }}_{\mathrm{s}\mathrm{d}}\Vert }^2}$

所与の信頼半径$\mathrm{\Delta }$のもと、パウエルのドッグレッグ法では次のように更新ステップ${\mathit{\delta }}_{𝒌}$を選択する。

• ガウス・ニュートンステップ${\mathit{\delta }}_{\mathrm{g}\mathrm{n}}$が信頼領域内にある場合($\Vert {\mathit{\delta }}_{\mathrm{g}\mathrm{n}}\Vert \le \mathrm{\Delta }$)、${\mathit{\delta }}_{\mathrm{g}\mathrm{n}}$
• ${\mathit{\delta }}_{\mathrm{g}\mathrm{n}}$と最急降下ステップ${\mathit{\delta }}_{\mathrm{s}\mathrm{d}}$の両方が信頼領域の外にある場合($\Vert t{\mathit{\delta }}_{𝒔𝒅}\Vert >\mathrm{\Delta }$)、$\frac{\mathrm{\Delta }}{\Vert {\mathit{\delta }}_{\mathrm{s}\mathrm{d}}\Vert }{\mathit{\delta }}_{\mathrm{s}\mathrm{d}}$
• ${\mathit{\delta }}_{\mathrm{g}\mathrm{n}}$は信頼領域の外側にあるが、$t{\mathit{\delta }}_{\mathrm{s}\mathrm{d}}$は内側にある場合、$t{\mathit{\delta }}_{\mathrm{s}\mathrm{d}}+s({\mathit{\delta }}_{\mathrm{g}\mathrm{n}}-t{\mathit{\delta }}_{\mathrm{s}\mathrm{d}})$を$s$について$\Vert \mathit{\delta }\Vert =\mathrm{\Delta }$を満たすよう解いたもの（ドッグレッグステップ）テンプレート:Sfn

参考文献

• テンプレート:Cite book
• テンプレート:Cite conference
• テンプレート:Cite book
• テンプレート:Cite book

関連項目

• ガウス・ニュートン法
• 準ニュートン法

外部リンク

• テンプレート:Cite web