# Cutting-planes for optimization of convex functions over nonconvex sets

Motivated by mixed-integer, nonlinear optimization problems, we derive linear inequality characterizations for sets of the form conv{(x, q ) \in R^d × R : q \in Q(x), x \in R^d - int(P )} where Q is convex and differentiable and P \subset R^d . We show that in several cases our characterization leads to polynomial-time separation algorithms that operate in the original space of variables, in particular when Q is a positive-definite quadratic and P is a polyhedron or an ellipsoid.

May 2013