アフィンスケーリング

数学的最適化において、アフィンスケーリングは線形計画問題を解くアルゴリズムです。具体的には、 1967 年にソビエトの数学者 II Dikinによって発見され、 1980 年代半ばに 米国で再発明された内点法です。

アフィンスケーリングには、数々の発見の歴史がある。1967年、ロシア科学アカデミーのエネルギーシステム研究所（当時はソ連科学アカデミーのシベリアエネルギー研究所）のIIディキンが初めてアフィンスケーリングの収束を証明した。続いて1974年にその収束性が証明された。 ^{[1]ディキンの研究は、1984年に}カルマルカールのアルゴリズムが発見されるまで、ほとんど注目されなかった。カルマルカールのアルゴリズムは、線形計画法のための最初の実用的な多項式時間アルゴリズムであった。カルマルカールの方法の重要性と複雑さから、数学者はより単純なバージョンを探すことになった。

その後、いくつかのグループが独立してカルマーカのアルゴリズムの変種を考案した。IBMのERバーンズ^[2]、AT&TのRJヴァンダーベイ率いるチーム^[3]、その他数人がカルマーカが使用した射影変換をアフィン変換に置き換えた。数年後、この「新しい」アフィンスケーリングアルゴリズムは実際には数十年前のディキンの結果の再発明であることがわかった。^{[1] [4]}再発見者のうち、バーンズとヴァンダーベイらだけがアフィンスケーリングの収束特性の分析を成し遂げた。この時期にアフィンスケーリングも考案していたカルマーカは、それが自身のアルゴリズムと同じくらい速く収束すると誤って信じていた。^{[5] : 346}

アフィン スケーリングは 2 つのフェーズで動作します。最初のフェーズでは最適化を開始する実行可能なポイントを見つけ、2 番目のフェーズでは実行可能な領域内に厳密に留まりながら実際の最適化を実行します。

どちらのフェーズでも、等式形式の線形計画法を解きます。

c ⋅ xを最小化する

Ax = b、x ≥ 0を条件とする。

これらの問題は反復法を使用して解決されます。反復法は概念的には、問題の実行可能領域内に厳密に点の軌跡をプロットし、問題の再スケールバージョンで投影された勾配降下ステップを計算し、ステップを元の問題にスケールバックすることで進行します。スケーリングにより、検討中の点が実行可能領域の境界に近い場合でも、アルゴリズムが大きなステップを実行し続けることができるようになります。^{[5] : 337}

形式的には、アフィンスケーリングの中核となる反復法は、入力としてA、b、c 、厳密に実行可能な初期推定値x ⁰ > 0 （すなわち、 Ax ⁰ = b）、許容値ε、ステップサイズβを取り、次に^[1]を反復して進める^：111

• D _{k を}対角行列とし、その対角成分はx ^kとします。
• 双対変数のベクトルを計算します。

  ${\displaystyle w^{k}=(AD_{k}^{2}A^{\operatorname {T} })^{-1}AD_{k}^{2}c.}$

• 双対における不等式制約の 緩みを測定する縮小コストのベクトルを計算します。

  ${\displaystyle r^{k}=cA^{\オペレータ名 {T} }w^{k}.}$

• かつの場合、現在の解x ^kはε最適です。${\displaystyle r^{k}>0}$${\displaystyle \mathbf {1} ^{\operatorname {T} }D_{k}r^{k}}}$
• の場合、問題は無制限です。${\displaystyle -D_{k}r^{k}\geq 0}$
• アップデート${\displaystyle x^{k+1}=x^{k}-\beta {\frac {D_{k}^{2}r^{k}}{\|D_{k}r^{k}\|}}}$

フェーズIの初期化では、追加の変数uを持つ補助問題を解き、その結果を使用して元の問題の初期点を導きます。x 0^{を任意の正の点とします。元の問題}に対して実行可能である必要はありません。x ⁰の実行不可能性は、ベクトルによって測定されます 。

${\displaystyle v=b-Ax^{0}}$。

v = 0の場合、x ^{0 は}実行可能である。実行可能でない場合、フェーズIは補助問題を解く。

最小化

Ax + uv = b、x ≥ 0、u ≥ 0を条件とする。

^{この問題は、上記の反復アルゴリズム[a]}によって解くのに適した形式を持ち、

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

は、それに対する実行可能な初期点である。補助問題を解くと、

${\displaystyle {\begin{pmatrix}x^{*}\\u^​​{*}\end{pmatrix}}}$。

u ^* = 0の場合、元の問題ではx ^* ≥0は実行可能（必ずしも厳密に内部的ではない）であるが、u ^* > 0の場合、元の問題は実行不可能である。^{[5] : 343}

アフィンスケーリングは、述べるのは簡単ですが、分析するのは困難です。その収束はステップサイズβに依存します。ステップサイズβ ≤ ⁠の場合、2/3⁠、アフィンスケーリングのVanderbeiの変種は収束することが証明されているが、 β > 0.995の場合、準最適値に収束する例題が知られている。 ^{[5] : 342 アルゴリズムの他の変種は、} β > ⁠の場合でも小さな問題でカオス的な挙動を示すことが示されている2/3⁠ . ^{[6] [7]}

• Adler, Ilan; Monteiro, Renato DC (1991). 「線形計画問題におけるアフィンスケーリング連続軌道の限界挙動」(PDF) .数学プログラミング. 50 (1–3): 29–51. doi :10.1007/bf01594923. S2CID  15748327.
• Saigal, Romesh (1996). 「主アフィンスケーリング法の簡単な証明」(PDF) . Annals of Operations Research . 62 : 303–324. doi :10.1007/bf02206821. hdl : 2027.42/44263 . S2CID  14046399.
• Tseng, Paul; Luo, Zhi-Quan (1992). 「アフィンスケーリングアルゴリズムの収束について」(PDF) .数理計画. 56 (1–3): 301–319. CiteSeerX  10.1.1.94.7852 . doi :10.1007/bf01580904. hdl :1721.1/3161. S2CID  13714272.

• 「15.093 最適化手法、講義 21: アフィン スケーリング アルゴリズム」(PDF)。MIT OpenCourseWare。2009年。
• ミッチェル、ジョン (2010 年 11 月)。「内点法」。レンセラー工科大学。
• 「講義 6: 内点法」(PDF)。NCTU OpenCourseWare 。 2016 年 10 月 11 日にオリジナル(PDF)からアーカイブ。2016 年 2 月 6 日に取得。