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

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

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

近年, 半正定値計画問題や２次錐計画問題等, 多項式時間で解ける凸計画問題が, 新たな強力で柔軟なモデリングの手段として実用化されつつあり, 統計学や信号処理, パターン認識, ロバスト最適化, 制御, 最適設計などへの応用が現在活発に進められている. 半正定値計画法を用いれば, 現在, 2000次元程度のベクトルデータ300個から30000変数程度のガウシアングラフィカルモデルを厳密に最尤推定することが可能である. また, 数千次元の2次錐問題を数万回程度繰り返し解くようなシミュレーションもパソコンにより半日程度で可能である. これらは, 両方とも, 申請者のかかわった研究の実際例であり, 近年のアルゴリズムと計算機の発展によりはじめて可能となったことである. その一方, 何の変哲もない FIR フィルタ設計に由来する半正定値計画問題が求解困難であることがある. このように, 理論的には効率的であることが保証されているようなクラスの問題であっても, 実際には求解困難な問題が存在し, どのような問題にも対処できる安定した実装の開発にはなお研究が必要とされる. また, 一般の凸計画問題に対するアルゴリズムの研究が十分になされているとはいえない. 多項式時間で解ける凸計画問題のクラスを拡げることは重要である. また, 対称錐計画問題において一番効率的とされる多項式時間主双対内点法を一般の凸計画問題に拡張することも, まだ十分に研究が進展していない, 興味深い問題である.
そのような問題意識の下に, 本申請課題では, 凸計画問題に対する数値解法の基礎および実装技術について, 国際共同研究を行った。 Faybusovichは統計数理研究所に平成19年秋に 2ヶ月滞在し, Copositive錐上の線形計画問題に対する障壁関数を数値積分によって数値的に計算するための基礎的研究を進めた.今年度も引き続き研究を継続する予定である. また, Monteiro とは平成19年夏にチューリッヒで開催された国際会議ICIAM2007で, 対面し, 互いの最新の研究成果について議論した. 特に, 本年度は, Monteiro との共同研究の成果に基づいて, 小原とともに, 多項式時間内点法の情報幾何理論を構築したが, この理論を Monteiro および Zhao と昨年度の共同研究において議論した, 半正定値計画問題に対する主双対内点法の計算複雑度を積分で表現する問題と結びつける方向で今後の研究を進める予定である.

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

[論文]
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 (2008), No.1, pp105-149.

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

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