  


LagrangianConic Relaxations, Part II: Applications to Polynomial Optimization Problems
Naohiko Arima(nao_arimame.com) Abstract: We present the moment cone (MC) relaxation and a hierarchy of sparse LagrangianSDP 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 LagrangianSDP 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 Lagrangianconic relaxations from the unified framework. We prove under a certain assumption that the optimal value of the LagrangianSDP 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 LagrangianSDP relaxations is designed to be used in combination with the bisection and $1$dimensional Newton methods, which was proposed in Part I, for solving largescale POPs efficiently and effectively. Keywords: Polynomial optimization problem, moment cone relaxation, SOS relaxation, a hierarchy of the LagrangianSDP relaxations, exploiting sparsity. Category 1: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Category 2: Convex and Nonsmooth Optimization (Convex Optimization ) Citation: Research Report B476, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, OhOkayama, Meguroku, Tokyo 1528552, January (2014). Download: [PDF] Entry Submitted: 01/09/2014 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  