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