Optimization Online


Strong formulations for convex functions over nonconvex sets

Daniel Bienstock (dano***at***columbia.edu)
Alexander Michalka (admichalka***at***gmail.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society