内点法

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

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

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

最小化: $f(x)$

条件: $c(x)\geq 0,x\in \mathbb {R} ^{n},c(x)\in \mathbb {R} ^{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)}}\nabla c_{i}(x)~~~~(3)$

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

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

$\forall i=1,\ldots ,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 })$は次の線型方程式の解として与えられる。

${\begin{pmatrix}W&-A^{T}\\\Lambda A&C\end{pmatrix}}{\begin{pmatrix}p_{x}\\p_{\lambda }\end{pmatrix}}={\begin{pmatrix}-g+A^{T}\lambda \\\mu 1-C\lambda \end{pmatrix}}$

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

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

$\lambda \geq 0$

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

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

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

実装

• IPOPT

参考文献

• 福島雅夫『数理計画入門』朝倉書店、1996年。ISBN 978-4254280043。 
• 福島雅夫『非線形最適化の基礎』朝倉書店、2001年。ISBN 978-4254280012。