Intersection Cuts for Polynomial Optimization

Bienstock, Daniel; Chen, Chen; Munoz, Gonzalo; Lodi, A.; Nagarajan, V

Abstract

We consider dynamically generating linear constraints (cutting planes) to tighten relaxations for polynomial optimization problems. Many optimization problems have feasible set of the form S boolean AND P, where S is a closed set and P is a polyhedron. Integer programs are in this class and one can construct intersection cuts using convex "forbidden" regions, or S-free sets. Here, we observe that polynomial optimization problems can also be represented as a problem with linear objective function over such a feasible set, where S is the set of real, symmetric matrices representable as outer-products of the form xx(T). Accordingly, we study outer-product-free sets and develop a thorough characterization of several (inclusion-wise) maximal intersection cut families. In addition, we present a cutting plane approach that guarantees polynomial-time separation of an extreme point in P \ S using our outer-product-free sets. Computational experiments demonstrate the promise of our approach from the point of view of strength and speed.

Más información

Título según WOS: ID WOS:000493314100006 Not found in local WOS DB
Título de la Revista: EDUCATING FOR A NEW FUTURE: MAKING SENSE OF TECHNOLOGY-ENHANCED LEARNING ADOPTION, EC-TEL 2022
Volumen: 11480
Editorial: SPRINGER INTERNATIONAL PUBLISHING AG
Fecha de publicación: 2019
Página de inicio: 72
Página final: 87
DOI:

10.1007/978-3-030-17953-3_6

Notas: ISI