内点法

内点法#

  • 読み: ないてんほう

  • 英名: Interior Point Method

内点法は 1967 年 Dikin が線形計画問題に対する有効な解法として提案した.ただし,当時は広く知られることは無く,1984 年に Karmarkar が同様な手法を提案した時の方が研究者に与えたインパクトは比較にならないほど大きいものであった.なお,Karmarkar の提案した手法に関しては,特許取得騒動など手法そのもの以外に関する話題が多いことでも知られている.

内点法では実行可能領域の内部を探索し,点列を逐次生成することで解を求めている.これは,実行可能領域の端点を辿る事で解を求めている単体法の特徴とは大きく異なるものである.なお,Karmarkar の提案以降多くの内点法のアルゴリズムが提案されているが有力なものとしては主双対内点法がある.また,内点法の考え方を線形計画問題以外の問題に適用する研究が進み,現在では非線形計画問題や半正定値計画問題に対する内点法が知られている.

関連