ドッグレッグ法

ドッグレッグ法（ドッグレッグほう、）またはパウエルのドッグレッグ法（パウエルのドッグレッグほう、）は、1970年にによって導入された、非線形最小二乗問題を解くための反復的最適化アルゴリズムである。レーベンバーグ・マルカート法と同様、ガウス・ニュートン法と勾配降下法とを組み合わせるが、信頼領域を明示的に使用する。各反復において、ガウス・ニュートン法により算出されたステップが信頼領域内にある場合は、それを使用して現在の解を更新する。ガウス・ニュートン法により算出されたステップが信頼領域外に出てしまう場合、コーシー点と呼ばれる最急降下方向に沿った目的関数の最小点を探す。コーシー点が信頼領域の外側にある場合は、信頼領域の境界まで切りつめられ、新しい解として採用される。コーシー点が信頼領域内にある場合、新しい解は、信頼領域の境界と、コーシー点とガウス・ニュートン法によるステップを結ぶ線（ドッグレッグステップ）との交点を次の解とする。
このアルゴリズムの名前は、ドッグレッグステップの構成がゴルフのドッグレッグホールの形状に似ていることに由来する。
定式化.
formula_1を所与として、次の形式の最小二乗問題を考える。
パウエルのドッグレッグ法は最適点formula_3に収束する点列をformula_4により構築することでこの問題を解く。各反復において、ガウス・ニュートン法ステップは次のように与えられる。
ここで、formula_6はヤコビ行列を表わす。一方、最急降下方向は次式のように与えられる。
目的関数を最急降下方向に沿って線形化すると、以下を得る。
コーシー点におけるパラメータの値を計算するには、最後の表式をに関して微分したものとゼロを結んだ等式を解けばよく、解は次の式で与えられる。
所与の信頼半径formula_10のもと、パウエルのドッグレッグ法では次のように更新ステップformula_11を選択する。