過去の記録
2011年度 後期
1/6 (金) 17:00--19:00 @W9-201
- 講演者: 羽鳥映子氏 (経営工学専攻 中田研究室 M2)
- データマイニングに関する講演です (諸事情により題目および概要は非公開とさせて頂きます).
- 講演者: 永野清仁氏 (東京大学 生産技術研究所 最先端数理モデル連携研究センター 特任助教)
- 題目: 凸最適化と制約付き劣モジュラ関数最小化
- 概要: 多くの組合せ最適化問題は劣モジュラ関数の最小化問題として記述される.
制約なしの劣モジュラ関数最小化は多項式時間で解けることが知られている.
しかし、制約を付け加えることで多くの場合最適化が難しくなる.
サイズ制約下の劣モジュラ関数最小化はNP困難であり, さらに近似解を得ることすらも理論的には難しい.
しかし, 最密部分グラフ問題やグラフ分割問題などの基本問題を一般化した重要な問題であり, 現実的な手法の提案は重要である.
本研究では劣モジュラ制約下の凸最適化手法を用いることでサイズ制約下の劣モジュラ関数最小化の厳密解を部分的に求めるようなアルゴリズムを設計した.
さらに計算機実験によって提案手法の有効性について評価した.
12/16 (金) 17:00--19:00 @W9-201
- 講演者: 小野寺俊裕氏 (経営工学専攻 水野研究室 M2)
- 題目: 多期間ポートフォリオ問題に対する動的な意思決定を用いたロバスト最適化
- 概要: 本研究では, 多期間ポートフォリオ問題に対する動的な意思決定を用いたロバスト最適化の応用を行う.
ロバスト最適化とは, 現実問題に様々な不確実性が存在している場合に最悪状況を想定し最適化を行う手法である.
この手法には, 最悪状況を意識しすぎるあまり解が保守的になってしまうという問題がある.
そこで, 本研究ではその保守性を緩和するために, 動的な意思決定の1つの方法であるFinite Adaptabilityを応用し, 多期間ポートフォリオ問題への適応を行う.
そして, その効果を数値実験を通して評価, 考察を行う.
- 講演者: 浅原惇希氏 (経営工学専攻 中田研究室 M2)
- 題目: 半正定値計画問題に対する高精度ソルバの開発
- 概要: 半正定値計画問題を高精度, かつ現実的な時間内で解くことを目標としソルバの開発を行った.
半正定値計画問題を精度良く解くことは難しく, 従来は解が求められない問題に対して, 非常に時間がかかる多倍長演算を利用するパッケージを用いるなどしていた.
この研究では, 主双対内点法の終了後に得られた点を補正するアルゴリズムを拡張主双対法を基に考案した.
SDPLIBを中心とした多種のベンチマーク問題に対して数値実験を行うことで, より実用的なソフトウェアであることを示す.
11/25 (金) 17:00--19:00 @W9-201
- 講演者: 坂口聡一郎氏 (数理・計算科学専攻 小島研究室 M2)
- 題目: 非凸二次整数混合計画問題に対する拡張主双対法を用いた効率的な求解
- 概要: 非凸二次整数混合計画問題とは, 最大カット問題や最近接ベクトル問題など整数混合のケースを内包し, 様々な応用をもつ問題である.
これまでに, 半正定値緩和及び分枝カットと分枝限定法を用いて求解する手法が研究されてきた.
今回この手法を紹介する.
またこの手法は, 分枝カットの段階で制約が逐次追加される反復計算の特徴をもち,
従来の内点法に比べ拡張主双対法に有利な性質である.
そこで、拡張主双対法による半正定値緩和を試みているので, その紹介も行なう.
- 講演者: 和田悠太郎氏 (経営工学専攻 村木研究室 M2)
- 最適化の応用に関する講演です (諸事情により題目および概要は非公開とさせて頂きます).
11/11 (金) 17:00--19:00 @W9-201
- 講演者: 鮏川矩義氏 (筑波大学 大学院システム情報工学研究科 社会システム工学専攻 山本研究室 M2)
- 題目: 線形順序付け問題に対するラグランジュ緩和と釘付けテスト
- 概要: 線形順序付け問題は, 個人の選好をまとめて1つの選好を構成する方法や重みつき完了時刻の和を最小化する1機械スケジューリングなどに応用のあるNP困難な組合せ最適化問題である.
本発表では, 線形順序付け問題を0--1整数線形計画問題として定式化した際のラグランジュ緩和法における乗数の取り扱いを改良する方法と, 通常の釘付けテストを問題の構造を用いて強化する手法を提案し, それらの性能を数値実験により評価する.
- 講演者: 木村慧氏 (東京大学 大学院情報理工学系研究科 数理情報学専攻 数理情報第2研究室 D1)
- 題目: 整数線形システムの実行可能性問題に対する計算複雑さの指標
- 概要: 本研究では, m × n 行列 A, m 行ベクトル b, 整数 d が与えられたとき, ''A x ≥ b, 0 ≤ xi ≤ d - 1, xi は整数'' が実行可能であるかを判定する問題を扱った.
本研究では, この問題に対し, 計算複雑さの指標 γ を提案した.
この指標は行列 A の符号情報のみに基づくものである.
本研究では上記の問題に対し,
1. γ < 1 であれば, 多項式時間可解である.
2. γ = 1 であれば, 擬多項式時間可解かつ弱NP完全である.
3. γ > 1 であれば, 強NP完全である.
ことを示した.
この結果は先行研究における2次システムやホーンシステムに対する結果を真に包含している.
また, 指標 γ は行列 A の符号情報から作られる線形計画問題の最適値であり, 多項式時間で計算可能である.
10/18 (金) 17:30--19:00 @W9-201
- 講演者: 田中研太郎氏 (経営工学専攻 助教)
- 題目: 統計における条件付き独立性と線形計画問題
- 概要: 統計における条件付き独立性の表現手法として, グラフを用いた表現手法 (グラフィカルモデリング) がよく使われるが, グラフでは表すことのできない条件付き独立性の構造が存在することが知られている.
この欠点を克服するために, imsetと呼ばれるものを用いた代数的表現の手法がStudeny (2005) によって提案されている.
imsetは有限集合上の優モジュラ関数のなす錐の双対錐に対応しており, 条件付き独立性に関する議論を線形計画問題に帰着できる場合があることが知られている.
今回の発表では, imsetによる条件付き独立性の表現についての基礎と, そこで現れる線形計画問題について紹介する.
また, 最近の研究で得られたいくつかの理論的な結果と数値例について発表する.
それ以前