Strong formulations for convex functions over nonconvex sets

Daniel Bienstock (danocolumbia.edu)
Alexander Michalka (admichalkagmail.com)

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

Keywords: nonconvex optimization, lifting, S-Lemma

Category 1: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 2: Global Optimization

Category 3: Linear, Cone and Semidefinite Programming (Second-Order Cone Programming )

Citation: Columbia University, November 2011

Download: [PDF]

Entry Submitted: 12/14/2011
Entry Accepted: 12/14/2011
Entry Last Modified: 12/06/2012

Modify/Update this entry