An Extension of Sums of Squares Relaxations to Polynomial Optimization Problems over Symmetric Cones

This paper is based on a recent work by Kojima which extended sums of squares relaxations of polynomial optimization problems to polynomial semidefinite programs. Let ${\cal E}$ and ${\cal E}_+$ be a finite dimensional real vector space and a symmetric cone embedded in ${\cal E}$; examples of $\calE$ and $\calE_+$ include a pair of the $N$-dimensional Euclidean space and its nonnegative orthant, a pair of the $N$-dimensional Euclidean space and $N$-dimensional second order cones, and a pair of the space of $m \times m$ real 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 ${\cal E}_+$, i.e., a minimization of a real valued polynomial $a(x)$ in the $n$-dimensional real variable vector $x$ over a compact feasible region $\{ x : b(x) \in {\cal E}_+ \}$, where $b(x)$ denotes an $\cal E$-valued polynomial in $x$. It is shown under a certain moderate assumption on the $\cal E$-valued polynomial $b(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.

Citation

Research Report B-406, Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology, Meguro-ku, Tokyo 152-8552, Japan

Article

Download

View An Extension of Sums of Squares Relaxations to Polynomial Optimization Problems over Symmetric Cones