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

課題番号	19−共研−2047		分野分類			統計数理研究所内分野分類			i
						主要研究分野分類			2
研究課題名	半正定値計画法の諸側面に対する数理工学的アプローチ
フリガナ 代表者氏名	オハラ　アツミ 小原　敦美				ローマ字		ＯＨＡＲＡ　ＡＴＳＵＭＩ
所属機関	大阪大学
所属部局	大学院基礎工学研究科システム創成専攻システム科学領域
職　　名	准教授
配分経費	研究費	40千円		旅　費		50千円		研究参加者数		3　人

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

半正定値計画法は, 正定対称行列錐上とアフィン空間の上で線形目的関数を最小化する問題であり, 制御や信号処理, 機械学習, 統計や組合せ最適化, 大域的最適化など多くの分野への応用が期待されている. 本申請課題では「モデリング・アルゴリズム・数理」の問題意識の下に, 以下の３つの話題について研究を遂行し半正定値計画法の実用面からのアプローチによる貢献を目指すとともに，情報幾何と計算複雑度を結びつける数学的理論からのアプローチによる寄与も目的としていた．
1. 半正定値計画法の統計科学や機械学習への応用
(a) 半正定値計画法の密度関数推定への応用
(b) 半正定値計画法の大規模正規分布推定への応用
2. 悪条件の半正定値計画問題に対する頑健なアルゴリズムの構築
3. 半正定値計画法に関する情報幾何学的理論の構築

１に関しては，　密度関数の推定で重要な役割を果たす多項式最適化に関する研究成果[5],[7]や最大エントロピー法と関連の深いdeterminantの最適化について成果[1]が得られた．
次に２においては，応用の実用化に際して必要となる半正定値計画法に対する内点法の頑健な実装について研究した.また求解困難な半正定値計画問題の原因を様々な観点から検討した．これについては次年度も引き続いて検討し，有効な解決策を見いだす必要がある．
３では情報幾何学的な手法の導入により, 半正定値計画法に対する内点法の反復回数を問題の幾何学的量により特徴付ける理論的枠組みを構築した．具体的には予測子・修正子タイプのある内点法アルゴリズムを提案し，その多項式性の証明と反復回数の上限を許容領域の錐への埋め込み曲率の積分量で表すことができた．関連する研究成果は[2],[8],[9]である．
　その他当該研究に関連する数理最適化・情報幾何に関連する成果として，状態空間での平滑化分布の新しい効率的な計算法の研究[3]，非加法的エントロピーに対する情報幾何的考察[4]，半正定値計画と同様に錐計画問題のひとつである二次錐計画問題に対する新しいアルゴリズムの研究[6]を実施した．

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

[1] T. Tsuchiya and Y. Xia: An extension of the standard polynomial-time primal-dual path-following algorithm to the weighted determinant maximization problem with semidefinite constraints. Pacific Journal of Optimization 3 (2007), 165-182.
[2] 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 (2007) (already appeared online as future publication).
[3] K. Nakamura and T. Tsuchiya: A recursive recomputation approach for smoothing in nonlinear state-space modeling: an attempt for reducing space complexity. IEEE Transactions on Signal Processing (2007) (already appeared online as future publication).
[4] A. Ohara: Geometry of distributions associated with Tsallis statistics and properties of relative entropy minimization, Physics Letters A, 370 (2007), 184-193.
[5] M. Kojima and M. Muramatsu: An extension of sums of squares relaxations to polynomial optimization problems over symmetric cones. Mathematical Programming 110 (2007), 315-336.
[6] Masakazu Muramatsu: Towards a pivoting procedure for a class of second-order cone programming problems having multiple cone constraints. Pacific Journal of Optimization, 3 (2007) 87-98.
[7] M. Kojima and M. Muramatsu: A note on sparse SOS and SDP relaxations for polynomial optimization problems over symmetric cones. Computational Optimization and Applications (To appear).
[8] A. Ohara and T. Tsuchiya: An information geometric approach to polynomial-time interior-point algorithms − complexity bound via curvature integral-, Research Memorandum No. 1055, Institute of Statistical Mathematics, December (2007).
[9]土谷，小原：内点法と情報幾何　−計算の複雑さへの微分幾何学的アプローチ-，数学セミナー，２００８年３月号

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

研究参加者一覧
氏名	所属機関
土谷　隆	統計数理研究所
村松　正和	電気通信大学