過去の記録
2012年度 後期
1/17 (木) 17:00--18:30 @W9-201
- 講演者: 宮代隆平氏 (東京農工大学 工学部 情報工学科 准教授)
- 最適化の応用に関する講演です (諸事情により題目および概要は非公開とさせて頂きます).
12/21 (金) 17:00--18:30 @W9-201
- 講演者: 千代竜佑氏 (中田研究室 M2)
- 題目: 年金資産運用に対する連続時間モデルと多期間ポートフォリオ最適化
- 概要: 年金資産運用は, 一般的な資産運用と比較すると運用期間が長期にわたることや継続的なキャッシュフローがあることが特徴であり, 様々な最適化モデルが考えられてきた.
先行研究では資産価値がキャッシュフローを追跡するような運用を目的とした資産運用問題が連続時間モデルで記述され, 解析解が求められている.
しかしこの方法で解くことのできる問題は限られており, 運用上の制約なども扱うことができない.
そのため本研究では多期間ポートフォリオ最適化の手法を用いて, 同様の問題を不等式制約を扱うことのできる形でモデル化する.
また数値実験により連続時間モデルの近似となっていることを示す.
- 講演者: 宮崎慶氏 (山下研究室 M2)
- 題目: Completely Positive計画問題に対するT錐緩和による問題サイズの縮小化
- 概要: 最近, 多くのNP困難な最適化問題が同値なCompletely Positive (CP) 錐上の線形計画問題 (CPP) として定式化されることが示された.
この問題のNP困難性はCP錐に集約されており, 様々なCP錐の緩和錐が提案されている.
それらの緩和錐の中でもH. Dongにより提案されたT錐を用いると緩和問題を線形計画問題 (LP) に定式化できるが, 元問題の次数が上がった時にLPの変数の数が増大し, メモリが不足する.
本論文では, 二次割当問題 (QAP) や最大安定集合問題 (SSP) など, 特定の構造を持つCPP定式化可能な最適化問題に対してT錐緩和LPの変数の数を大幅に縮小する手法を提案し, その手法をQAPとSSPに適用し, 数値実験を行った.
12/13 (木) 17:00--18:30 @W9-201
- 講演者: 林紳太郎氏 (水野研究室 M2)
- 最適化の応用に関する講演です (諸事情により題目および概要は非公開とさせて頂きます).
- 講演者: 中垣敬氏 (福田研究室 M2)
- 題目: 対数行列式と l1 ノルムを持つ半正定値計画問題に対するスペクトル射影勾配法の実装
- 概要: 本研究では, 対数行列式と l1 ノルムを持つ半正定値計画問題に対するスペクトル射影勾配法について考察する.
この問題は, ガウシアングラフィカルモデルの最尤推定問題などを含む.
これまで同じ目的関数でも変数行列のいくつかの要素が0であるといった特殊な線形制約を持つ問題のみ議論されてきた.
しかし本研究では, より幅広い一般の線形制約を持つ問題を取り扱う.
この問題は, 制約付き最適化問題の代表的なアルゴリズムである内点法では規模が大きくなり, 解くのが困難になる.
今回, この問題に対してスペクトル射影勾配法に基づくアルゴリズムを提案する.
最後に数値実験の結果を報告し, このアルゴリズムの性能を評価する.
11/1 (木) 17:00--18:30 @W9-201
- 講演者: 小林佑輔氏 (東京大学 大学院情報理工学系研究科 数理情報学専攻 助教)
- 題目: 制約付き2マッチング問題に対するアルゴリズム
- 概要: 最大マッチング問題は多項式時間で解くことのできる代表的な組合せ最適化問題であり, その事実を用いて最大2マッチング問題も容易に多項式時間で解くことができる.
一方で, 巡回セールスマン問題は, 最大2マッチング問題に付加的な条件を加えた問題と解釈することができるが, 代表的なNP困難問題である.
本発表では, 様々な制約を付加した2マッチング問題の解法・困難性について紹介する.
また, この問題を通して, 自分がどのような動機・目的を持って組合せ最適化問題に取り組んでいるかを紹介したい.
それ以前