東工大最適化セミナー

過去の記録

題目: 不動点定理を用いたドロネー性の確認
概要: 計算幾何学における基本的なデータ構造にボロノイ図とその双対であるドロネー図がある. 本研究ではドロネー図の位相構造だけを取り出したドロネーグラフを扱う. 平面上に埋め込まれた三角形分割グラフがドロネーグラフであるか否かの判定は, 浮動小数点演算を前提とした画像処理では重要である. そしてその判定が線形計画問題に (多項式時間で) 帰着できることは1990年台中頃には知られていたが, その証明は難解・複雑なものであった. 近年我々は新たに簡潔明瞭なる証明を提案したが, その成功の鍵は不動点定理を用いたことである. 本発表では, 計算幾何学と最適化の面白さを伝えることが出来れば幸いです. 本研究は松井知己氏 (東京工業大学) との共同研究です.

題目: 凸計画問題に対する効率的な劣勾配法と新しい計算量解析の枠組み
概要: 本研究では, 凸計画問題に対する劣勾配法を扱う. NemirovskiとYudinによって提案されたMirror Descent (MD) 法は, アルゴリズムの生成点列 x_k に対して, 絶対誤差 f(x_k) - f^* の収束オーダーが O(1/√k) であることを保証するために強い仮定が必要となる. 本研究では, そのような仮定を必要としない拡張MD法を提案する. 同様の性質を持つ劣勾配法としてNesterovが2009年に提案したDual-Averaging (DA) 法があるが, 提案手法はDA法よりも小さな絶対誤差の上界を保証できる. さらに我々は, 拡張MD法とDA法のモデルをひとつの枠組みの中で統一的に解析をおこない, DA法の解析を従来よりも簡略化した. 本研究では, この枠組みの応用として, 滑らかな目的関数を持つ問題に対する効率的な勾配法を提案し, Nesterovが提案した O(1/k²) の収束オーダーを持つアルゴリズムと比較して, より小さな絶対誤差の上界を保証できることを示す.

題目: 多数回停止可能な最適停止問題における勝利確率の下界について
概要: 本発表では, 古典的秘書問題を特殊ケースとして含むBrussのOdds Problemについて議論する. Odds Problemでは, 0/1確率変数列を逐次観測し, 各変数を観測後に観測を停止するか, 観測を継続するかを決定する. 停止した確率変数が, 1 となる最後の確率変数である確率を最大にする規則を最適停止規則と呼び, その際の確率を勝利確率と呼ぶ. Odds Problemの勝利確率は 1/e 以上であることが2003年にBrussによって示されている. Odds Problemにおいて, 多数回停止を可能とした問題については, 停止回数2回の場合の勝利確率が e^-1 + e^-3/2 以上であることが, 2010年にAno, Kakinuma, and Miyoshiによって示されている. 本研究では, 一般の停止回数に対して, 勝利確率の下限を与える. これらの下限は多数回停止可能な古典的秘書問題の勝利確率の下限でもあるという美しい構造を持つことが発見される. 本研究は, 穴太克則氏 (芝浦工業大学) との共同研究である.

講演者: Antoine Deza氏 (Department of Computing and Software, Faculty of Engineering, McMaster University)

題目: Colourful linear programming and colourful simplicial depth
概要: In statistics, there are several measures of the depth of a point p relative to a fixed set S of sample points in dimension d. One of the most intuitive is the simplicial depth of p introduced by Liu in 1990, which is the number of simplices generated by points in S that contain p. Carathéodory's Theorem can be restated as: The simplicial depth is at least 1 if p belongs to the convex hull of S, and finding such a simplex corresponds to a linear programming feasibility problem. We present recent results and open questions dealing with a generalization of linear programming introduced by Bárány and Onn in 1997, and the associated generalization of the Carathéodory's Theorem proven by Bárány in 1982. In particular, we present recent generalizations of the Colourful Carathéodory Theorem due to Arocha et al. and Holmsen et al. and our strengthening of these. We provide a lower bound for the colourful version of the simplicial depth improving the earlier bounds of Bárány and Matoušek and of Stephen and Thomas, and verify that the conjectured lower bound is tight for dimension 4. Computational approaches for small dimensions are discussed. Based on joint works with Frédéric Meunier (ENPC Paris), Tamon Stephen (Simon Fraser), Pauline Sarrabezolles (ENPC Paris), and Feng Xie (Microsoft).