# Parabolic Relaxation for Quadratically-constrained Quadratic Programming -- Part II: Theoretical & Computational Results

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

## Key facts

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

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

- [Semidefinite relaxations for certifying robustness to adversarial examples](https://mlsanity.com/paper/1811.01057/) (2018)
- [Safety Verification and Robustness Analysis of Neural Networks via Quadratic Constraints and Semidefinite Programming](https://mlsanity.com/paper/1903.01287/) (2019)
- [The non-convex Burer-Monteiro approach works on smooth semidefinite programs](https://mlsanity.com/paper/1606.04970/) (2016)
- [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)
- [Verification of Non-Linear Specifications for Neural Networks](https://mlsanity.com/paper/1902.09592/) (2019)
- [Rank-one Convexification for Sparse Regression](https://mlsanity.com/paper/1901.10334/) (2019)
- [Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage](https://mlsanity.com/paper/1702.06838/) (2017)
- [A System Level Approach to Controller Synthesis](https://mlsanity.com/paper/1610.04815/) (2016)
- [Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity](https://mlsanity.com/paper/1607.01151/) (2016)
- [Convergence Rate of Block-Coordinate Maximization Burer-Monteiro Method for Solving Large SDPs](https://mlsanity.com/paper/1807.04428/) (2018)
- [A bounded degree SOS hierarchy for polynomial optimization](https://mlsanity.com/paper/1501.06126/) (2015)
- [Optimization over Structured Subsets of Positive Semidefinite Matrices via Column Generation](https://mlsanity.com/paper/1512.05402/) (2015)
- [Separable and Localized System Level Synthesis for Large-Scale Systems](https://mlsanity.com/paper/1701.05880/) (2017)
- [The many faces of degeneracy in conic optimization](https://mlsanity.com/paper/1706.03705/) (2017)
- [Convex Relaxation of Bilinear Matrix Inequalities Part II: Applications to Optimal Control Synthesis](https://mlsanity.com/paper/1809.09817/) (2018)
- [Strong duality in conic linear programming: facial reduction and extended duals](https://mlsanity.com/paper/1301.7717/) (2013)
- [Sum of Squares Basis Pursuit with Linear and Second Order Cone Programming](https://mlsanity.com/paper/1510.01597/) (2015)
- [A Two-Step Pre-Processing for Semidefinite Programming](https://mlsanity.com/paper/1806.10868/) (2018)

## Abstract (arXiv)

In the first part of this work [32], we introduce a convex parabolic relaxation for quadratically-constrained quadratic programs, along with a sequential penalized parabolic relaxation algorithm to recover near-optimal feasible solutions. In this second part, we show that starting from a feasible solution or a near-feasible solution satisfying certain regularity conditions, the sequential penalized parabolic relaxation algorithm convergences to a point which satisfies Karush-Kuhn-Tucker optimality conditions. Next, we present numerical experiments on benchmark non-convex QCQP problems as well as large-scale instances of system identification problem demonstrating the efficiency of the proposed approach.