アフィンスケーリング法について

質問

参考にしている文献
（http://www.me.titech.ac.jp/~mizu_lab/suuti_kougi1.3.pdf）

線形計画問題において、等式標準形の線形計画問題は、
　目的：ｃTｘ　→　最小
　条件：Ａｘ＝ｂ、ｘ＞＝０　　・・・　（１）
となる。

現時点の点をｘ_t　とする。
（１）の条件では、実行可能領域が多面体になるので、それをｘ_tを中心とする楕円体で近似する。そして、楕円体の中で目的関数を最小にする方向にｘ_tを更新する。
というのがアフィンスケーリング法の原理だと思っています。
自分の中では、添付した図のような感じだと思っています。

参考文献では、（１）から楕円体の近似を行っていますが、なぜこの形になるのでしょうか？イメージが浮かびません。

　目的：ｃTｄ　→　最小
　条件：Ａｄ＝０、ｄTＧｄ＝β^2

まず、ｄTＧｄ＝β^2　が楕円を表しているのでしょうか？
楕円の標準形は、
　ｘ^2 / a^2　＋　ｙ^2 / ｂ^2　＝　１
のように表されますが、ｄTＧｄ＝β^2　が楕円になるのがどうもよく分かりません。

また、Ａｄ＝０という条件は、どういう意味なのでしょうか？
ｄが楕円曲線上にあるということでしょうか？

回答よろしくお願いします。

回答No.1

PRFRD · ベストアンサー

図の理解は大変 good で，アルゴリズムはその図の通りに動作します．

ただ，普通はそれを「多面体を近似している」とは解釈せず，
単に「探索方向を楕円体上で決定する」と見ると思います．
（そのほうが一般的ですし，あんまり良い近似にもなっていないので）

さて，以下本題です．dT G d = β^2 が楕円体をあらわしていることは簡単で，
G は正定値対称行列なので，適当な直交行列 P を用いて
　PT G P = diag(a1, ..., an)　(a1, ..., an > 0)
と対角化することができます．x = P d と座標変換すれば
　xT G x = a1 x1^2 + ... + an xn^2 = β^2
となって，スケーリングの仕方は違いますが，楕円体の標準形になっています．

次に A d = 0 の意味ですが，質問者さんの図を見れば分かるように，
「現在の実行可能解 x_t を d だけ進めた
　新しいベクトル x_t + d もまた実行可能になってほしい」
ので，A d = 0 はそれを保証するための条件です．
同じことですが，x_t + d が多面体内にある，という条件です．

補足

回答ありがとうございました。
回答をみて、理解できました。

また、なぜ「アフィン変換」する必要があるのでしょうか？
アフィン変換は、スケーリング・回転することなのは知っていますが、そうする必要がある理由が分かりません。なにも変換しないと解けないのでしょうか？

補足回答お願いします。

回答No.3

PRFRD

No.2のコメントに対して：
なんか色々ダメです．
多分 No.1 で私が x という記号を使ったのが悪かったのですが，
No.1 の x は，現在居る点 x_t とは無関係の記号です．

アルゴリズムの動作はもっと単純で，
　現在いる点 x において，正定値行列 G を x から作り，
　　min cT d
　　s.t. dT G d = 1, A d = 0
　を解いて d を決定し，x を x + βd に置き換える．
という動作を繰り返すだけです．なので
> 現在いる点ｘにおいて、
> d = P・x によるアフィン変換で写像をする
は違います（アフィン変換を陽に構成することはありません）し，
> アフィン変換により、点から楕円体が形成される。
は，よくわかりません（点が楕円体を生成するとは？）．
また，
> 一番長い方向（２次元なら長軸の長さ）を求め
も違います．目的関数が最も減る方向であり，
それが楕円の軸方向になるとは限りません．

なお，アフィンスケーリング法に「アフィンスケーリング」という
名前がついているのは，アルゴリズムの動作が
「アフィンスケーリングした空間で，球で探索する
　アルゴリズムを実行しているのと実質的に同じ」
だからで，本当にアフィンスケーリングするわけではありません．

回答No.2

PRFRD

No.1のコメントに対して：
「アフィン変換する」というのは要するに「球でなく楕円体を使う」
ということなんですが，これをする必要性を理解するのは結構大変です．
結論だけ簡単に述べると
「球でやると毎ステップの移動距離が小さいけれど
　楕円体でやると移動距離がそれなりに大きいから」
というのが理由です．

歴史的には，もともとアフィン変換しない（球を使う）方法がありました．
ただ，どうもそれだと収束性能に関して，うまい評価が出来ません．
（角のほうで球がどんどん小さくなり，前に進めなくなるイメージ）．

そこで，球の変わりに楕円体を使う，というものを考えた人がいて，
それでやってみると，毎回それなりのステップ進む，ということがわかり，
なんと，大域的な収束性まで示せたりします．

ちなみにアフィンスケーリング法の詳細な解析は1990年～2000年にかけて行われており，
アフィンスケーリングの効果を理解するには，そのあたりの論文を読む必要があります

お礼

確かに、球より楕円体のほうが効果的なのはイメージできました。
もし球でやるなら、条件の「ｄTＧｄ＝β^2」の部分を、球を表す標準形になるということですよね。

一応自分の理解が以下の通りで正しいのか確認したいので、今一度補足回答お願いします。

流れとしては、
現在いる点ｘにおいて、
d = P・x によるアフィン変換で写像をする。（回答No.1では、x = P・dとなっていましたが、d = P・xではないでしょうか？）
アフィン変換により、点から楕円体が形成される。
この楕円体を多面体の中に収まるように、楕円体の大きさβを調節しつつ、
一番長い方向（２次元なら長軸の長さ）を求め、移動する方向ｄとする。
あとはこれの繰り返しで最適解を発見する
ということでしょうか。

補足

※お礼の方で投稿してしまったので、補足のところに投稿しなおします。

確かに、球より楕円体のほうが効果的なのはイメージできました。
もし球でやるなら、条件の「ｄTＧｄ＝β^2」の部分を、球を表す標準形になるということですよね。

一応自分の理解が以下の通りで正しいのか確認したいので、今一度補足回答お願いします。

流れとしては、
現在いる点ｘにおいて、
d = P・x によるアフィン変換で写像をする。（回答No.1では、x = P・dとなっていましたが、d = P・xではないでしょうか？）
アフィン変換により、点から楕円体が形成される。
この楕円体を多面体の中に収まるように、楕円体の大きさβを調節しつつ、
一番長い方向（２次元なら長軸の長さ）を求め、移動する方向ｄとする。
あとはこれの繰り返しで最適解を発見する
ということでしょうか。