In this paper we derive strong linear inequalities for sets of the form {(x, q) ∈ R^d × R : q ≥ Q(x), x ∈ R^d − int(P ) }, where Q(x) : R^d → R is a quadratic function, P ⊂ R^d and “int” denotes interior. Of particular but not exclusive interest is the case where P denotes a closed convex set. In this paper, we present several cases where it is possible to characterize the convex hull by efficiently separable linear inequalities.
Citation
Columbia University, November 2011