平成19（2007）年度　共同研究集会実施報告書

課題番号	19−共研−5011		分野分類			統計数理研究所内分野分類			i
						主要研究分野分類			2
研究課題名	最適化：モデリングとアルゴリズム
フリガナ 代表者氏名	ツチヤ　タカシ 土谷　隆				ローマ字		Takashi Tsuchiya
所属機関	統計数理研究所
所属部局	数理・推論研究系
職　　名	教授
配分経費	研究費	40千円		旅　費		880千円		研究参加者数		25　人

研究目的と成果（経過）の概要

最適化は、統計科学・数理科学・情報科学における基本的方法論の一つである。最適化手法の発展は新しいモデルの発展を促し、また、新しいモデルが最適化手法に新たな問題を投げかける。そのような意味で、最適化は、横断的に他の分野と相互交流しながら発展してきた。連続的最適化の分野では、最近の凸計画法の実用化は、機械学習や統計、パターン認識、制御、工学等における新しいモデルの開発を可能とし、さらに、Compressive Sensingに現れる大規模 L1正則化問題の解法や半正定値計画法の多項式計画問題への応用、内点法の情報幾何の展開など、計算、理論両面で新しい挑戦が続いている。離散的最適化の分野では、巡回セールスマン問題をはじめとする大規模問題の厳密解法やナーススケジューリング問題など現実にモデル化される最適化問題に対する実用的近似解法の研究が着実に進められ、現在は、３０００変数程度の０−１計画問題の多くは十分に実用レベルで厳密に解ける時代に入りつつある。しかしながら、その一方、理論的には効率的に解けることが保証されているにもかかわらず、数値的困難により解けない最適化問題も存在し、モデリングや実装面等なども含め、より一層の研究の進展が望まれる。
本研究集会は、1986年度から引き続いて開催されてきた最適化に関する研究集会であり、研究者の間でも高い評価を得ているものである。また、毎年報文集として、共同研究リポートの刊行も続けている。本年度も、３月１８日、１９日両日研究集会を開催し、２１件の発表と４６人の参加者があった。以下にプログラムを掲載する。

当該研究に関する情報源（論文発表、学会発表、プレプリント、ホームページ等）

３月１８日（火）
10:00〜10:35 離散準L/M凸関数最小化における連続緩和
　　　　　　　　土村　展之（東京大学　大学院情報理工学系研究科）
　　　　　　　　森口　聡子（上智大学　理工学部　機械工学科）
10:35〜11:10 完全選好リストを持つ安定結婚問題における戦略的操作可能性について
　　　　　　　　小林　弘達（中央大学）
　　　　　　　　松井　知己（中央大学）
11:15〜11:50 連続変数のM/L凸関数の基本性質について
　　　　　　　　室田　一雄（東京大学　大学院情報理工学系研究科）
　　　　　　　　塩浦　昭義（東北大学　大学院情報科学研究科）
11:50〜12:25 鉄道最安運賃経路検索
　　　　　　　　池上　敦子（成蹊大学　理工学部　情報工学科）
　　　　　　　　森田　隼史（日本信号株式会社）
　　　　　　　　山口　拓真（日本信号株式会社）
　　　　　　　　菊地　丞（日本信号株式会社）
　　　　　　　　中山　利弘（日本信号株式会社）
13:25〜14:00 バリア付き施設配置問題に対する厳密解法
　　　　　　　　栗田　圭介（電気通信大学　情報工学科）
　　　　　　　　松村　正和（電気通信大学　情報工学科）
14:00〜14:35 Portfolio Learning via VaR/CVaR Minimization
　　　　　　　　後藤　順哉（中央大学　理工学部　経営システム工学科）
　　　　　　　　武田　朗子（東京工業大学　情報理工学研究科　数理・計算科学専攻）
14:35〜15:10 Game theoretical analysis of combining binary classifiers for multi-class
Classification problems
白石　友一（総合研究大学院大学　複合化学研究科　統計科学専攻）
　　　　　　　　福永　健次（統計数理研究所）
15:20〜15:55 A new three term conjugate gradient method for unconstrained optimization
成島　康史（東京理科大学　理学部　数理情報科学科）
　　　　　　　　矢部　博（東京理科大学　理学部　数理情報科学科）
　　　　　　　　John A.Ford(University of Essex)
15:55〜16:30 Nonlinear Conjugate Gradient Methods with Structured Secant Condition
for Nonlinear Least Squares Problems
小林　道也（東京理科大学大学院　理学研究科）
　　　　　　　　矢部　博（東京理科大学　理学部　数理情報科学科）
　　　　　　　　成島　康史（東京理科大学　理学部　数理情報科学科）
16:30〜17:05 有界な線形計画問題に対して目的関数に存在しない計算複雑度を有する
Mizuno-Todd-Ye 予測子-修正子アルゴリズムの一変種
　北原　知就（東京工業大学　経営工学専攻）
　土谷　隆（統計数理研究所）

３月１９日（水）
10:00〜10:35 変分不等式に対する二次制約付きニュートン法
　　　　　　　　田地　宏一（名古屋大学大学院　工学研究科）
　　　　　　　　中尾　敬一（名古屋大学　工学部）
10:35〜11:10 多項式時間内点法への情報幾何学的接近法
　　　　　　　　土谷　隆（統計数理研究所）
　　　　　　　　小原　敦美（大阪大学　大学院基礎工学研究科　システム創成専攻）
11:15〜11:50 非線形SDP問題に対する主双対内点法の局所的超１次収束性について
　　　　　　　　山下　浩（（株）数理システム）
　　　　　　　　矢部　博（東京理科大学　理学部　数理情報科学科）
11:50〜12:25 双対一般化KYP補題と主双対内点法
　　　　　　　　山口　健（東京大学　大学院情報理工学研究系）
　　　　　　　　土谷　隆（統計数理研究所）
　　　　　　　　原　辰次（東京大学　大学院情報理工学系研究科）
13:25〜14:00 線形不等式制約の下でのＬ凸関数最小化
　　　　　　　　藤重　悟（京都大学　数理解析研究所）
　　　　　　　　林　匠（京都大学　大学院理学研究科）
　　　　　　　　永野　清仁（東京大学　大学院情報理工学研究科）
14:00〜14:35 最小費用全域木ゲームの劣モジュラ性
　　　　　　　　小林　真之（豊橋技術科学大学　大学院工学研究科　情報工学専攻）
　　　　　　　　岡本　吉央（東京工業大学　大学院情報理工学研究科）
14:35〜15:10 高階Delaunay三角形分割の列挙アルゴリズム
　　　　　　　　阿部　雄介（豊橋技術科学大学　大学院工学研究科　情報工学専攻）
　　　　　　　　岡本　吉央（東京工業大学　大学院情報理工学研究科）
15:20〜15:55 On the Pipage Rounding Algorithm for Submodular Function Maximization
−A View from Discrete Convex Analysis−
　　　　　　　　塩浦　昭義（東北大学　大学院情報科学研究科）
15:55〜16:30 OSSに対する決定論カオスに基づく信頼性評価法とその応用
　　　　　　　　田村　慶信（広島工業大学　情報学部　情報工学科）
　　　　　　　　山田　茂（鳥取大学　工学部　社会開発システム工学科）
16:35〜17:10 信頼度成長過程を考慮したソフトウェアの実時間性評価モデル
　　　　　　　　得能　貢一（鳥取大学　工学部　社会開発システム工学科）
　　　　　　　　山田　茂（鳥取大学　工学部　社会開発システム工学科）
17:10〜17:45 2次元ソフトウェア信頼性に基づく最適リリース問題に関する一考察
　　　　　　　　井上　真二（鳥取大学　工学部　社会開発システム工学科）
　　　　　　　　山田　茂（鳥取大学　工学部　社会開発システム工学科）

研究参加者一覧
氏名	所属機関
阿部　雄介	豊橋技術科学大学
池上　敦子	成蹊大学
伊藤　聡	統計数理研究所
井上　真二	鳥取大学
茨木　俊秀	関西学院大学
岩田　覚	京都大学
小島　政和	東京工業大学
小林　真之	豊橋技術科学大学
今野　浩	中央大学
田地　宏一	名古屋大学
田邊　國士	早稲田大学
田村　明久	慶應義塾大学
田村　慶信	広島工業大学
得能　貢一	鳥取大学
春名　亮	金沢学院大学
福島　雅夫	京都大学
藤重　悟	京都大学
水野　眞治	東京工業大学
村松　正和	電気通信大学
室田　一雄	東京大学
矢部　博	東京理科大学
山下　浩	（株）数理システム
山田　茂	鳥取大学
吉瀬　章子	筑波大学