Information Geometry of Convex Optimization : Extension and Applications

凸优化的信息几何:扩展与应用

• 批准号: 20340024
• 负责人: TSUCHIYA Takashi
• 金额: $ 5.99万
• 依托单位: National Graduate Institute for Policy Studies (2010)The Institute of Statistical Mathematics (2008-2009)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (B)
• 财政年份: 2008
• 资助国家: 日本
• 起止时间: 2008 至 2010
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20340024/
• 关键词: 凸最適化; 情報幾何; 内点法; 数理計画; 計算複雑度; 制御理論; グラフィカルモデル; 微分幾何; 対称錐計画; 線形計画; 半正定値計画

Interior-point algorithms for semidefinite programs and symmetric cone programs are analyzed in view of information geometry to show that the iteration complexity of primal-dual interior-point algorithms is approximately represented as a infomration geometric integral over central trajectory. Through extensive numerical experiments we demonstrated that the integral very accurately predict iteration-complexity of interior-point algorithms. One of the largest Gaussian graphical models in the world are successfully solved with super computer. Primal-dual interior-pont algorithms for large-scale Gaussian graphical models are developed. Regularization and facial reduction approaches for ill-conditioned semidefinite programs are developed.

从信息几何的角度分析了半定规划和对称锥规划的内点算法，证明了原始-对偶内点算法的迭代复杂度可以近似表示为中心轨迹上的信息几何积分。通过大量的数值实验证明，该积分可以很准确地预测内点算法的迭代复杂度。用超级计算机成功求解了世界上最大的高斯图形模型之一。提出了大规模高斯图形模型的原对偶内嵌算法。提出了病态半定规划的正则化和面约化方法。

项目成果

Applications of semidefinite programs with log-determinant terms

具有对数行列式项的半定规划的应用

• 发表时间: 2008
• 作者: S.Kakihara;R.D.C.Monteiro;A.Ohara;T.Tsuchiya;M.Hino;Takashi Tsuchiya and Atsumi Ohara;藤沢潤;J. Kigami;Takashi Tsuchiya;J.Kigami;小田芳彰;J.Kigami;M. Fukuda
• 通讯作者: M. Fukuda

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

• DOI: 10.1007/s10107-007-0141-5
• 发表时间: 2008-09-01
• 期刊: MATHEMATICAL PROGRAMMING
• 影响因子: 2.7
• 作者: Monteiro, Renato D. C.;Tsuchiya, Takashi
• 通讯作者: Tsuchiya, Takashi

Strange behaviors of interior-point mehtods for solving semidefinite programming problems in polynomial optimization

解决多项式优化中半定规划问题的内点方法的奇怪行为

• 发表时间: 2008
• 作者: Masakazu Muramatsu;Hayato Waki
• 通讯作者: Hayato Waki

Facial Reduction Algorithm and Conic Expansion Algorithm

面部缩小算法和圆锥展开算法

• 发表时间: 2009
• 作者: Masakazu Muramatsu;Hayato Waki
• 通讯作者: Hayato Waki

Geometry of q-Exponential Family of Probability Distributions

• DOI: 10.3390/e13061170
• 发表时间: 2011-06-01
• 期刊: ENTROPY
• 影响因子: 2.7
• 作者: Amari, Shun-ichi;Ohara, Atsumi
• 通讯作者: Ohara, Atsumi