Linear and Discrete Optimization の第三週目の感想。ちょうど5週目に入ったところなので今更だけれど。 #linearopt
第二週目で頂点を全列挙することでLPを解くというアルゴリズムを実装したけれど、第三週ではより効率的な方法として、隣接する頂点を移動していく単体法(Simplex method)を導入する。
第二週で多面体P={x ∈R^n | Ax≤b}の頂点の特徴付けを二つ与えたように、今度は頂点x1,x2が隣接しているということについて、やはり2つの定義を与える。1つは多面体に対してvalidであって、かつx1,x2の両方でactiveになるようなn-1個の線形独立な不等式が存在すること。もう1つは、線分{λx1 + (1-λ)x2 | λ∈R, 0≤λ≤1 }が最適解の集合になるようなLP max{c^T x | x ∈P} が存在すること(そういう目的関数ベクトルcが存在すること)。
そのうえで、隣接する頂点間で目的関数を改善する方に繰り返し移動していくアルゴリズムが単体法。 Aが正則行列なら、基底を一個入れ替えて実行可能な基底を得られれば、n-1個の不等式はactiveなままなので、隣接頂点なのね。
最後に、縮退している場合を扱うために縮退している場合でも停止性の保証されるBlandのピボット規則と、初期実行可能基底解を求めるために二段階法(Two-Phase Simplex Method)とを説明。
この講義では変数の非負制約はずっとなしできているのだけれど、二段階法での変形で非負制約がある形に変形していた。確かに、非負制約があって嬉しいのはここくらいなのか。なるほどとちょっと感心。
第一週目の感想
https://plus.google.com/100215187201873478127/posts/LhApNmsFT2B
第二週目の感想
https://plus.google.com/100215187201873478127/posts/WcTEf8nmxHs