題目: Optimization of dynamical systems, bilevel programming and observability on smart-grids.
概要: In the french "Sogrid" project about smart-grids, our aim is
to place the minimum number of measurement devices on the links of a
power-grid in order to "observe" to whole grid. After studying the
complexity of the problem, we present a first natural but computationally
unsatisfactory MILP model, which we reformulate into a bilevel program
using a fixed point argument. We will then study a large class of
dynamical systems depending on parameters which we want to optimize. We
will show that under some dominance hypothesis, these problems can be
reformulated into conic bilevel programs. We then present a new
constraints and variables generation algorithm to solve the problem and
show that the observability problem can be solved by a simplified version
of the algorithm. Finally we discuss some relations between the
observability problem and the minimum rank of a graph and show that some
bounds can be found to speed up the algorithm.
概要: 本発表では, 古典的秘書問題を特殊ケースとして含む 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 によって示されている.
本研究では, 一般の停止回数に対して, 勝利確率の下限を与える.
これらの下限は多数回停止可能な古典的秘書問題の勝利確率の下限でもあるという美しい構造を持つことが発見される.
本研究は, 穴太克則氏 (芝浦工業大学) との共同研究である.
4/25 (木) 17:00--18:00 @ W9-201
講演者: 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 Barany 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).
