アフィンスケーリング法

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

歴史

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

以降、カーマーカー法の類似の解法がいくつかのグループによって独立に提案された。IBMの E.R.Barnes^[2]、AT&Tのロバート・ヴァンダーベイ（英語版）らのグループ^[3]、その他いくつかのチームがカーマーカー法の射影変換をアフィン変換に置き換えた内点法を提案した。これらの提案から数年が経ってから、彼らによって提案されたアフィンスケーリング法が実際にはディキンの研究の再発見に過ぎなかったことが判明した^[1]^[4]。再発見を通じて Barnes およびヴァンダーベイらのみがアフィンスケーリング法の収束性について示すことができた。またカーマーカーもアフィンスケーリング法を編み出していたが、カーマーカー法と同様の収束性をもつ解法であると誤った認識をしていたとされている^[5]^:346。

アルゴリズム

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

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

$\min$		$c^{\top }x$
$\mathrm {s.t.}$		$Ax=b$
		$x\geq 0$

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

具体的には、アフィンスケーリング法の肝となる反復手順について説明する。ここで $A$ 、 $b$ 、 $c$ が与えられたとする。初期解は $x 0 > 0$ とし実行可能（ $Ax 0 = b$ ）であるとする。許容誤差を $ε$ 、ステップサイズを $β$ とする。このとき反復手順は^[1]^:111:

$x k$ を対角成分に並べた対角行列を $D k$ とする。
双対変数ベクトルを求める:
$w^{k}=(AD_{k}^{2}A^{\operatorname {T} })^{-1}AD_{k}^{2}c$
双対問題の制約に対応するスラック変数（英語版）の値を知るために被約費用ベクトルを求める:
$r^{k}=c-A^{\operatorname {T} }w^{k}$
もし $r^{k}>0$ かつ $\mathbf {1} ^{\operatorname {T} }D_{k}r^{k}<\varepsilon$ ならば、現在解 $x k$ は $ε$ 近似最適解である。
もし $-D_{k}r^{k}\geq 0$ ならば、問題は非有界である。
更新する: $x^{k+1}=x^{k}-\beta {\frac {D_{k}^{2}r^{k}}{\|D_{k}r^{k}\|}}$

初期化

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

v=b-Ax^{0}

.

もし $v = 0$ であるならば、これはすなわち右辺が元の問題の制約と一致することから $x 0$ は実行可能である。そうでなければ、以下の人工問題を解く。

$\min$		$u$
$\mathrm {s.t.}$		$Ax+uv=b$
		$x\geq 0$
		$u\geq 0$

この人工問題は以下の値が実行可能内点解であることが容易に分かるので、後は上記で説明した反復法によって最適解を求める^{[注釈 2]}:

{\begin{pmatrix}x^{0}\\1\end{pmatrix}}

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

{\begin{pmatrix}x^{*}\\u^{*}\end{pmatrix}}

.

もし $u * = 0$ であるならば、元の問題の（厳密には実行可能内点解ではないが）実行可能解である。もし $u * > 0$ であるならば、元の問題は実行不可能である^[5]^:343。

分析

アフィンスケーリング法は実装が容易である代わりに収束性の分析が容易でないとされている。アフィンスケーリング法の収束性はステップサイズ $β$ によって決まる。ステップサイズが $β ≤ .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}2/3$ のとき、ヴァンダーベイのアフィンスケーリング法は収束することが知られている。一方、ステップサイズが $β > 0.995$ のときはある問題に対して最適値でない値に収束することが知られている^[5]^:342。他のアフィンスケーリング法についてもステップサイズ $β > 2 / 3$ のときに規模の小さな問題に対しても複雑な挙動を示すことが知られている^[6]^[7]。