ドッグレッグ法のソースを表示

{{翻訳直後|[[:en:Special:Permalink/1084557811|en: Powell's dog leg method]]|date=2022年9月}}
'''ドッグレッグ法'''（ドッグレッグほう、{{Lang-en-short|dog leg method}}）または'''パウエルのドッグレッグ法'''（パウエルのドッグレッグほう、{{Lang-en-short|Powell's dog leg method}}）は、[[1970年]]に{{Ill2|マイケル・J・D・パウエル|en|Michael J. D. Powell}}によって導入された、[[非線形最小二乗法|非線形最小二乗]]問題を解くための[[反復法 (数値計算)|反復]]的[[数理最適化|最適化]]アルゴリズムである{{sfn|Powell|1970}}。[[レーベンバーグ・マルカート法]]と同様に[[ガウス・ニュートン法]]と[[最急降下法|勾配降下]]法とを組み合わせた解法であるが、[[信頼領域]]を明示的に使用する。各反復において、ガウス・ニュートン法により算出されたステップが信頼領域内にある場合は、それを使用して現在の解を更新する。ガウス・ニュートン法により算出されたステップが信頼領域外に出てしまう場合、コーシー点と呼ばれる最急降下方向に沿った[[損失関数|目的関数]]の最小点を探す。コーシー点が信頼領域の外側にある場合は、信頼領域の境界まで切りつめられ、新しい解として採用される。コーシー点が信頼領域内にある場合、新しい解は、信頼領域の境界と、コーシー点とガウス・ニュートン法によるステップを結ぶ線（ドッグレッグステップ）との交点を次の解とする{{sfn|Yuan|2000}}。

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

== 定式化 ==
[[ファイル:Powell_dog_leg.svg|リンク=//upload.wikimedia.org/wikipedia/commons/thumb/6/69/Powell_dog_leg.svg/220px-Powell_dog_leg.svg.png|サムネイル|ドッグレッグステップの構成]]
<math>f_i: \mathbb{R}^n \to \mathbb{R}</math>を所与として、次の形式の[[最小二乗法|最小二乗]]問題を考える。

: <math>
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
</math>

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

: <math>
\boldsymbol{\delta_\mathrm{gn}} = - \left( \boldsymbol{J}^\top \boldsymbol{J} \right)^{-1} \boldsymbol{J}^\top \boldsymbol{f}(\boldsymbol{x})
</math>

ここで、<math>\boldsymbol{J} = \left( \frac{\partial{f_i}}{\partial{x_j}} \right)</math>は[[ヤコビ行列]]を表わす。一方、[[最急降下法|最急降下]]方向は次式のように与えられる。

: <math>
\boldsymbol{\delta_\mathrm{sd}} = - \boldsymbol{J}^\top \boldsymbol{f}(\boldsymbol{x})
</math>

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

: <math>
\begin{align}
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{align}
</math>

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

: <math>
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}
</math>

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

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

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 参考文献 ==
* {{Cite book|last=Lourakis|first=M.L.A.|last2=Argyros|first2=A.A.|title=Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1|chapter=Is Levenberg-Marquardt the most efficient optimization algorithm for implementing bundle adjustment?|year=2005|pages=1526-1531|doi=10.1109/ICCV.2005.128|isbn=0-7695-2334-X}}
* {{Cite conference|title=A review of trust region algorithms for optimization|book-title=Iciam|year=2000|volume=99|last=Yuan|first1=Ya-xiang}}
* {{Cite book|first=M.J.D.|last=Powell|chapter=A new algorithm for unconstrained optimization|editor-first=J.B.|editor-last=Rosen|editor2-first=O.L.|editor2-last=Mangasarian|editor3-first=K.|editor3-last=Ritter|title=Nonlinear Programming|publisher=Academic Press|location=New York|year=1970|pages=31–66|ref=harv}}
* {{Cite book|first=M.J.D.|last=Powell|chapter=A hybrid method for nonlinear equations|editor-first=P.|editor-last=Robinowitz|title=Numerical Methods for Nonlinear Algebraic Equations|publisher=Gordon and Breach Science|location=London|year=1970|pages=87–144}}

== 関連項目 ==
* [[ガウス・ニュートン法]]
* [[準ニュートン法]]

== 外部リンク ==
* {{Cite web |url=https://mathworks.com/help/optim/ug/equation-solving-algorithms.html |title=Equation Solving Algorithms |publisher=MathWorks |access-date=2022-09-17}}

{{最適化アルゴリズム}} 

{{DEFAULTSORT:とつくれつくほう}}
[[Category:最適化アルゴリズムとメソッド]]
[[Category:最小二乗法]]