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

課題番号	20−共研−2058		分野分類			統計数理研究所内分野分類			i
						主要研究分野分類			2
研究課題名	凸計画法の数理とアルゴリズム
フリガナ 代表者氏名	ツチヤ　タカシ 土谷　隆				ローマ字		Takashi TSUCHIYA
所属機関	統計数理研究所
所属部局	数理・推論研究系
職　　名	教授
配分経費	研究費	40千円		旅　費		180千円		研究参加者数		5　人

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

近年, 半正定値計画問題や２次錐計画問題等, 多項式時間で解ける凸計画問題が, 新たな強力で柔軟なモデリングの手段として実用化されつつあり, 統計学や信号処理, パターン認識, ロバスト最適化, 制御, 最適設計などへの応用が現在活発に進められている. しかしながら, 大規模化や数値的悪条件等まだ解決すべき問題がいろいろとある. また, 一般の凸計画問題に対するアルゴリズムの研究が十分になされているとはいえない. 多項式時間で解ける凸計画問題のクラスを拡げることは重要である. また, 対称錐計画問題において一番効率的とされる多項式時間主双対内点法を一般の凸計画問題に拡張することも, まだ十分に研究が進展していない, 興味深い問題である.
そのような問題意識の下に, 本申請課題では, 凸計画問題に対する数値解法の基礎および実装技術について, 下記の問題に取り組んだ.
1. 10月から11月にかけて, Florian Jarre 教授が統計数理研究所客員として来日し, 研究代表者と悪条件の半正定値計画問題に対する数値解法について研究した. 特に制御に由来する半正定値計画問題の主双対内点法を取り上げ, その数値的挙動について調べた.
2. Renato Monteiro 教授と半正定値計画問題に対する主双対内点法の曲率積分による反復回数の評価についてメイルや Fax を通じて議論した.
3. 統計数理研究所上野 助教とデータ同化に現れる大規模凸最適化問題（半正定値計画問題と密接な関係のある −logdet 関数最小化問題）の求解に取り組み, 約34000次元, 10万変数強のガウシアングラフィカルモデルの最尤推定に成功した. また, 約7800次元のモデルで15万変数までのモデルの情報量規準によるモデル選択を試みた.
それぞれの研究については現在も研究を継続中である.

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

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.
Mathematical Programming, Vol.115, No.1 (2008), pp.105-149.
L. Faybusovich , T. Mouktonglang , T. Tsuchiya, Numerical experiments with universal barrier functions for cones of Chebyshev systems, Computational Optimization and Applications, Vol.41 No.2, pp. 205-223, November 2008.
G.Ueno and T.Tsuchiya, Covariance Regularization in Inverse Space, Manuscript, The Institute of Statistical Mathematics, April 2009 (To appear in The Quarterly Journal of the Royal Meteorological Society).

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

研究参加者一覧
氏名	所属機関
Zhao Gongyun	シンガポール国立大学
Faybusovich Leonid	ノートルダム大学
Monteiro Renato	ジョージア工科大学
Jarre Florian	ドイツ デュッセルドルフ大学