Convexification is a core technique in global polynomial optimization. Currently, two different approaches compete in practice and in the literature. First, general approaches rooted in nonlinear programming. They are comparitively cheap from a computational point of view, but typically do not provide good (tight) relaxations with respect to bounds for the original problem. Second, approaches based on sum-of-squares and moment relaxations. They are typically computationally expensive, but do provide tight relaxations. In this paper, we embed both kinds of approaches into a unified framework of monomial relaxations. We develop a convexification strategy that allows to trade off the quality of the bounds against computational expenses. Computational experiments show that a combination with a prototype cutting-plane algorithm gives very encouraging results.
Citation
Institut für Mathematische Optimierung, Otto-von-Guericke Universität Magdeburg, Universitätsplatz 2, 39108 Magdeburg, Germany, 01/2019
Article
View Convexification of polynomial optimization problems by means of monomial patterns