Linear and Discrete Optimization の第四週目のメモ(既に第6週に入っているので、今更ながらだけれど)。次は双対性の話かなぁ、と思っていたら、単体法の計算量の話だった。 #linearopt
1ステップの計算量の話は大したことはないのだけれど、逆行列の成分が入力に対して多項式で抑えられていることとかちゃんとやってて、ちょっと「へぇ」と思った。
ステップ数に関しては、入力の多項式で抑えられるようなピボット規則があるかは未解決問題(Smale の Mathematical Problems for the Next Century に含まれてる)。
いくつか分かっている結果としては以下のようなものがある:
* 多くのピボット規則に対しては、指数ステップ必要になる入力が存在する
* 平均実行時間は多項式 (Borgwardt 1982)
* 係数を(N(0,σ)で)摂動すると、ステップ数の期待値は 1/σ, n, m に対して多項式 (Spielman and Teng 2004)
* 乱択を用いるピボット規則で、ステップ数の期待値が2^O(√m)のものあり (Kalai (1992, 1997), Matoušek, Sharir & Welzl (1996), Friedmann, Hansen, Zwick (2011))
さらに、多面体の頂点とその隣接関係で定義されるグラフを考えると、このグラフの直径が多項式で抑えられることは、単体法のステップ数が多項式で抑えられることの必要条件。
この直径に関して知られている最も良い上界は Kalai & Kleitman bound (1992) という
Δ(n,m) ≤ m^{1 + log n} というもの。
証明までして、この証明は面白かった。
プログラミングの課題は、単体法で毎回基底から逆行列を一から計算するのではなく、基底の変更に合わせて逆行列を更新するようにする変更。
これでひと通りの実装が出来たことになるので、自分が昔書いたやつも書きなおそうかなぁ……
第一週目の感想
https://plus.google.com/100215187201873478127/posts/LhApNmsFT2B
第二週目の感想
https://plus.google.com/100215187201873478127/posts/WcTEf8nmxHs
第三週目の感想
https://plus.google.com/100215187201873478127/posts/2B5nsPfjGx6