Strong formulations for convex functions over nonconvex sets

Published: 2011/12/14, Updated: 2012/12/06

Global Optimization, Nonsmooth Optimization, Second-Order Cone Programming lifting, nonconvex optimization, s-lemma Short URL: https://optimization-online.org/?p=11838

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.

Strong formulations for convex functions over nonconvex sets

Citation

Article