Aggregations of Quadratic Inequalities and Hidden Hyperplane Convexity

DOI10.1137/22M1528215zbMATH Open1529.90054arXiv2210.01722OpenAlexW4390613562MaRDI QIDQ6136657FDOQ6136657

Authors: Grigoriy Blekherman, Santanu S. Dey, Shengding Sun 

Publication date: 17 January 2024

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

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$.

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

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

zbMATH Keywords

quadratic programmingpolynomial optimizationconvex geometry

Mathematics Subject Classification ID

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

Cites Work

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

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)