- 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/2004Entry Accepted: 04/28/2004Entry Last Modified: 04/30/2004Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.