05 2017/06 07
28293031010203
04 050607080910
11121314151617
18192021 222324
25262728 293001
Click セミナー

過去のセミナー

開催日2017年4月10日(月曜日)
開催時間16時00分-17時30分
発表者坂上 晋作 
発表者の紹介NTT コミュニケーション科学基礎研究所
タイトル二値変数多項式最適化の縮小 Lasserre hierarchy
 
発表の概要
二値変数多項式最適化問題は,
Lasserre hierarchy という枠組みによって半正定値計画問題(SDP)に緩和することができる.
この緩和には緩和次数というパラメータが存在し,
緩和次数を大きく取るほど厳密な緩和となる反面,得られるSDPの問題のサイズが大きくなってしまう.
近年,Fawzi らは Lasserre hierarchy と Cayley グラフの関係に着目することで,
目的関数が2次関数の場合に,厳密な緩和を得るための緩和次数の上界を示した.
本研究ではこの結果を拡張し,目的関数が(2次関数とは限らない)多項式関数の場合に,
厳密な緩和を得るための緩和次数の上界を示す.
開催場所VBL棟 301B