Sums of Squares and Semidefinite Programming Relaxations for Polynomial Optimization Problems with Structured Sparsity
Sums of Squares and Semidefinite Programming Relaxations for Polynomial Optimization Problems with Structured Sparsity
复制标题
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Hayato Waki;Sunyoung Kim;M. Kojima;M. Muramatsu
中科院分区：
文献类型：
--
作者：
Hayato Waki;Sunyoung Kim;M. Kojima;M. Muramatsu
.研究了无约束和不等式约束的稀疏多项式优化问题。定义了一个相关稀疏模式图，用于在POP的目标多项式和约束多项式中寻找某种稀疏结构.基于该图，得到了导致有效SOS和半有限规划（SDP）松弛的SOS多项式的支持集.从各种测试问题的数值结果包括显示SOS和SDP松弛的改进性能。
. Unconstrained and inequality constrained sparse polynomial optimization problems (POPs) are considered. A correlative sparsity pattern graph is defined to find a certain sparse structure in the objective and constraint polynomials of a POP. Based on this graph, sets of supports for sums of squares (SOS) polynomials that lead to efficient SOS and semidefinite programming (SDP) relaxations are obtained. Numerical results from various test problems are included to show the improved performance of the SOS and SDP relaxations.