東工大最適化セミナー

このセミナーは東工大で最適化に関係する研究を行なっている研究室が中心となって行っているもので, 各研究室の教員や大学院生あるいは他大学からのゲストによる最新の研究成果について議論を行い, さらに研究を発展させていくことを目標としています. 参加申込等は不要ですので, ぜひお立ち寄りください.

今後の予定

今学期のセミナーはすべて終了しました.

題目: 錐制約をもつ半無限計画問題に関する諸研究
概要: 半無限計画問題とは, 無限個の不等式制約と有限個の変数で特徴付けされた最適化問題のクラスである. 工学や経済における多くの現実問題が半無限計画問題として自然に定式化されることが知られ, 最適性条件や双対性などに関する理論の構築や, それらに基づいた半無限計画問題を解くためのアルゴリズムの設計が盛んに行われてきた. 本講演では, 凸錐制約をもつ半無限計画問題に焦点をあて, それらの最適性条件やアルゴリズムについて述べる.

題目: 交互方向乗数法の確率的解法
概要: 機械学習における正則化学習問題を解くにあたり, 交互方向乗数法は非常に汎用的でかつ強力な最適化手法である. 本研究では, 交互方向乗数法をベースとしたいくつかの確率的最適化手法を提案する. サンプル数が大きい場合には, 一回ごとの更新に全てのサンプルを観測して更新するのではなく, 少数のサンプルのみを観測して更新する確率的最適化手法が有用である. 提案手法は大きく二つのタイプに分けられ, 一つ目は観測したサンプルは捨ててしまうオンライン型の手法で, 二つ目は双対問題において確率的座標降下法を用いる手法である. オンライン型の手法としては, 近接勾配型と双対平均型の手法を紹介し, それぞれがミニマクス最適なレートを達成することを示す. 一方, 双対問題において確率的座標降下法を用いる手法は, 指数的収束を達成することを示す. それぞれの手法を数値実験結果を交えて, その有用性について議論する.

題目: 二部グラフ上の最適予算配分問題に対する高速アルゴリズム
概要: 二部グラフ上の最適予算配分問題は, 企業のマーケティング活動を数学的にモデル化した最適化問題である. この問題には, 定数近似比の多項式時間アルゴリズムが知られていたが, 計算量の面で実用的ではなかった. また, マーケティングにおける実際の意思決定に役立てるには, より複雑な状況にも対応できるようにする必要がある. 本研究では, この問題を劣モジュラ性と呼ばれる組合せ的概念を用いて捉えなおし, より複雑な状況下でも定数近似解を求められることを示した. さらに, 劣モジュラ性を利用することで, 広告の影響力が時間とともに減衰するような状況ではほぼ線形時間で定数近似解を求められることを示した. 最後に, 実際の広告データとべき乗則にもとづくグラフに対して数値実験を行い, その有用性を確かめた.

題目: 船舶航行計画問題に対する航路生成法
概要: 本発表では, 船舶航行計画問題に対する厳密解法を提案する. 船舶航行計画問題とは, 出発地から目的地までの航路と船速をうまく決めて燃料の総消費量を最小にする問題である. 船舶航行計画問題は混合0--1整数非線形最適化問題として定式化でき, 少しだけ近似を施すと混合0--1整数2次錐最適化問題に変形できる. この問題は汎用ソフトウェアで解くことが可能だが, 大規模な問題を解くことは難しい. そこで本研究では, 航路の生成と船速の最適化を交互に繰り返す航路生成法を提案する. この解法の特徴は, 航路の生成は制約付き最短路問題に, 船速の最適化は2次錐最適化問題に帰着できるため, 各反復を高速に実行できること, 航路を生成する際に最適値の下界値を求めることができるため, 理論的にはすべての航路を生成することなく最適解を求めることができること, 燃料の総消費量が少ないことが見込まれる航路を優先して生成するため, 反復の途中であっても優れた暫定最適解を得ることができることの3つである. なお本研究は小林和博氏 (海上技術安全研究所) との共同研究である.