ドッグレッグ法

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

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

定式化

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

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

F ( x ) = 1 2 ‖ f ( x ) ‖ 2 = 1 2 ∑ i = 1 m ( f i ( x ) ) 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}}

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

δ g n = − ( J ⊤ J ) − 1 J ⊤ f ( x ) {\displaystyle {\boldsymbol {\delta _{\mathrm {gn} }}}=-\left({\boldsymbol {J}}^{\top }{\boldsymbol {J}}\right)^{-1}{\boldsymbol {J}}^{\top }{\boldsymbol {f}}({\boldsymbol {x}})}

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

δ s d = − J ⊤ f ( x ) {\displaystyle {\boldsymbol {\delta _{\mathrm {sd} }}}=-{\boldsymbol {J}}^{\top }{\boldsymbol {f}}({\boldsymbol {x}})}

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

F ( x + t δ s d ) ≈ 1 2 ‖ f ( x ) + t J ( x ) δ s d ‖ 2 = F ( x ) + t δ s d ⊤ J ⊤ f ( x ) + 1 2 t 2 ‖ J δ s d ‖ 2 {\displaystyle {\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 = − δ s d ⊤ J ⊤ f ( x ) ‖ J δ s d ‖ 2 = ‖ δ s d ‖ 2 ‖ J δ s d ‖ 2 {\displaystyle 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}}}}

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

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

出典

  1. ^ a b Powell 1970.
  2. ^ a b Yuan 2000.

参照文献

  • 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日閲覧。

関連項目

  • 表
  • 話
  • 編
  • 歴
非線形(無制約)
… 関数　
勾配法
収束性
準ニュートン法
その他の求解法
… ヘッセ行列
  • 最適化におけるニュートン法（英語版）
The graph of a strictly concave quadratic function is shown in blue, with its unique maximum shown as a red dot. Below the graph appears the contours of the function: The level sets are nested ellipses.
Optimization computes maxima and minima.
非線形(制約付き)
一般
微分可能
凸最適化
凸縮小化
  • 切除平面法（英語版、デンマーク語版、ドイツ語版、スペイン語版）
  • 簡約勾配法
  • 劣勾配法（英語版）
線型 および
二次
内点法
ベイズ-交換
  • 単体法
  • 改訂シンプレックス法（英語版）
  • 十字法（英語版）
  • レムケの主ピボット操作法（英語版）
組合せ最適化
系列範例
(Paradigms)
グラフ理論
最小全域木
最大フロー問題
メタヒューリスティクス
  • カテゴリ（最適化 • アルゴリズム） • ソフトウェア（英語版）