### Abstract

Original language | English |
---|---|

Pages (from-to) | 405-431 |

Journal | Mathematical Programming |

Volume | 151 |

Issue number | 2 |

Early online date | 30 Sep 2014 |

DOIs | |

Publication status | Published - Jul 2015 |

### Fingerprint

### Keywords

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

### Cite this

*Mathematical Programming*,

*151*(2), 405-431. https://doi.org/10.1007/s10107-014-0822-9

}

*Mathematical Programming*, vol. 151, no. 2, pp. 405-431. https://doi.org/10.1007/s10107-014-0822-9

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

Research output: Contribution to journal › Article › Scientific › peer-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 -