Aggregations of Quadratic Inequalities and Hidden Hyperplane Convexity

DOI10.1137/22M1528215MaRDI QIDQ6136657zbMATH OpenOpenAlexFDO

Authors Grigoriy Blekherman, Santanu S. Dey, Shengding Sun

Publication date 17 January 2024

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2210.01722

zbMATH Keywords

quadratic programmingpolynomial optimizationconvex geometry

Mathematics Subject Classification ID

Quadratic programming (90C20) Nonconvex programming, global optimization (90C26) Polynomial optimization (90C23)

Abstract: We study properties of the convex hull of a set $S$ described by quadratic inequalities. A simple way of generating inequalities valid on $S$ is to take a nonnegative linear combinations of the defining inequalities of $S$. We call such inequalities aggregations. Special aggregations naturally contain the convex hull of $S$, and we give sufficient conditions for such aggregations to define the convex hull. We introduce the notion of hidden hyperplane convexity (HHC), which is related to the classical notion of hidden convexity of quadratic maps. We show that if the quadratic map associated with $S$ satisfies HHC, then the convex hull of $S$ is defined by special aggregations. To the best of our knowledge, this result generalizes all known results regarding aggregations defining convex hulls. Using this sufficient condition, we are able to recognize previously unknown classes of sets where aggregations lead to convex hull. We show that the condition known as positive definite linear combination together with hidden hyerplane convexity is a sufficient condition for finitely many aggregations to define the convex hull. All the above results are for sets defined using open quadratic inequalities. For closed quadratic inequalities, we prove a new result regarding aggregations giving the convex hull, without topological assumptions on $S$.

Recommendations

• Convex hull of two quadratic or a conic quadratic and a quadratic inequality
• On obtaining the convex hull of quadratic inequalities via aggregations
• Convex hulls of quadratically parameterized sets with quadratic constraints
• On the convex hull of convex quadratic optimization problems with indicators
• Convex hull presentation of A quadratically constrained set and its application in solving quadratic programming problems

Cites work

• scientific article; zbMATH DE number 1234104 (Why is no real title available?)
• A Survey of the S-Lemma
• A second-order cone based approach for solving the trust-region subproblem and its variants
• Aggregation-based cutting-planes for packing and covering integer programs
• Convex hull of two quadratic constraints is an LMI set
• Convex hull of two quadratic or a conic quadratic and a quadratic inequality
• Convexifications of rank-one-based substructures in QCQPs and applications to the pooling problem
• Convexity of quadratic transformations and its use in control and optimization
• Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs
• How to convexify the intersection of a second order cone and a nonconvex quadratic
• Linear Systems of Real Quadratic Forms. II
• Matrix Analysis
• On generalized surrogate duality in mixed-integer nonlinear programming
• On obtaining the convex hull of quadratic inequalities via aggregations
• On the Field of Values of a Matrix
• On the mapping of quadratic forms
• On the tightness of SDP relaxations of QCQPs
• Permanently going back and forth between the ``quadratic world and the ``convexity world in optimization
• Polynomial Solvability of Variants of the Trust-Region Subproblem
• Quadratic programs with hollows
• The convex hull of a quadratic constraint over a polytope

This page was built for publication: Aggregations of Quadratic Inequalities and Hidden Hyperplane Convexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6136657)