■第17回研究会(2005年9月3日(土)14:00--18:00 東京大学 工学部6号館)の講演概要
 
14:00--15:50『多項式最適化問題に対する半正定値計画緩和』東京工業大学 脇 隼人 氏
多項式最適化問題とは, 目的関数と制約式が多項式で記述された最適化問題であ り, 二次最適化問題や0-1整数計画問題などの多くの最適化問題を記述すること ができる.

この多項式最適化問題に対して, Lasserre(2002)とParrilo(2003)が独立に半正 定値計画緩和を提案した. 特にLasserreは, 得られる半正定値計画問題の最小 値が多項式最適化問題に収束するという理論的性質を示したけでなく, 数値実験 では実際に多項式最適化問題の最小値が得られていることを報告していた.

しかしながら, Lasserreの手法では多項式最適化問題の変数の数が多くなると, 得られる半正定値計画問題が大規模になり, 最適値を得ることが困難になる.

そこで, 多項式最適化問題の疎性や構造を利用することで得られる半正定値計画 問題を小さくすることを考えた. これにより多項式最適化問題の疎性や構造によ るが変数の数が数百から数千の規模の多項式最適化問題を解くことができるよう になった.

なお, 小島政和先生, Ewha women's Univ.のKim Sunyoung先生と電気通信大学の 村松正和先生との共同研究です.

 
16:10--18:00『グラフの最小彩色問題に係わる協力ゲームの数理とアルゴリズム』豊橋技術科学大学 岡本 吉央 氏
最小彩色ゲームとは、エージェント間に競合がある状況の下で生じる最小コス トを各エージェントへ公平に分配する問題を協力ゲーム理論の枠組でモデル化 したものです。これは Deng, Ibaraki, and Nagamochi (1999) によって提案 された概念であり、より大きな枠組である「組合せ最適化ゲーム」の一例になっ ています。本発表では、最小彩色ゲームに関して知られている性質を、特にコ アと呼ばれる公平配分の集合に焦点を絞って紹介します。コアとは (非空とは 限らない) 有界な凸多面体であり、劣モジュラ最適化の分野における基多面体 と等価な概念ですが、協力ゲーム理論に現れる関数が劣モジュラであるとは限 らないため、基多面体に対するより詳細な考察が必要となります。その点が研 究対象としての魅力の1つとなっています。発表では、協力ゲーム理論、組合 せ最適化、グラフ理論に関する特別な前提知識を仮定しないように努めます。
 
Seminars on Algorithms in Operations Research
ホーム - SAORについて - 会場案内 - 全日程 - リンク
(c) 2003-2004 SAOR All rights reserved.