  


An Extension of Sums of Squares Relaxations to Polynomial Optimization Problems over Symmetric Cones
Masakazu Kojima (kojimais.titech.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 (Semidefinite Programming ) Category 2: Global Optimization (Theory ) Citation: Research Report B406, Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology, Meguroku, Tokyo 1528552, Japan Download: [Postscript][Compressed Postscript][PDF] Entry Submitted: 04/28/2004 Modify/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  