# An Inexact Projected Gradient Method with Rounding and Lifting by Nonlinear Programming for Solving Rank-One Semidefinite Relaxation of Polynomial Optimization arXiv: https://arxiv.org/abs/2105.14033 ยท HTML: https://mlsanity.com/paper/2105.14033/ ## Key facts - Cited by 10 papers in the map (data through 14 Oct 2026). - Builds on 29 of its 97 references that are in the map. - First posted on arXiv 28 May 2021. ## Builds on (most cited first, 29 of 29) - [TEASER: Fast and Certifiable Point Cloud Registration](https://mlsanity.com/paper/2001.07715/) (2020) - [Manopt, a Matlab toolbox for optimization on manifolds](https://mlsanity.com/paper/1308.5200/) (2013) - [Graduated Non-Convexity for Robust Spatial Perception: From Non-Minimal Solvers to Global Outlier Rejection](https://mlsanity.com/paper/1909.08605/) (2019) - [SE-Sync: A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group](https://mlsanity.com/paper/1612.07386/) (2016) - [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014) - [The non-convex Burer-Monteiro approach works on smooth semidefinite programs](https://mlsanity.com/paper/1606.04970/) (2016) - [A Polynomial-time Solution for Robust Registration with Extreme Outlier Rates](https://mlsanity.com/paper/1903.08588/) (2019) - [ROBIN: a Graph-Theoretic Approach to Reject Outliers in Robust Estimation using Invariants](https://mlsanity.com/paper/2011.03659/) (2020) - [Scalable Semidefinite Programming](https://mlsanity.com/paper/1912.02949/) (2019) - [A Quaternion-based Certifiably Optimal Solution to the Wahba Problem with Outliers](https://mlsanity.com/paper/1905.12536/) (2019) - [Outlier-Robust Estimation: Hardness, Minimally Tuned Algorithms, and Applications](https://mlsanity.com/paper/2007.15109/) (2020) - [SDPNAL+: A Majorized Semismooth Newton-CG Augmented Lagrangian Method for Semidefinite Programming with Nonnegative Constraints](https://mlsanity.com/paper/1406.0942/) (2014) - [One Ring to Rule Them All: Certifiably Robust Geometric Perception with Outliers](https://mlsanity.com/paper/2006.06769/) (2020) - [In Perfect Shape: Certifiably Optimal 3D Shape Reconstruction from 2D Landmarks](https://mlsanity.com/paper/1911.11924/) (2019) - [Optimal Pose and Shape Estimation for Category-level 3D Object Perception](https://mlsanity.com/paper/2104.08383/) (2021) - [TSSOS: A Moment-SOS hierarchy that exploits term sparsity](https://mlsanity.com/paper/1912.08899/) (2019) - [On the local stability of semidefinite relaxations](https://mlsanity.com/paper/1710.04287/) (2017) - [Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension](https://mlsanity.com/paper/2003.03210/) (2020) - [Exact Semidefinite Formulations for a Class of (Random and Non-Random) Nonconvex Quadratic Programs](https://mlsanity.com/paper/1802.02688/) (2018) - [A convex relaxation to compute the nearest structured rank deficient matrix](https://mlsanity.com/paper/1904.09661/) (2019) - [On the tightness of SDP relaxations of QCQPs](https://mlsanity.com/paper/1911.09195/) (2019) - [Chordal decomposition in operator-splitting methods for sparse semidefinite programs](https://mlsanity.com/paper/1707.05058/) (2017) - [A Convergent 3-Block Semi-Proximal Alternating Direction Method of Multipliers for Conic Programming with 4-Type of Constraints](https://mlsanity.com/paper/1404.5378/) (2014) - [A hierarchy of spectral relaxations for polynomial optimization](https://mlsanity.com/paper/2007.09027/) (2020) - [Strong duality in Lasserre's hierarchy for polynomial optimization](https://mlsanity.com/paper/1405.7334/) (2014) - [An Efficient Inexact Symmetric Gauss-Seidel Based Majorized ADMM for High-Dimensional Convex Composite Conic Programming](https://mlsanity.com/paper/1506.00741/) (2015) - [On the R-superlinear convergence of the KKT residues generated by the augmented Lagrangian method for convex composite conic programming](https://mlsanity.com/paper/1706.08800/) (2017) - [Sparse Semidefinite Programs with Guaranteed Near-Linear Time Complexity via Dualized Clique Tree Conversion](https://mlsanity.com/paper/1710.03475/) (2017) - [The sum-of-squares hierarchy on the sphere, and applications in quantum information theory](https://mlsanity.com/paper/1908.05155/) (2019) ## Built on by (most cited first, 10 of 10) - [Object Pose Estimation with Statistical Guarantees: Conformal Keypoint Detection and Geometric Uncertainty Propagation](https://mlsanity.com/paper/2303.12246/) (2023) - [Scalable 3D Registration via Truncated Entry-wise Absolute Residuals](https://mlsanity.com/paper/2404.00915/) (2024) - [Estimation Contracts for Outlier-Robust Geometric Perception](https://mlsanity.com/paper/2208.10521/) (2022) - [Accelerating nuclear-norm regularized low-rank matrix optimization through Burer-Monteiro decomposition](https://mlsanity.com/paper/2204.14067/) (2022) - [A Provably Convergent and Practical Algorithm for Gromov--Wasserstein Optimal Transport](https://mlsanity.com/paper/2605.04175/) (2026) - [Tractable hierarchies of convex relaxations for polynomial optimization on the nonnegative orthant](https://mlsanity.com/paper/2209.06175/) (2022) - [Decomposed Global Optimization for Robust Point Matching with Low-Dimensional Branching](https://mlsanity.com/paper/2405.08589/) (2024) - [Convex Relaxation for Solving Large-Margin Classifiers in Hyperbolic Space](https://mlsanity.com/paper/2405.17198/) (2024) - [Global Truncated Loss Minimization for Robust and Threshold-Resilient Geometric Estimation](https://mlsanity.com/paper/2603.14796/) (2026) - [Fast and Effective Computation of Generalized Symmetric Matrix Factorization](https://mlsanity.com/paper/2603.19147/) (2026) ## Abstract (arXiv) We consider solving high-order semidefinite programming (SDP) relaxations of nonconvex polynomial optimization problems (POPs) that often admit degenerate rank-one optimal solutions. Instead of solving the SDP alone, we propose a new algorithmic framework that blends local search using the nonconvex POP into global descent using the convex SDP. In particular, we first design a globally convergent inexact projected gradient method (iPGM) for solving the SDP that serves as the backbone of our framework. We then accelerate iPGM by taking long, but safeguarded, rank-one steps generated by fast nonlinear programming algorithms. We prove that the new framework is still globally convergent for solving the SDP. To solve the iPGM subproblem of projecting a given point onto the feasible set of the SDP, we design a two-phase algorithm with phase one using a symmetric Gauss-Seidel based accelerated proximal gradient method (sGS-APG) to generate a good initial point, and phase two using a modified limited-memory BFGS (L-BFGS) method to obtain an accurate solution. We analyze the convergence for both phases and establish a novel global convergence result for the modified L-BFGS that does not require the objective function to be twice continuously differentiable. We conduct numerical experiments for solving second-order SDP relaxations arising from a diverse set of POPs. Our framework demonstrates state-of-the-art efficiency, scalability, and robustness in solving degenerate rank-one SDPs to high accuracy, even in the presence of millions of equality constraints.