Convex Hull Results on Quadratic Programs with Non-Intersecting Constraints

Alexander Joyce (joyce4clemson.edu)
Boshi Yang (boshiyclemson.edu)

Abstract: Let F be a set defined by quadratic constraints. Understanding the structure of the closed convex hull cl(C(F)) := cl(conv{xx’ | x in F}) is crucial to solve quadratically constrained quadratic programs related to F. A set G with complicated structure can be constructed by intersecting simple sets. This paper discusses the relationship between cl(C(F)) and cl(C(G)), where G results by adding non-intersecting quadratic constraints to F. We prove that cl(C(G)) can be represented as the intersection of cl(C(F)) and half spaces defined by the added constraints. The proof relies on a complete description of the asymptotic cones of sets defined by a single quadratic equality and a partial characterization of the recession cone of cl(C(G)). Our proof generalizes an existing result for bounded quadratically defined F with non-intersecting hollows and several results on cl(C(G)) for G defined by non-intersecting quadratic constraints. The result also implies a sufficient condition for when the lifted closed convex hull of an intersection equals the intersection of the lifted closed convex hulls.

Keywords: Convex Hull, Non-Intersecting, Semidefinite Programming, Asymptotic Cone, Quadratically Constrained Quadratic Programming

Category 1: Linear, Cone and Semidefinite Programming

Citation:

Download: [PDF]

Entry Submitted: 05/28/2021
Entry Accepted: 05/28/2021
Entry Last Modified: 01/23/2022

Modify/Update this entry