メロートラの予測子修正子法

メロートラの予測子修正子法

メロートラの予測子修正子法（Mehrotra's predictor-corrector method）は、線形計画問題に対する数理最適化手法の一種であり、内点法に分類される。この手法は1989年にサンジェイ・メロートラによって提案され、以降、多くの最適化問題において効果的に利用されるようになった。特に、行列のコレスキー分解を活用し、効率的に大規模な線形計画問題の解決を図る点がその特徴である。

基本的な考え方

この手法は、予測子としての探索方向を最初に計算し、その後修正子としての探索方向を求める。具体的には、最初に線形方程式系を解くことで最適解への予測方向を決定し、その後、探索方向に関連するステップサイズを決定して中心への探索方向を求める。この探索方向は予測方向と修正方向の組み合わせにより得られる。

メロートラの予測子修正子法は、特に反復計算において、予測方向と修正方向の計算に同じコレスキー分解した行列を再利用することによって、計算の効率性が高められる。このため従来の内点法に比べ、全体の計算時間は短縮され、最適解に迅速に近づくことが可能となる。

導出の流れ

メロートラの手法の導出は、NocedalとWrightによって整理されており、特に次のようなKKT条件が導入される。線形計画問題を標準形に書き換え、最適解を求めるための必要条件を調べる。この最適化問題では、目的関数が最小化され、制約条件を満たす解を見つけることが求められる。このような問題に対して、KKT条件は次のように表現される：

• - Lagrangeの勾配条件
• - 実行可能条件
• - 補完条件

これにより、最適解を求めるための数学的な枠組みが整う。

予測・中心化・修正の流れ

予測子修正子法では、まずアフィンスケーリング方向を見つけ、次に修正方向を求めるための中心化ステップが行われる。この際、最適解への接近を示す双対ギャップを利用し、中心化パラメータを調整して安定した収束を図る。アフィンスケーリング方向の修正においては、相補性条件に基づき追加の修正が行われ、最終的に中心化および修正された探索方向が集約されて採用される。

このプロセスを経て、最適解に向かう効率的な計算が進められ、特に最適点に近い場合には収束速度が高まることが観察される。

二次計画問題への応用

メロートラの内点法は、本来線形計画問題用の手法であるが、その基本的な構造は二次計画問題にも適用可能である。この柔軟さが、メロートラ法の大きな利点の一つとも言える。特に、数理最適化の分野で様々な問題に対する実用的かつ効率的な解法を提供する能力が評価されている。

結論

メロートラの予測子修正子法は、内点法の中でも特に実用的な手法であり、計算効率の観点からも優れた特性を持っている。多くの最適化のニーズに応えるこの手法は、今後も幅広い応用が期待される。

もう一度検索