Development of highly accurate algorithms for semidefinite programming problems

开发半定规划问题的高精度算法

• 批准号: 22740056
• 负责人: WAKI Hayato
• 金额: $ 2.25万
• 依托单位: Kyushu University (2012-2013)The University of Electro-Communications (2010-2011)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2010
• 资助国家: 日本
• 起止时间: 2010-04-01 至 2014-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22740056/
• 关键词: 半正定値計画; 面的縮小; 多項式最適化問題; 半正定値計画緩和; 高精度計算; 対称錐上の線形最適化問題; 面的縮小法; 半正定値計画問題; H∞制御問題; 線形行列不等式; 低ランク解; 国際情報交換; 凸集合; 数理計画法

We mainly proposed an algorithm to remove ill-conditionedness in a given semidefinite programming problems (SDPs). In particular, we focus on ill-conditioned SDP, i.e., the SDP or its dual do not have any interior feasible solutions. Our results are: (1) We proposed a pre-processor for ill-conditioned SDP. It generates an equivalent and well-conditioned SDP with the original. Furthermore, we proposed a similar pre-processor for conic optimization problems, (2) We traced a reason why the resulting SDP from some applications are ill-conditioned, (3) We proposed an algorithm to generate well-conditioned SDP for polynomial optimization problems.

针对一类半定规划问题，提出了一种消除病态性的算法。特别地，我们关注病态SDP，即，SDP及其对偶不存在任何内部可行解。我们的结果是：（1）我们提出了一个病态SDP的预处理器。它生成与原始SDP等效且条件良好的SDP。（2）分析了某些应用中得到的SDP是病态的原因;（3）提出了一种生成多项式优化问题的良态SDP的算法。

项目成果

数学応用の要 -- 最適化 --

数学应用精要——最优化——

• 发表时间: 2013
• 作者: 高垣知哲;上岡修平;S.Matsumoto;Hayato Waki;松本詔;Yuzuru Inahama;上岡修平;脇 隼人;松本詔;上岡修平;Yuzuru Inahama;脇 隼人
• 通讯作者: 脇 隼人

Facial Reduction Algorithms for Conic Optimization Problems

• DOI: 10.1007/s10957-012-0219-y
• 发表时间: 2012-11
• 期刊: Journal of Optimization Theory and Applications
• 影响因子: 1.9
• 作者: Hayato Waki;M. Muramatsu

SparsePOP: a Sparse Semidefinite Programming Relaxation of Polynomial Optimization Problems

• 发表时间: 2005
• 期刊: Quaternary Science Reviews
• 影响因子: 4
• 作者: Hayato Waki;Sunyoung Kim;M. Kojima;M. Muramatsu

多項式行列不等式系に対する半正定値計画緩和について

多项式矩阵不等式系统的半正定规划松弛

• 发表时间: 2013
• 作者: 高垣知哲;上岡修平;脇 隼人
• 通讯作者: 脇 隼人

A perturbed sums of squares theorem for polynomial optimization and its applications, Optimization : Computation

多项式优化的扰动平方和定理及其应用，优化：计算

• 作者: S.Watanabe;K.Ishii;M.Sawa;Yuzuru Inahama;松本詔;上岡修平;Hayato Waki
• 通讯作者: Hayato Waki