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

Masakazu Kojima (kojimais.titech.ac.jp)
Masakazu Muramatsu (muramatucs.uec.ac.jp)

Abstract: 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.

Keywords: Polynomial Optimization Problem, Conic Program, Symmetric Cone, Euclidean Jordan Algebra, Sum of Squares, Global Optimization, Semidefinite Program

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Global Optimization (Theory )

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

Download: [Postscript][Compressed Postscript][PDF]

Entry Submitted: 04/28/2004
Entry Accepted: 04/28/2004
Entry Last Modified: 04/30/2004

Modify/Update this entry