Optimization Online


Convex Hull Results on Quadratic Programs with Non-Intersecting Constraints

Alexander Joyce (joyce4***at***clemson.edu)
Boshi Yang (boshiy***at***clemson.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


Download: [PDF]

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

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