内点法

内点法（ないてんほう、テンプレート:Lang-en-short）とは、連続最適化問題のアルゴリズムであり、カーマーカー法に触発されて生まれた多くの手法の総称である。実行可能領域の内部を経由して、最適解に収束するのが特徴である。また、大規模問題に対しては計算効率が良い点や非線型問題にも対応できる点で、シンプレックス法よりも優れているといえる。内点法は、点列を生成する方法によって、アフィン変換法、ポテンシャル減少法、解析的中心追跡法、パス追跡法などに分類されるテンプレート:Sfn。また、扱う問題によっては、与えられた問題を直接扱う方法（主内点法、テンプレート:Lang-en-short）、その双対問題を扱う方法（双対内点法、テンプレート:Lang-en-short）、主問題と双対問題を同時に解く方法（主双対内点法、テンプレート:Lang-en-short）に分けられるテンプレート:Sfn。

主双対内点法による非線型最適化

主双対内点法のアイディアは単純で、制約付き非線型最適化問題にも応用が可能である。ここでは単純のために制約式が全て不等式で与えられる非線型最適化問題について考える。

最小化: $f(x)$

条件: $c(x)\ge 0,x\in {ℝ}^n,c(x)\in {ℝ}^m(1)$

この最適化問題の対数バリア関数は次のようになる。

$B(x,\mu )=f(x)-\mu \sum _{i=1}^m\ln (c_i(x))(2)$

ここで$\mu$は正のスカラーで、時に「バリア・パラメータ」とも呼ばれる。この$\mu$が0に収束していくと、$B(x,\mu )$が最適解に収束していく。

前述のバリア関数の勾配は

$g_b=g-\mu \sum _{i=1}^m\frac{1}{c_i(x)}\mathrm{\nabla }{c}_i(x)(3)$

となる。ただし、$g$は元の関数$f(x)$の勾配であり、$\mathrm{\nabla }{c}_i$は$c_i$の勾配を表す。

主値$x$に加えて、双対値$\lambda \in {ℝ}^m$をラグランジュ乗数として導入する。

$\mathrm{\forall }i=1,\dots ,m,c_i(x){\lambda }_i=\mu (4)$

この条件は時に摂動相補性条件とも呼ばれる。式(4)を式(3)に適用することにより以下を得る。

$g-A^T\lambda =0(5)$

ただし、行列$A$は制約$c(x)$のヤコビ行列である。

式(5)が表しているのは関数$f(x)$の勾配が制約式の勾配により張られる部分空間の中に存在するということである。このとき小さな$\mu$による摂動相補性条件は、最適解が$c_i(x)=0$の境界付近に存在するか、もしくは制約$c_i(x)$の勾配$g$がほとんど0であるということを表している。

式(4)および式(5)に対してニュートン法を用いて$(x,\lambda )$を更新していくことを考えると、その更新幅$(p_x,p_{\lambda })$は次の線型方程式の解として与えられる。

$\left(\begin{array}{cc}W& -A^T\\ \mathrm{\Lambda }A& C\end{array}\right)\left(\begin{array}{c}{p}_x\\ p_{\lambda }\end{array}\right)=\left(\begin{array}{c}-g+A^T\lambda \\ \mu 1-C\lambda \end{array}\right)$

ただし行列$W$は関数$B(x,\mu )$のヘッセ行列であり、対角行列$\mathrm{\Lambda }$は$\lambda$を対角成分に持つ。また、$C$は$C_{ii}=c_i(x)$なる対角行列である。

式(1), (4), および$\mu >0$から

$\lambda \ge 0$

がそれぞれのステップに課される。この条件を保つために、適切なステップ更新幅$\alpha$を選び、

$(x,\lambda )\to (x+\alpha p_x,\lambda +\alpha p_{\lambda })$

とすることで、最適解に向かって収束していく。

分類

線形計画法

発表年	名称	考案者	計算量	補足	出典
1967年	アフィン変換法	I.I.Dikin		線形計画問題に対する内点法として始めて提案された解法であるテンプレート:Sfn。1988年に米国において再発見されたテンプレート:Sfnテンプレート:Sfn。	テンプレート:Sfn
1984年	カーマーカーの射影変換法 （カーマーカー法）	ナレンドラ・カーマーカー	反復回数: $O(nL)$ 総計算量: $O(n^{4}L)$	内点法として初めて多項式オーダーで動作することが証明された解法であるテンプレート:Sfn。カーマーカー法が提案されたことによって、内点法が盛んに研究されるようになったテンプレート:Sfn。	テンプレート:Sfn
1986年	アフィン変換法	バーンズ			テンプレート:Sfn
1986年	アフィン変換法	Vanderbei、Meketon、Freedman			テンプレート:Sfn
1987年	パス追跡法 （主双対内点法）	小島政和、水野眞治、吉瀬章子		主双対内点法の一種。ステップ幅の決定に近傍$N_2(\beta )$テンプレート:Efn を使用するテンプレート:Sfn。	テンプレート:Sfn
1987年	パス追跡法 （主双対内点法）	田辺國士		主双対内点法の一種。ステップ幅の決定に近傍$N_{ln}(\beta )$テンプレート:Efn を使用するテンプレート:Sfn。	テンプレート:Sfn
1988年	リネガーの解析的中心追跡法	J.リネガー	反復回数: $O(\sqrt{n}L)$		テンプレート:Sfn
1992年	メロートラの予測子・修正子法	サンジェイ・メロートラ		非常に効率よく解くことのできる解法として知られている内点法テンプレート:Sfn。非実行可能型の主双対内点法に分類されるテンプレート:Sfn。	テンプレート:Sfn

凸二次計画問題・線形相補性問題

発表年	名称	考案者	計算量	補足	出典
1989年	パス追跡法	小島政和、水野眞治、吉瀬章子	反復回数: $O(\sqrt{n}L)$	実行可能型内点法。	テンプレート:Sfn
1991年	ポテンシャル減少法	小島政和、水野眞治、吉瀬章子	反復回数: $O(\sqrt{n}L)$	実行可能型内点法。	テンプレート:Sfn

実装

• IPOPT

参考文献

• テンプレート:Cite book
• テンプレート:Cite book
• テンプレート:Cite book