Linear and Discrete Optimization の第二週目。 #linearopt
多面体の頂点は、その多面体内の点に対してvalidかつ、その点でだけactiveになるような線形不等式が存在することで、綺麗に特徴付けられる。これは知らなくて、「へぇ、こうやって定義するんだ」と感心した。
ただ、これは扱いにくいので、多面体P={x ∈R^n | Ax≤b}の中の点で「Ax≤bのうちn本の不等式がactiveな点」という同値だけれど表現に依存した定義(basic feasible solution)を与えて、それを使っていく。
その上で、最適解が存在するなら、頂点で最適なものが存在することを示し、頂点を列挙して最適解を求めるという(非効率的な)アルゴリズムを実装することで、アルゴリズム的に解けることを示す。
数学的に綺麗な定義と、実際にアルゴリズムで用いる定義の対応を丁寧に追いつつ、かついきなり一足飛びに単体法とかに行かずに頂点を列挙するアルゴリズムを使って段階を踏んで説明しているあたりは良いなぁ。この辺りの分野の教科書を真面目に読んだことはないのだけれど、これまでに眺めたどの教科書よりも分かりやすい説明をしていると思った。
プログラミングの演習は何を使うのかなぁ、きっとPythonあたりだろうなぁ、と思っていたら、SymPy http://sympy.org/ だった。使ったことないけれど、まあ順当なところだろうな。
それから、ちょっと寄り道して Fourier-Motzkin variable elimination の話なんかもしていた。(Fourier-Motzkin variable elimination はOmega (Omega test) の基礎になっている決定手続きで、その辺りのことは昨年の ProofSummit 2012 で少しだけ話した http://www.slideshare.net/sakai/omega-test-and-beyond )
自分が知らなくてちょっと驚いたのは、Fourier-Motzkin variable elimination を、充足可能性と恒真性の検査だけでなく、最適化にも直接使える点。言われてみれば当たり前なんだけれど、目的関数を変数でおいて、他の変数をすべて射影して消去したうえで、目的関数をおいた変数の上限下限を見れば良い。
第一週の感想 https://plus.google.com/u/0/100215187201873478127/posts/LhApNmsFT2B
Linear and Discrete Optimization
