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.