Optimization Online


Completely Positive Reformulations for Polynomial Optimization

Javier Pena (jfp***at***andrew.cmu.edu)
Juan C. Vera (j.c.veralizcano***at***tilburguniversity.edu )
Luis F. Zuluaga (luis.zuluaga***at***lehigh.edu)

Abstract: Polynomial optimization encompasses a very rich class of problems in which both the objective and constraints can be written in terms of polynomials on the decision variables. There is a well stablished body of research on quadratic polynomial optimization problems based on reformulations of the original problem as a conic program over the cone of completely positive matrices, or its conic dual, the cone of copositive matrices. As a result of this reformulation approach, novel solution schemes for quadratic polynomial optimization problems have been designed by drawing on conic optimization tools, and the extensively studied cones of completely positive and of copositive matrices. In particular, this approach has been applied to solve key combinatorial optimization problems. Along this line of research, we consider polynomial optimization problems that are not necessarily quadratic. For this purpose, we use a natural extension of the cone of completely positive matrices; namely, the cone of completely positive tensors. We provide a general characterization of the class of polynomial optimization problems that can be formulated as a conic program over the cone of completely positive tensors. As a consequence of this characterization, it follows that recent related results for quadratic problems can be further strengthened and generalized to higher order polynomial optimization problems. Also, we show that the conditions underlying the characterization are conceptually the same, regardless of the degree of the polynomials de ning the problem. To illustrate our results, we discuss in further detail special and relevant instances of polynomial optimization problems.

Keywords: Polynomial Optimization, Copositive Programming, Completely Positive Tensors, Quadratic Programming

Category 1: Global Optimization (Theory )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Mathematical Programming (forthcoming), available at: http://link.springer.com/article/10.1007%2Fs10107-014-0822-9


Entry Submitted: 10/08/2013
Entry Accepted: 10/23/2013
Entry Last Modified: 10/11/2014

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