# A low-rank augmented Lagrangian method for large-scale semidefinite programming based on a hybrid convex-nonconvex approach

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jan 2024.

## Built on by (most cited first, 4 of 4)

- [Stochastic Constrained Decentralized Optimization for Machine Learning with Fewer Data Oracles: a Gradient Sliding Approach](https://mlsanity.com/paper/2404.02511/) (2024)
- [Scalable Second-order Riemannian Optimization for K-means Clustering](https://mlsanity.com/paper/2509.21675/) (2025)
- [Suboptimality bounds for trace-bounded SDPs enable a faster and scalable low-rank SDP solver SDPLR+](https://mlsanity.com/paper/2406.10407/) (2024)
- [A User Manual for cuHALLaR: A GPU Accelerated Low-Rank Semidefinite Programming Solver](https://mlsanity.com/paper/2508.15951/) (2025)

## Abstract (arXiv)

This paper introduces HALLaR, a new first-order method for solving large-scale semidefinite programs (SDPs) with bounded domain. HALLaR is an inexact augmented Lagrangian (AL) method where the AL subproblems are solved by a novel hybrid low-rank (HLR) method. The recipe behind HLR is based on two key ingredients: 1) an adaptive inexact proximal point method with inner acceleration; 2) Frank-Wolfe steps to escape from spurious local stationary points. In contrast to the low-rank method of Burer and Monteiro, HALLaR finds a near-optimal solution (with provable complexity bounds) of SDP instances satisfying strong duality. Computational results comparing HALLaR to state-of-the-art solvers on several large SDP instances arising from maximum stable set, phase retrieval, and matrix completion show that the former finds higher accurate solutions in substantially less CPU time than the latter ones. For example, in less than 20 minutes, HALLaR can solve a maximum stable set SDP instance with dimension pair (n,m)≈ (106,107) within 10-5 relative precision.