内点法

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

内点法(ないてんほう、: 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_ic_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}

ただし行列Wは関数f(x)ヘッセ行列であり、対角行列\Lambda\lambdaを対角成分に持つ。

したがって、式(1), (4)から

 \lambda \geq 0

がそれぞれのステップに課される。適切なステップ更新幅\alphaを選び、

(x, \lambda) \rightarrow (x + \alpha p_x, \lambda + \alpha p_\lambda)

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

実装[編集]

参考文献[編集]