On robust numerical methods of semidefinite relaxation for polynomial optimization problems

多项式优化问题的半定松弛鲁棒数值方法

• 批准号: 22560061
• 负责人: MURAMATSU Masakazu
• 金额: $ 2.5万
• 依托单位: The University of Electro-Communications
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2010
• 资助国家: 日本
• 起止时间: 2010-04-01 至 2013-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22560061/
• 关键词: 最適化; 錐線形計画; 多項式計画; 半正定値計画; 頑健性; 面的削減法

We established the theory of facial reduction algorithm (FRA) for conic linear optimization problems, and prove that the conic expansion approach is dual to FRA. For SDP relaxation for polynomial optimization problems (POPs), sometimes we can compute the optimal value of POP by solving the SDP relaxation problem although the SDP problem is infeasible. We elucidated the reason of this phenomena, and proposed a new SDP relaxation scheme using this property.

建立了求解圆锥曲线线性优化问题的面约简算法（FRA）理论，并证明了圆锥曲线展开法与FRA算法是对偶的。对于多项式优化问题的SDP松弛问题，有时即使SDP松弛问题是不可行的，也可以通过求解SDP松弛问题来计算多项式优化问题的最优解。我们解释了这一现象的原因，并利用这一性质提出了一种新的SDP弛豫方案。

项目成果

Afacial reduction algorithm for fording sparse SOS representations

用于福特稀疏 SOS 表示的面部缩减算法

• 发表时间: 2010
• 期刊: Operations Research Letters
• 影响因子: 1.1
• 作者: H.Waki;M.Muramatsu
• 通讯作者: M.Muramatsu

Adaptive SDP relaxation for polynomial optimization

用于多项式优化的自适应 SDP 松弛

• 发表时间: 2013
• 作者: T.Ohkami;S.Koyama;M. Muramatsu
• 通讯作者: M. Muramatsu

2次元トーラスグラフ上での情報拡散ゲームにおけるナッシュ均衡

二维环图信息扩散博弈中的纳什均衡

• 发表时间: 2013
• 作者: T.Ohkami;S.Matsuura;S.Koyama;塚田健,深堀康紀,谷尾真明,杉原正顯;祐成友樹,村松正和
• 通讯作者: 祐成友樹,村松正和

The facial reduction algorithm for semidefinite programming relaxation of polynomial optimization problems

多项式优化问题半定规划松弛的面部缩减算法

• 发表时间: 2010
• 作者: 山下真悟;永井学志;M. Muramatsu
• 通讯作者: M. Muramatsu

A perturbed sums of squares theorem for polynomial optimization and its applications

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

• 发表时间: 2012
• 作者: Masakazu Muramatsu;Levent Tuncel;and Hayato Waki
• 通讯作者: and Hayato Waki