Title | ||
---|---|---|
An Extension of Sums of Squares Relaxations to Polynomial Optimization Problems Over Symmetric Cones |
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 $$\varepsilon$$ and $$\varepsilon_{+}$$ be a finite dimensional real vector space and a symmetric cone embedded in $$\varepsilon$$; examples of $$\varepsilon$$ and $$\varepsilon_{+}$$ 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 × 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 $$\varepsilon_{+}$$, i.e., a minimization of a real valued polynomial a(x) in the n-dimensional real variable vector x over a compact feasible region $$\{ {\bf x} : b({\bf x}) \in \varepsilon_{+}\}$$, where b(x) denotes an $$\varepsilon$$- valued polynomial in x. It is shown under a certain moderate assumption on the $$\varepsilon$$-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. |
Year | DOI | Venue |
---|---|---|
2007 | 10.1007/s10107-006-0004-5 | Math. Program. |
Keywords | Field | DocType |
n-dimensional real variable vector,optimal value,sum of squares,squares relaxations,m real symmetric,symmetric cone,n-dimensional second-order cone,euclidean jordan algebra,polynomial optimization problem,positive semidefinite matrix,finite dimensional real vector,squares relaxation,semidefinite program,n-dimensional euclidean space,symmetric cones,polynomial optimization problems,global optimization,conic program,hermitian matrices,vector space,euclidean space | Discrete mathematics,Vector space,Mathematical optimization,Combinatorics,Orthant,Polynomial,Matrix (mathematics),Positive-definite matrix,Euclidean space,Hermitian matrix,Mathematics,Semidefinite programming | Journal |
Volume | Issue | ISSN |
110 | 2 | 1436-4646 |
Citations | PageRank | References |
14 | 1.83 | 8 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Masakazu Kojima | 1 | 1603 | 222.51 |
Masakazu Muramatsu | 2 | 336 | 28.68 |