ドッグレッグ法

ウィキペディア

ドッグレッグ法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/05/26 03:54 UTC 版)

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

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

定式化

ドッグレッグステップの構成

$f_{i}:\mathbb {R} ^{n}\to \mathbb {R}$

Optimization computes maxima and minima.

非線形（制約付き）

凸最適化

組合せ最適化

メタヒューリスティクス

• 進化的アルゴリズム（進化戦略・遺伝的アルゴリズム）
• 山登り法
• 局所探索法
• 焼きなまし法
• タブーサーチ
• 群知能（ACO・PSO）
• ベイスンホッピング法
• 量子焼きなまし法

• カテゴリ（最適化 • アルゴリズム） • ソフトウェア