内点法

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

[編集] 主双対内点法による非線形最適化

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

最小化: $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_y \end{pmatrix} = \begin{pmatrix} -g + A^T \lambda \\ \mu 1 - C \lambda \end{pmatrix}$