Lagrangian-Conic Relaxations, Part II: Applications to Polynomial Optimization Problems
Abstract: We present the moment cone (MC) relaxation and a hierarchy of sparse Lagrangian-SDP relaxations of polynomial optimization problems (POPs) using the unified framework established in Part I. The MC relaxation is derived for a POP of minimizing a polynomial subject to a nonconvex cone constraint and polynomial equality constraints. It is an extension of the completely positive programming relaxation for QOPs. Under a copositivity condition, we characterize the equivalence of the optimal values between the POP and its MC relaxation. A hierarchy of sparse Lagrangian-SDP relaxations, which is parameterized by a positive integer $\omega$ called the relaxation order, is proposed for an equality constrained POP. It is obtained by combining a sparse variant of Lasserre's hierarchy of SDP relaxation of POPs and the basic idea behind the conic and Lagrangian-conic relaxations from the unified framework. We prove under a certain assumption that the optimal value of the Lagrangian-SDP relaxation with the Lagrangian multiplier $\lambda$ and the relaxation order $\omega$ in the hierarchy converges to that of the POP as $\lambda \rightarrow \infty$ and $\omega \rightarrow \infty$. The hierarchy of sparse Lagrangian-SDP relaxations is designed to be used in combination with the bisection and $1$-dimensional Newton methods, which was proposed in Part I, for solving large-scale POPs efficiently and effectively.
Keywords: Polynomial optimization problem, moment cone relaxation, SOS relaxation, a hierarchy of the Lagrangian-SDP relaxations, exploiting sparsity.
Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )
Category 2: Convex and Nonsmooth Optimization (Convex Optimization )
Citation: Research Report B-476, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Oh-Okayama, Meguro-ku, Tokyo 152-8552, January (2014).
Entry Submitted: 01/09/2014
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|