- | ||||
|
![]()
|
An Extension of Sums of Squares Relaxations to Polynomial Optimization Problems over Symmetric Cones
Masakazu Kojima (kojima 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 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 | |
![]() |