ドッグレッグ法

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

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

 定式化 
リンク=//upload.wikimedia.org/wikipedia/commons/thumb/6/69/Powell_dog_leg.svg/220px-Powell_dog_leg.svg.png|サムネイル|ドッグレッグステップの構成
 を所与として、次の形式の最小二乗問題を考える。



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



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



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



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



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

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

 脚注 

 参考文献 





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

 外部リンク 




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