# Parabolic Relaxation for Quadratically-constrained Quadratic Programming -- Part I: Definitions & Basic Properties

arXiv: https://arxiv.org/abs/2208.03622 · HTML: https://mlsanity.com/paper/2208.03622/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 90 references that are in the map.
- First posted on arXiv 7 Aug 2022.

## Builds on (most cited first, 23 of 23)

- [Tightness of the maximum likelihood semidefinite relaxation for angular synchronization](https://mlsanity.com/paper/1411.3272/) (2014)
- [SDPNAL+: A Majorized Semismooth Newton-CG Augmented Lagrangian Method for Semidefinite Programming with Nonnegative Constraints](https://mlsanity.com/paper/1406.0942/) (2014)
- [DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization](https://mlsanity.com/paper/1706.02586/) (2017)
- [A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics](https://mlsanity.com/paper/1908.05209/) (2019)
- [Rank-one Convexification for Sparse Regression](https://mlsanity.com/paper/1901.10334/) (2019)
- [Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity](https://mlsanity.com/paper/1607.01151/) (2016)
- [Scalable Robust Matrix Recovery: Frank-Wolfe Meets Proximal Methods](https://mlsanity.com/paper/1403.7588/) (2014)
- [Exact Semidefinite Formulations for a Class of (Random and Non-Random) Nonconvex Quadratic Programs](https://mlsanity.com/paper/1802.02688/) (2018)
- [A bounded degree SOS hierarchy for polynomial optimization](https://mlsanity.com/paper/1501.06126/) (2015)
- [Guaranteed Globally Optimal Planar Pose Graph and Landmark SLAM via Sparse-Bounded Sums-of-Squares Programming](https://mlsanity.com/paper/1809.07744/) (2018)
- [Phase retrieval for imaging problems](https://mlsanity.com/paper/1304.7735/) (2013)
- [Lasserre hierarchy for large scale polynomial optimization in real and complex variables](https://mlsanity.com/paper/1709.04376/) (2017)
- [Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone](https://mlsanity.com/paper/1312.6643/) (2013)
- [Sequential Relaxation of Unit Commitment with AC Transmission Constraints](https://mlsanity.com/paper/1809.09812/) (2018)
- [Convex Relaxation of Bilinear Matrix Inequalities Part II: Applications to Optimal Control Synthesis](https://mlsanity.com/paper/1809.09817/) (2018)
- [SDP-quality bounds via convex quadratic relaxations for global optimization of mixed-integer quadratic programs](https://mlsanity.com/paper/2106.13721/) (2021)
- [Robust Stability Analysis of Sparsely Interconnected Uncertain Systems](https://mlsanity.com/paper/1311.2602/) (2013)
- [On the closure of the completely positive semidefinite cone and linear approximations to quantum colorings](https://mlsanity.com/paper/1502.02842/) (2015)
- [A Spatial Branch-and-Cut Method for Nonconvex QCQP with Bounded Complex Variables](https://mlsanity.com/paper/1705.09057/) (2017)
- [A Scalable Semidefinite Relaxation Approach to Grid Scheduling](https://mlsanity.com/paper/1707.03541/) (2017)
- [Penalized Parabolic Relaxation for Optimal Power Flow Problem](https://mlsanity.com/paper/1809.09809/) (2018)
- [Convex Relaxation of Bilinear Matrix Inequalities Part I: Theoretical Results](https://mlsanity.com/paper/1809.09814/) (2018)
- [Penalized Semidefinite Programming for Quadratically-Constrained Quadratic Optimization](https://mlsanity.com/paper/2004.14328/) (2020)

## Abstract (arXiv)

For general quadratically-constrained quadratic programming (QCQP), we propose a parabolic relaxation described with convex quadratic constraints. An interesting property of the parabolic relaxation is that the original non-convex feasible set is contained on the boundary of the parabolic relaxation. Under certain assumptions, this property enables one to recover near-optimal feasible points via objective penalization. Moreover, through an appropriate change of coordinates that requires a one-time computation of an optimal basis, the easier-to-solve parabolic relaxation can be made as strong as a semidefinite programming (SDP) relaxation, which can be effective in accelerating algorithms that require solving a sequence of convex surrogates. The majority of theoretical and computational results are given in the next part of this work [57].