内点法（ないてんほう、）とは、連続最適化問題のアルゴリズムであり、カーマーカー法に触発されて生まれた多くの手法の総称である。実行可能領域の内部を経由して、最適解に収束するのが特徴である。また、大規模問題に対しては計算効率が良い点や非線型問題にも対応できる点で、シンプレックス法よりも優れているといえる。内点法は、点列を生成する方法によって、アフィン変換法、ポテンシャル減少法、解析的中心追跡法、パス追跡法などに分類される。また、扱う問題によっては、与えられた問題を直接扱う方法（主内点法、）、その双対問題を扱う方法（双対内点法、）、主問題と双対問題を同時に解く方法（主双対内点法、）に分けられる。
主双対内点法による非線型最適化 主双対内点法のアイディアは単純で、制約付き非線型最適化問題にも応用が可能である。ここでは単純のために制約式が全て不等式で与えられる非線型最適化問題について考える。
最小化: 条件:
この最適化問題の対数バリア関数は次のようになる。
ここでは正のスカラーで、時に「バリア・パラメータ」とも呼ばれる。このが0に収束していくと、が最適解に収束していく。
前述のバリア関数の勾配は
となる。ただし、は元の関数の勾配であり、はの勾配を表す。
主値に加えて、双対値をラグランジュ乗数として導入する。
この条件は時に摂動相補性条件とも呼ばれる。式(4)を式(3)に適用することにより以下を得る。
ただし、行列は制約のヤコビ行列である。
式(5)が表しているのは関数の勾配が制約式の勾配により張られる部分空間の中に存在するということである。このとき小さなによる摂動相補性条件は、最適解がの境界付近に存在するか、もしくは制約の勾配がほとんど0であるということを表している。
式(4)および式(5)に対してニュートン法を用いてを更新していくことを考えると、その更新幅は次の線型方程式の解として与えられる。
ただし行列は関数のヘッセ行列であり、対角行列はを対角成分に持つ。また、はなる対角行列である。
式(1), (4), およびから
がそれぞれのステップに課される。この条件を保つために、適切なステップ更新幅を選び、
とすることで、最適解に向かって収束していく。
分類 線形計画法 発表年 名称 考案者 計算量 補足 出典 1967年 アフィン変換法 I.I.ディキン 線形計画問題に対する内点法として始めて提案された解法である。1988年に米国において再発見された。 1984年 カーマーカーの射影変換法（カーマーカー法） ナレンドラ・カーマーカー 反復回数: 総計算量: 内点法として初めて多項式オーダーで動作することが証明された解法である。カーマーカー法が提案されたことによって、内点法が盛んに研究されるようになった。 1986年 アフィン変換法 バーンズ 1986年 アフィン変換法 Vanderbei、Meketon、Freedman 1987年 パス追跡法（主双対内点法） 小島政和、水野眞治、吉瀬章子 主双対内点法の一種。ステップ幅の決定に近傍 を使用する。 1987年 パス追跡法（主双対内点法） 田辺國士 主双対内点法の一種。ステップ幅の決定に近傍 を使用する。 1988年 リネガーの解析的中心追跡法 J.リネガー 反復回数: 1992年 メロートラの予測子・修正子法 サンジェイ・メロートラ 非常に効率よく解くことのできる解法として知られている内点法。非実行可能型の主双対内点法に分類される。
凸二次計画問題・線形相補性問題 発表年 名称 考案者 計算量 補足 出典 1989年 パス追跡法 小島政和、水野眞治、吉瀬章子 反復回数: 実行可能型内点法。 1991年 ポテンシャル減少法 小島政和、水野眞治、吉瀬章子 反復回数: 実行可能型内点法。
実装 IPOPT
脚注
注釈
出典
参考文献