メロートラの予測子修正子法とは？わかりやすく解説

メロートラの予測子修正子法（メロートラのよそくししゅうせいしほう、英: Mehrotra's predictor–corrector method）とは数理最適化において線形計画問題に対する内点法の一種である。1989年にサンジェイ・メロートラによって提案された^[1]。

予測子修正子法では探索方向を求めるためにコレスキー分解を用いて大規模な行列を必要に応じて計算し、反復する内点法である。行列の分解ステップでは計算量の大きいステップである。このことは行列した分解を複数回の反復を通じて使用することで実用上の計算量を抑えることができる。

予測子修正子法の各反復では予測方向・修正方向の二つの探索方向を求めるために同一のコレスキー分解した行列を使用する。

予測子修正子法の基本的なアイデアとして、始めに最適解への探索方向を線形の方程式系を解いて決定する（予測子）。続いて最適解への探索方向に対するステップサイズを求めて中心への探索方向も求める。このとき中心方向と2次の方程式系によって決定される（修正子）。

予測子修正子法の探索方向は予測方向・修正方向の和をとることで求まる。

メロートラの予測子修正子法は大変実践向きの内点法ではあるが、多項式オーダーの証明は今のところされていない^[2]。修正方向では予測方向で用いたコレスキー分解した行列をもう一度使用して計算することから効率よく反復を行うことができるため、他の内点法と比べても計算にかかる時間はわずかとされている。しかしながら、反復における追加の計算も最適解に到達するまでに必要な反復回数も十分減少することから、計算にかかる全体の時間も大きなものではないとされる。また最適解に十分に近い点では非常に早く収束することが知られている。