An Extension of Sums of Squares Relaxations to Polynomial Optimization Problems Over Symmetric Cones |
| |
Authors: | Masakazu Kojima Masakazu Muramatsu |
| |
Institution: | (1) Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, 2-12-1-W8-29 Oh-Okayama, Meguro-ku, Tokyo 152-8552, Japan;(2) Department of Computer Science, The University of Electro-Communications, 1-5-1 Chofugaoka, Chofu-shi, Tokyo 182-8585, Japan |
| |
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
and be a finite dimensional real vector space and a symmetric cone embedded in ; examples of and 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 , i.e., a minimization of a real valued polynomial a(x) in the n-dimensional real variable vector x over a compact feasible region , where b(x) denotes an - valued polynomial in x. It is shown under a certain moderate assumption on the -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.
Research supported by Grant-in-Aid for Scientific Research on Priority Areas 16016234. |
| |
Keywords: | Polynomial optimization problem Conic program Symmetric cone Euclidean Jordan algebra Sum of squares Global optimization Semidefinite program |
本文献已被 SpringerLink 等数据库收录! |
|