ドッグレッグ法

この項目「ドッグレッグ法」は翻訳されたばかりのものです。不自然あるいは曖昧な表現などが含まれる可能性があり、このままでは読みづらいかもしれません。（原文：en: Powell's dog leg method） 修正、加筆に協力し、現在の表現をより自然な表現にして下さる方を求めています。ノートページや履歴も参照してください。（2022年9月）

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

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

定式化[編集]

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

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

${\displaystyle {\boldsymbol {\delta _{\mathrm {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 _{\mathrm {sd} }}}=-{\boldsymbol {J}}^{\top }{\boldsymbol {f}}({\boldsymbol {x}})}$

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

${\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に関して微分したものとゼロを結んだ等式を解けばよく、解は次の式で与えられる。

${\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 }$のもと、パウエルのドッグレッグ法では次のように更新ステップ${\displaystyle {\boldsymbol {\delta _{k}}}}$を選択する。

• ガウス・ニュートンステップ${\displaystyle {\boldsymbol {\delta _{\mathrm {gn} }}}}$が信頼領域内にある場合(${\displaystyle \left\|{\boldsymbol {\delta _{\mathrm {gn} }}}\right\|\leq \Delta }$)、${\displaystyle {\boldsymbol {\delta _{\mathrm {gn} }}}}$
• ${\displaystyle {\boldsymbol {\delta _{\mathrm {gn} }}}}$と最急降下ステップ${\displaystyle {\boldsymbol {\delta _{\mathrm {sd} }}}}$の両方が信頼領域の外にある場合(${\displaystyle \left\|t{\boldsymbol {\delta _{sd}}}\right\|>\Delta }$)、${\displaystyle {\frac {\Delta }{\left\|{\boldsymbol {\delta _{\mathrm {sd} }}}\right\|}}{\boldsymbol {\delta _{\mathrm {sd} }}}}$
• ${\displaystyle {\boldsymbol {\delta _{\mathrm {gn} }}}}$は信頼領域の外側にあるが、${\displaystyle t{\boldsymbol {\delta _{\mathrm {sd} }}}}$は内側にある場合、${\displaystyle t{\boldsymbol {\delta _{\mathrm {sd} }}}+s\left({\boldsymbol {\delta _{\mathrm {gn} }}}-t{\boldsymbol {\delta _{\mathrm {sd} }}}\right)}$を${\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日閲覧。

関連項目[編集]

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

表 話 編 歴 数理最適化 • 最適化問題 : メソッド • ヒューリスティック
非線形(無制約)	… 関数　 黄金分割探索 直線探索 ネルダー–ミード法 連続放物線補間（英語版） 勾配法 収束性 信頼領域 ウルフ条件（英語版） 準ニュートン法 BFGS法 ブロイデン法 L-BFGS（英語版） DFP法 対称ランク1法（英語版） その他の求解法 ガウス・ニュートン法 最急降下法 レーベンバーグ・マルカート法 共役勾配法（非線形共役勾配法） 切り捨てニュートン法（英語版） ドッグレッグ法 … ヘッセ行列 最適化におけるニュートン法（英語版）
非線形(制約付き)	一般 バリア関数 ペナルティ関数法（英語版） 微分可能 ラグランジュの未定乗数法 逐次二次計画法 連続線形計画（英語版）
凸最適化	凸縮小化 切除平面法（英語版、デンマーク語版、ドイツ語版、スペイン語版） 簡約勾配法 劣勾配法（英語版） 線型 および 二次 内点法 カチヤン楕円体法 カーマーカーの投影アルゴリズム ベイズ-交換 単体法 改訂シンプレックス法（英語版） 十字法（英語版） レムケの主ピボット操作法（英語版）
組合せ最適化	系列範例 (Paradigms) 近似アルゴリズム 動的計画法 貪欲法 整数計画問題(分枝限定法 若しくは 切断) グラフ理論 最小全域木 ベルマン–フォード法 ブルーフカ法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法（英語版） クラスカル法 最大フロー問題 Dinic法（英語版） エドモンズ・カープ フォード・ファルカーソン プッシュリラベル最大流アルゴリズム（英語版）
メタヒューリスティクス	進化的アルゴリズム（進化戦略） 山登り法 局所探索法 焼きなまし法 タブーサーチ ベイスンホッピング法
カテゴリ（最適化 • アルゴリズム） • ソフトウェア（英語版）