内点法

内点法とは

内点法（英: interior point method）は、連続最適化問題におけるアルゴリズムの一種であり、カーマーカー法に触発されて発展した様々な手法の総称です。その最大の特徴は、実行可能領域の内部を経由しながら、最適解へと収束していく点にあります。

特に、大規模な問題や非線形問題に対しては、シンプレックス法よりも計算効率が高いとされています。これは、内点法が問題の構造をより柔軟に捉え、効率的な探索を可能にするためです。

内点法は、点列を生成する方法によって、いくつかの種類に分類されます。

アフィン変換法: 解の探索において、アフィン変換を利用する方法。
ポテンシャル減少法: ポテンシャル関数を減少させる方向に探索を進める方法。
パス追跡法: 最適解への経路を追跡するように探索を進める方法。

さらに、内点法は扱う問題に応じて、以下の３つに分類することもできます。

主内点法（英: primal interior point method）: 与えられた問題を直接扱う方法。
双対内点法（英: dual interior point method）: 問題の双対問題を扱う方法。
主双対内点法（英: primal-dual interior point method）: 主問題と双対問題を同時に解く方法。

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

主双対内点法は、制約付きの非線形最適化問題に応用できます。ここでは、制約条件がすべて不等式で与えられる以下の問題を考えます。

最小化:
`f(x)`

条件:
`c(x) ≥ 0, x ∈ R^n, c(x) ∈ R^m` (1)

ここで、`f(x)` は最小化したい関数、`c(x)` は制約条件を表します。

この問題に対して、対数バリア関数を導入します。

`B(x, μ) = f(x) - μ Σ[i=1 to m] ln(ci(x))` (2)

ここで、`μ` は正のスカラーであり、バリアパラメータと呼ばれます。`μ` が0に近づくにつれて、`B(x, μ)` の解は元の問題の最適解に近づいていきます。

バリア関数の勾配は次のようになります。

`gb = g - μ Σ[i=1 to m] (1/ci(x)) * ∇ci(x)` (3)

ここで、`g` は `f(x)` の勾配、 `∇ci` は `ci(x)` の勾配です。

さらに、ラグランジュ乗数 `λ ∈ R^m` を導入し、以下の条件を課します。

`∀i = 1, ..., m, ci(x)λi = μ` (4)

この条件は摂動相補性条件と呼ばれます。

式(4)を式(3)に適用すると、以下の式が得られます。

`g - ATλ = 0` (5)

ここで、`A` は制約 `c(x)` のヤコビ行列です。式(5)は、関数 `f(x)` の勾配が制約式の勾配によって張られる部分空間に存在することを示します。

摂動相補性条件は、最適解が `ci(x) = 0` の境界付近に存在するか、制約 `ci(x)` の勾配 `g` がほぼ0であることを意味します。

式(4)と式(5)に対して、ニュートン法を用いて `(x, λ)` を更新することを考えます。更新幅 `(px, pλ)` は、以下の線形方程式の解として求められます。


[ W -A^T ] [ px ] = [ -g + A^Tλ ]
[ ΛA C ] [ pλ ] = [ μ1 - Cλ ]


ここで、`W` はバリア関数 `B(x, μ)` のヘッセ行列、`Λ` は `λ` を対角成分とする対角行列、`C` は `ci(x)` を対角成分とする対角行列です。

`μ > 0`であることから、各ステップで `λ ≥ 0` であることが条件となります。この条件を保つために、適切なステップ幅 `α` を選び、以下のように更新します。

`(x, λ) → (x + αpx, λ + αpλ)`

このプロセスを繰り返すことで、解が最適解へと収束していきます。

実装

内点法の実装には、様々なライブラリやソルバーが利用可能です。例えば、非線形最適化ソルバーとして有名なIPOPTなどが挙げられます。

参考文献

内点法に関するより詳しい情報は、最適化に関する専門書や論文を参照してください。

もう一度検索