ドッグレッグ法

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

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

定式化 

を所与として、次の形式の最小二乗問題を考える。

 

パウエルのドッグレッグ法は最適点に収束する点列をにより構築することでこの問題を解く。各反復において、ガウス・ニュートン法ステップは次のように与えられる。

 

ここで、はヤコビ行列を表わす。一方、最急降下方向は次式のように与えられる。

 

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

 

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

 

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

 ガウス・ニュートンステップが信頼領域内にある場合()、
 と最急降下ステップの両方が信頼領域の外にある場合()、
 は信頼領域の外側にあるが、は内側にある場合、をについてを満たすよう解いたもの（ドッグレッグステップ）

出典

参照文献

外部リンク

関連項目 
 ガウス・ニュートン法
 準ニュートン法

 

最適化アルゴリズムとメソッド
最小二乗法