Optimization Online


Convexification of polynomial optimization problems by means of monomial patterns

Gennadiy Averkov(gennadiy.averkov***at***ovgu.de)
Benjamin Peters(benjamin.peters***at***ovgu.de)
Sebastian Sager(sager***at***ovgu.de)

Abstract: 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.

Keywords: convexification · cutting-planes · McCormick relaxation · moment problem · nonlinear optimization · polynomial optimization · separation problem · sum-of-squares

Category 1: Nonlinear Optimization (Bound-constrained Optimization )

Category 2: Global Optimization (Theory )

Category 3: Linear, Cone and Semidefinite Programming

Citation: Institut für Mathematische Optimierung, Otto-von-Guericke Universität Magdeburg, Universitätsplatz 2, 39108 Magdeburg, Germany, 01/2019

Download: [PDF]

Entry Submitted: 01/16/2019
Entry Accepted: 01/16/2019
Entry Last Modified: 01/16/2019

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