ISMP 5日目

最終日です．帰ってしまった人がだいぶいます．

最初の招待講演．Andrzej Ruszczynskiの「Risk-Averse Optimization」．確率計画の話で，リスク最小化モデルに関わる講演者らの研究についてサーベイ的な部分から最新の研究までを．第1のトピックは確率優越とそれがリスク最小化モデルで果たす役割について．個人的には確率優越制約を持つ期待値最小化の辺りが面白かった．第2のトピックは確率変数列のリスクをどのように測り，それに関して多期間最適化を行うかという話．Time-consistentな動的リスク測度という概念があるようで，それに対してRisk-Averse Equivalence Theorem，Nested Decomposition Theoremというものが成り立ち，それを用いると多期間リスク回避最適化問題が再帰的にうまく解けるようになる，というような話 (だったと思う)．どちらのトピックも細部は分からなかったけど，雰囲気はちょっとつかめた．

整数計画法のセッションからLeen Stougieの「Revival of Vertex Enumeration」．(有界であるとは限らない) 凸多面体の頂点列挙が難しいことはKhachiyan et al. (SODA 2006, DCG 2008) による結果だけども，それをちょっと拡張した，という話．個人的にはその部分より，凸多面体の頂点列挙がバイオインフォマティクスのある問題と関係している，というところの方が面白かった．

同じく整数計画法のセッションからMichel Goemansの「Smallest Compact Formulation of the Permutahedron」．置換多面体の普通のH表現ではファセットの数が指数的になってしまうが，これをある高次元多面体Qの射影だと思うとき，Qのファセット数を多項式的にすることができる．A. Capraraは置換多面体のそのようなH表現の大きさがいくらになるか尋ねた．講演者はそれがΘ(nlogn)になることを証明している．下界は一般の多面体に対する単純な組合せ的議論から従い，上界はAKSソーティング・ネットワークを使って実際にH表現を与えている．面白い．

ちなみに「Goemans」はどう発音するのか，ということについて．彼はベルギーの人 (のはず) なのでGoemansはグーマンズと発音するのが普通だと思います．英語読みではゴーマンズでしょうか．

招待講演2件目．Pablo Parriloの「The Convex Algebraic Geometry of Rank Minimization」．水曜日に階数最小化のセッションへ行って予習した甲斐があった．近くにいたH氏は速かったと言っていた．内容は与えられた凸集合上 (通常はアフィン空間上) で階数が最小の行列を見つける問題について，特に凸計画緩和を議論した．まず5つ応用が紹介されて，順に挙げると，2次計画問題，行列補完，自乗和，システム同定，video inpainting (Ding, Sznaier, Camps, ICCV '07)．その後，階数がある定数以下の行列全体が作る代数多様体がどれだけ複雑かというのを目で見てみる．こういう絵が出てくると直観も働き出して楽しい．その後にnuclear norm heuristicの紹介が出てきて，これが階数1の行列全体から成る代数多様体と単位球のintersectionの凸包であると見なせるという解釈を与えていた (んだと思う)．そして簡単な計算機実験から相転移現象があることを観察．それを理論的に説明するためにRIPという性質を定義して，それとrandom instanceの関係，そしてRIPがあればnuclear norm heuristicは正しい答えを出力するということを説明．ここらへんでcompressed sensingとの対応を眺め，最後に与えられた行列Cを疎な行列Aと階数が小さな行列Bに分解するという話を展開．これについても凸計画緩和したときにrandom instanceでは正しい答えが得られるということ．

錐計画のセッションからEtienne de Klerkの話．タイトルは忘れた (アブストラクト集に書いてあるものとは違った)．頂点数nの完全グラフの辺上にコストがついていて，それとは別にあるグラフHが与えられているとき，完全グラフの中にあるHと同型な部分グラフで辺コストが最小(あるいは最大)なものを見つけるという問題を考える．これはHが頂点数nのサイクルのとき最小化問題は巡回セールスマン問題になって，Hが完全2部グラフK_{n/2,n/2}のとき最大化問題はmax bisectionになる．この問題を2次割当問題として書き，半正定値計画緩和する．ここでHがdistance regular graphであると，付随するアソシエーション・スキームが出てきて，半正定値計画緩和が上手に書ける．ちなみに上の2つの例はdistance regular．その半正定値計画緩和と既存の緩和の1つとの関係を調べて，最適値が変わらないことを示している．