An Extension of Sums of Squares Relaxations to Polynomial Optimization Problems Over Symmetric Cones
An Extension of Sums of Squares Relaxations to Polynomial Optimization Problems Over Symmetric Cones
复制标题
DOI：
10.1007/s10107-006-0004-5
复制
发表时间：
2007-03
影响因子：
2.7
通讯作者：
M. Kojima;M. Muramatsu
中科院分区：
文献类型：
--
作者：
M. Kojima;M. Muramatsu
本文基于 Kojima 最近的一项工作，该工作将多项式优化问题的平方和松弛扩展到多项式半定规划。令and为有限维实向量空间并嵌入一个对称锥体；的例子包括一对N维欧几里得空间及其非负象阵、一对N维欧几里得空间和N维二阶锥体、以及一对m×m实数对称（或复数埃尔米特）矩阵空间及其正半定矩阵的锥体。平方和松弛进一步扩展到多项式优化问题，即在紧致可行区域上最小化当时维实变量向量 x 中的实值多项式 (x)，其中 b(x) 表示值多项式 inx。结果表明，在对有值多项式 b(x) 进行一定适度假设的情况下，问题的松弛平方和序列的最优值在数值求解时转换为半定规划序列，收敛于问题的最优值。
This paper is based on a recent work by Kojima which extended sums of squares relaxations of polynomial optimization problems to polynomial semidefinite programs. Letandbe a finite dimensional real vector space and a symmetric cone embedded in; examples ofandinclude a pair of theN-dimensional Euclidean space and its nonnegative orthant, a pair of theN-dimensional Euclidean space andN-dimensional second-order cones, and a pair of the space ofm×mreal symmetric (or complex Hermitian) matrices and the cone of their positive semidefinite matrices. Sums of squares relaxations are further extended to a polynomial optimization problem over, i.e., a minimization of a real valued polynomiala(x) in then-dimensional real variable vectorxover a compact feasible region, whereb(x) denotes an- valued polynomial inx. It is shown under a certain moderate assumption on the-valued polynomialb(x) that optimal values of a sequence of sums of squares relaxations of the problem, which are converted into a sequence of semidefinite programs when they are numerically solved, converge to the optimal value of the problem.