Optimization Online


Extension of Completely Positive Cone Relaxation to Polynomial Optimization

Naohiko Arima (arima.n.ab***at***m.titech.ac.jp)
Sunyoung Kim (skim***at***ewha.ac.kr)
Masakazu Kojima (kojima***at***is.titech.ac.jp)

Abstract: We propose the moment cone relaxation for a class of polynomial optimization problems (POPs) to extend the results on the completely positive cone programming relaxation for the quadratic optimization (QOP) model by Arima, Kim and Kojima. The moment cone relaxation is constructed to take advantage of sparsity of the POPs, so that efficient numerical methods can be developed in the future. We establish the equivalence between the optimal value of the POP and that of the moment cone relaxation under conditions similar to the ones assumed in the QOP model. The proposed method is compared with the canonical convexification procedure recently proposed by Pe$\tilde{\mbox{n}}$a, Vera and Zuluaga for POPs. The moment cone relaxation is theoretically powerful, but numerically intractable. For tractable numerical methods, the doubly nonnegative cone relaxation is derived from the moment cone relaxation. Exploiting sparsity in the doubly nonnegative cone relaxation and its incorporation into Lasserre's semidefinite relaxation are briefly discussed.

Keywords: Moment cone relaxation, doubly nonnegative cone relaxation, polynomial optimization, copositive programming, completely positive programming.

Category 1: Linear, Cone and Semidefinite Programming

Citation: B-471, Dept. of Math. and Comp. Sciences, Tokyo Institute of Technology, Tokyo 152-8552, February 2013.


Entry Submitted: 02/07/2013
Entry Accepted: 02/07/2013
Entry Last Modified: 02/07/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society