Completely positive reformulations for polynomial optimization

J.F. Pena, J.C. Vera Lizcano, L.F. Zuluaga

Research output: Contribution to journalArticleScientificpeer-review

26 Citations (Scopus)

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 established 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 programming 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 defining the problem. To illustrate our results, we discuss in further detail special and relevant instances of polynomial optimization problems.
Original languageEnglish
Pages (from-to)405-431
JournalMathematical Programming
Volume151
Issue number2
Early online date30 Sep 2014
DOIs
Publication statusPublished - Jul 2015

Keywords

  • polynomial optimization
  • copositive programming
  • completely positive tensors
  • quadratic programming

Fingerprint Dive into the research topics of 'Completely positive reformulations for polynomial optimization'. Together they form a unique fingerprint.

  • Cite this