ドッグレッグ法

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

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

定式化

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

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

$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}$

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

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

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

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

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

${\begin{aligned}F({\boldsymbol {x}}+t{\boldsymbol {\delta _{\mathrm {sd} }}})&\approx {\frac {1}{2}}\left\|{\boldsymbol {f}}({\boldsymbol {x}})+t{\boldsymbol {J}}({\boldsymbol {x}}){\boldsymbol {\delta _{\mathrm {sd} }}}\right\|^{2}\\&=F({\boldsymbol {x}})+t{\boldsymbol {\delta _{\mathrm {sd} }}}^{\top }{\boldsymbol {J}}^{\top }{\boldsymbol {f}}({\boldsymbol {x}})+{\frac {1}{2}}t^{2}\left\|{\boldsymbol {J}}{\boldsymbol {\delta _{\mathrm {sd} }}}\right\|^{2}\end{aligned}}$

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

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

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

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

参照文献

• Lourakis, M.L.A.; Argyros, A.A. (2005). “Is Levenberg-Marquardt the most efficient optimization algorithm for implementing bundle adjustment?”. Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1. pp. 1526-1531. doi:10.1109/ICCV.2005.128. ISBN 0-7695-2334-X 
• Yuan, Ya-xiang (2000). "A review of trust region algorithms for optimization". Iciam. Vol. 99.
• Powell, M.J.D. (1970). “A new algorithm for unconstrained optimization”. In Rosen, J.B.; Mangasarian, O.L.; Ritter, K.. Nonlinear Programming. New York: Academic Press. pp. 31–66 
• Powell, M.J.D. (1970). “A hybrid method for nonlinear equations”. In Robinowitz, P.. Numerical Methods for Nonlinear Algebraic Equations. London: Gordon and Breach Science. pp. 87–144 

外部リンク

• “Equation Solving Algorithms”. MathWorks. 2022年9月17日閲覧。

関連項目

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