アフィンスケーリング法

アフィンスケーリング法は線形計画問題の実行可能領域の（端点を辿る単体法と違って、）内部を厳密に移動する内点法の一種である。

アフィンスケーリング法（アフィンスケーリングほう、アフィン変換法、アフィンへんかんほう、テンプレート:Lang-en-short）とは、数理最適化において線形計画問題を解くためのアルゴリズムである。これは内点法であり、1967年ソヴィエト連邦の数学者 I.I.Dikin によって編み出され、1980年代にアメリカ合衆国で再発見された解法である。

歴史

アフィンスケーリング法は1967年、Doklady Akademii Nauk SSSR にロシア科学アカデミー、エネルギーシステム研究所テンプレート:Efnの I.I.Dikin によって提案、1974年に収束性を証明されて以降テンプレート:仮リンクを辿ることとなるテンプレート:R。Dikin の業績は線形計画問題に対する初の実用的多項式時間アルゴリズムであるカーマーカー法が1984年に編み出されるまでほとんど知られることがなかった。このカーマーカー法の目新しさと計算複雑性によってカーマーカー法の高度な技法をより単純な技法で実現するための研究に多くの研究者が興味を持ち始めた。

以降、カーマーカー法の類似の解法がいくつかのグループによって独立に提案された。IBMの E.R.Barnes、AT&Tのテンプレート:仮リンクらのグループ、その他いくつかのチームがカーマーカー法の射影変換をアフィン変換に置き換えた内点法を提案した。これらの提案から数年が経ってから、彼らによって提案されたアフィンスケーリング法が実際には Dikin の研究の再発見に過ぎなかったことが判明した。再発見を通じて Barnes および Vanderbei らのみがアフィンスケーリング法の収束性について示すことができた。またカーマーカーもアフィンスケーリング法を編み出していたが、カーマーカー法と同様の収束性をもつ解法であると誤った認識をしていたとされているテンプレート:Rp。

アルゴリズム

アフィンスケーリング法は二つの段階から構成されており、一段階目で実行可能点を求めて、二段階目は実行可能領域の内部を厳密に通って真の最適解を求める。

二つの段階ともに線形計画問題の等式標準形について考える:

minimize テンプレート:Math

subject to テンプレート:Math, テンプレート:Math.

アフィンスケーリング法は実行可能領域の内部の点を生成する反復法である。特徴として一回の反復で元の問題をスケーリングした問題においてアフィンスケーリング方向を求めて、元の問題へ戻る。現在の反復点が実行可能領域の境界に近い内点である場合でもアフィン変換によって十分なステップをとることができるテンプレート:Rテンプレート:Rp。

具体的には、アフィンスケーリング法の肝となる反復手順について説明する。ここでテンプレート:Mvar、テンプレート:Mvar、テンプレート:Mvarが与えられたとする。初期解は テンプレート:Math とし実行可能（テンプレート:Math）であるとする。許容誤差を テンプレート:Mvar、ステップサイズを テンプレート:Mvar とする。このとき反復手順はテンプレート:Rテンプレート:Rp:

• テンプレート:Mvar を対角成分に並べた対角行列を テンプレート:Mvar とする。
• 双対変数ベクトルを求める:

  $w^k=(A{D}_k^2{A}^{\mathrm{T}}{)}^{-1}A{D}_k^{2}c$

• 双対問題の制約に対応するテンプレート:仮リンクの値を知るために被約費用ベクトルを求める:

  $r^k=c-A^{\mathrm{T}}{w}^k$

• もし $r^k>0$ かつ ${\mathrm{𝟏}}^{\mathrm{T}}{D}_k{r}^k<\epsilon$ ならば、現在解 テンプレート:Math は テンプレート:Mvar近似最適解である。
• もし $-D_k{r}^k\ge 0$ ならば、問題は非有界である。
• 更新する: $x^{k+1}=x^k-\beta \frac{D_k^2{r}^k}{\Vert D_k{r}^k\Vert }$

初期化

一段階目では元の問題の初期解を求めるために追加の変数 テンプレート:Mvar を導入して人工問題を作成する。初期解 テンプレート:Math を任意の成分が厳密に正の値をとるものとする。ただしこれは元の問題の実行可能解である必要はない。テンプレート:Math の実行可能性は以下の式によって判定することができる:

$v=b-A{x}^0$.

もし テンプレート:Math であるならば、これはすなわち右辺が元の問題の制約と一致することから テンプレート:Math は実行可能である。そうでなければ、以下の人工問題を解く。

minimize テンプレート:Math

subject to テンプレート:Math, テンプレート:Math, テンプレート:Math.

この人工問題は以下の値が実行可能内点解であることが容易に分かるので、後は上記で説明した反復法によって最適解を求めるテンプレート:Efn:

$\left(\begin{array}{c}{x}^0\\ 1\end{array}\right)$

人工問題の最適解を以下のように置く:

$\left(\begin{array}{c}{x}^{*}\\ u^{*}\end{array}\right)$.

もし テンプレート:Mathであるならば、元の問題の（厳密には実行可能内点解ではないが）実行可能解である。 もし テンプレート:Math であるならば、元の問題は実行不可能であるテンプレート:Rテンプレート:Rp。

分析

アフィンスケーリング法は実装が容易である代わりに収束性の分析が容易でないとされている。アフィンスケーリング法の収束性はステップサイズ テンプレート:Mvar によって決まる。ステップサイズが テンプレート:Math のとき、Vanderbeiのアフィンスケーリング法は収束することが知られている。一方、ステップサイズが テンプレート:Math のときはある問題に対して最適値でない値に収束することが知られているテンプレート:Rテンプレート:Rp。他のアフィンスケーリング法についてもステップサイズ テンプレート:Math のときに規模の小さな問題に対しても複雑な挙動を示すことが知られている。

参考文献

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

外部リンク

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