Optimizing convex functions over nonconvex sets

2011/12/14 by Bienstock, Daniel, Michalka, Alexander
#90C26 #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1112.3290

Abstract

In this paper we derive strong linear inequalities for sets of the form (x, q) ∈ Rd × R : q ≥ Q(x), x ∈ Rd - int(P), where Q(x) : Rd → R is a quadratic function, P ⊂ Rd 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.

Related

• Explicit convex hull description of bivariate quadratic sets with indicator variables
• A Class of Problems where Dual Bounds Beat Underestimation Bounds
• A note on quadratic constraints with indicator variables: Convex hull description and perspective relaxation
• A non-convex relaxed version of minimax theorems
• On semidefinite descriptions for convex hulls of quadratic programs