アフィン変換法とは？わかりやすく解説

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

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

歴史

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

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

アルゴリズム

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

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

minimize

c \cdot x

subject to

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$

カテゴリ（最適化 • アルゴリズム） • ソフトウェア

[注釈 1]

[1]

[2]

[3]

[4]

[5]

一般	バリア関数ペナルティ関数法
微分可能	ラグランジュの未定乗数法拡張ラグランジュ関数法逐次二次計画法逐次線形計画法


	Copyright (C) 2025 （社）日本オペレーションズ・リサーチ学会 All rights reserved.
	All text is available under the terms of the GNU Free Documentation License. この記事は、ウィキペディアのアフィンスケーリング法 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

アフィン変換法とは？ わかりやすく解説

アフィン変換法

アフィンスケーリング法

歴史

アルゴリズム

「アフィン変換法」の関連用語

アフィン変換法とは？わかりやすく解説