Optimization Online


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

Masakazu Kojima (kojima***at***is.titech.ac.jp)
Masakazu Muramatsu (muramatu***at***cs.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society