Linear and Discrete Optimization の第五週目のメモ。こんどこそ線形計画問題の双対性の話(弱双対性、強双対性、Farkas の補題など)。 #linearopt
双対性については、形式的には理解していたのだけど、最適性の証明というモチベーションから説明してくれてすごく分かりやすかった。自分にはこれだけでもこの講義をとった価値があったなぁ。まあ、普通の教科書でもちゃんと読めば同じことは書いてあるのだろうけれど……
それから、マッチングと頂点被覆の話へ。max weight matching と min w-vertex cover の弱双対性を、整数計画とLP緩和を導入して証明。 さらに、二部グラフの場合に強双対性が成り立つことを、隣接行列の完全単模性(total unimodularity)を導入して証明。そういえば、完全単模性については、『型システム入門』の共訳者でもある +Yusuke KUROKI に昔教えてもらったなぁ。 ただ、自分は線形代数の知識が怪しくて、行列式に関する性質もあんましよく知らなかったので、完全単模性に関するクイズでちょっと苦労してしまった。
プログラミングの課題は、 多面体の頂点とは限らない内点が与えられたときに、そこから頂点を得るための ray shooting というアルゴリズムの実装。 これは単体法と大体一緒で、単体法の実装の復習に丁度良かった。
GurobiやCPLEXなどのMIPソルバでは、LP緩和を内点法の一種であるバリアを使って解くことがある。その場合、得られる解は頂点ではないかも知れないが、切除平面の適用などには頂点解の方が都合が良いので、crossoverと呼ばれる処理を行って、頂点解を得ている。 ray shooting は(その後の単体法による再最適化と合わせて)、crossoverのアルゴリズムと理解すれば良いのかな……
第一週目の感想
https://plus.google.com/100215187201873478127/posts/LhApNmsFT2B
第二週目の感想
https://plus.google.com/100215187201873478127/posts/WcTEf8nmxHs
第三週目の感想
https://plus.google.com/100215187201873478127/posts/2B5nsPfjGx6
第四週目の感想
https://plus.google.com/100215187201873478127/posts/JKJTRLZDNzm