内点法

内点法（ないてんほう、）とは、連続最適化問題のアルゴリズムであり、カーマーカー法に触発されて生まれた多くの手法の総称である。実行可能領域の内部を経由して、最適解に収束するのが特徴である。また、大規模問題に対しては計算効率が良い点や非線型問題にも対応できる点で、シンプレックス法よりも優れているといえる。内点法は、点列を生成する方法によって、アフィン変換法、ポテンシャル減少法、パス追跡法などに分類される。また、扱う問題によっては、与えられた問題を直接扱う方法(主内点法、)、その双対問題を扱う方法(双対内点法、)、主問題と双対問題を同時に解く方法(主双対内点法、)に分けられる。
主双対内点法による非線型最適化.
主双対内点法のアイディアは単純で、制約付き非線型最適化問題にも応用が可能である。ここでは単純のために制約式が全て不等式で与えられる非線型最適化問題について考える。
この最適化問題の対数バリア関数は次のようになる。
ここでformula_4は正のスカラーで、時に「バリア・パラメータ」とも呼ばれる。このformula_4が0に収束していくと、formula_6が最適解に収束していく。
前述のバリア関数の勾配は
となる。ただし、formula_8は元の関数formula_1の勾配であり、formula_10はformula_11の勾配を表す。
主値formula_12に加えて、双対値formula_13をラグランジュ乗数として導入する。
この条件は時に摂動相補性条件とも呼ばれる。式(4)を式(3)に適用することにより以下を得る。
ただし、行列formula_16は制約formula_17のヤコビ行列である。
式(5)が表しているのは関数formula_1の勾配が制約式の勾配により張られる部分空間の中に存在するということである。このとき小さなformula_4による摂動相補性条件は、最適解がformula_20の境界付近に存在するか、もしくは制約formula_21の勾配formula_8がほとんど0であるということを表している。
式(4)および式(5)に対してニュートン法を用いてformula_23を更新していくことを考えると、その更新幅formula_24は次の線型方程式の解として与えられる。
ただし行列formula_26は関数formula_27のヘッセ行列であり、対角行列formula_28はformula_29を対角成分に持つ。また、formula_30はformula_31なる対角行列である。
式(1), (4), およびformula_32から
がそれぞれのステップに課される。この条件を保つために、適切なステップ更新幅formula_34を選び、
とすることで、最適解に向かって収束していく。