平成18（2006）年度　一般研究２実施報告書

課題番号	18−共研−2015			専門分類		2
研究課題名	対称錐計画問題の数理とアルゴリズム
フリガナ 代表者氏名	ツチヤ　タカシ 土谷　隆			ローマ字		Takashi Tsuchiya
所属機関	統計数理研究所
所属部局	数理・推論研究系
職　　名	教授
所在地
TEL				FAX
E-mail
URL
配分経費	研究費	50千円	旅　費		310千円		研究参加者数	5　人

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

対称錐計画問題は半正定値計画問題および2次錐計画問題などの凸計画問題を含み, 主双対内点法によって多項式時間で解くことができる凸最適化問題のクラスである. 対称錐計画問題は新たに登場した強力で柔軟なモデリングの手段として, 統計学や信号処理, パターン認識, ロバスト最適化, 制御, 最適設計などへの応用が現在活発に進められている. その一方, 線形計画問題とは違い, 理論的な収束性は保証されていても, 解くことが困難な問題が存在する. この困難が, 問題本来の非線形性によるものか, 数値的な誤差によるものかも現状では必ずしも明らかではない. 安定したアルゴリズムの実装のためには, 非線形性の尺度を曲率として捉える, 幾何学的な方法論が有効であると考えられる.
その確立に向けて, 本研究では, 特に, 解法の基礎である内点法の計算複雑度について, 幾何学的立場を通じて理解するため, Monteiro 教授と Zhao 助教授が2006年10月に統計数理研究所を2週間および1週間訪問し, 研究代表者と, 線形計画問題の内点法に対する行列空間上のダイナミカルシステムの立場からのアプローチ, そして半正定値計画問題の主双対内点法の計算複雑度を中心曲線上の曲率の積分で表現するための基礎について議論した. 研究は途上であるが, 今後さらに検討を進め, まとまった成果が得られた段階で論文として発表する予定である. また, 線形計画問題に対する主双対内点法の枠組みでの中心曲線の全曲率の評価についてもさらに議論を深めた.

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

R.D.C. Monteiro and T. Tsuchiya:
A strong bound on the integral of the central path curvature and its relationship with the iteration complexity of primal-dual path-following LP algorithms. Research Memorandum No. 958, The Institute of Statistical Mathematics, September 2005, Revised November 2006 and April 2007 (To appear in Mathematical Programming).

研究会を開催した場合は、テーマ・日時・場所・参加者数を記入してください。

研究参加者一覧
氏名	所属機関
Zhao Gongyun	シンガポール国立大学
夏　雨	統計数理研究所
Faybusovich Leonid	ノートルダム大学
Monteiro Renato	ジョージア工科大学