Completely positive reformulations for polynomial optimization

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

Research output: Contribution to journalArticleScientificpeer-review

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

Fingerprint

Reformulation
Polynomials
Cone
Polynomial
Optimization Problem
Optimization
Cones
Completely Positive Matrices
Quadratic Polynomial
Tensor
Conic Programming
Tensors
Natural Extension
Combinatorial Optimization Problem
Combinatorial optimization
Higher Order
Line

Keywords

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

Cite this

Pena, J.F. ; Vera Lizcano, J.C. ; Zuluaga, L.F. / Completely positive reformulations for polynomial optimization. In: Mathematical Programming. 2015 ; Vol. 151, No. 2. pp. 405-431.
@article{305e31ab5112421a9f78649cd3a28717,
title = "Completely positive reformulations for polynomial optimization",
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.",
keywords = "polynomial optimization, copositive programming, completely positive tensors, quadratic programming",
author = "J.F. Pena and {Vera Lizcano}, J.C. and L.F. Zuluaga",
year = "2015",
month = "7",
doi = "10.1007/s10107-014-0822-9",
language = "English",
volume = "151",
pages = "405--431",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer",
number = "2",

}

Completely positive reformulations for polynomial optimization. / Pena, J.F.; Vera Lizcano, J.C.; Zuluaga, L.F.

In: Mathematical Programming, Vol. 151, No. 2, 07.2015, p. 405-431.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Completely positive reformulations for polynomial optimization

AU - Pena, J.F.

AU - Vera Lizcano, J.C.

AU - Zuluaga, L.F.

PY - 2015/7

Y1 - 2015/7

N2 - 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.

AB - 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.

KW - polynomial optimization

KW - copositive programming

KW - completely positive tensors

KW - quadratic programming

U2 - 10.1007/s10107-014-0822-9

DO - 10.1007/s10107-014-0822-9

M3 - Article

VL - 151

SP - 405

EP - 431

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 2

ER -