Pith. sign in

REVIEW 5 cited by

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

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2401.12490 v3 pith:4RLZ2DNJ submitted 2024-01-23 math.OC cs.NAmath.NA

Renato D.C. Monteiro , Arnesh Sujanani , Diego Cifuentes This is my paper · ORCID
classification math.OCcs.NAmath.NA
keywords methodhallarlow-rankaugmentedfindshybridinexactinstances
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

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)\approx (10^6,10^7)$ within $10^{-5}$ relative precision.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 5 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. New Understandings and Computation on Augmented Lagrangian Methods for Low-Rank Semidefinite Programming

    math.OC 2025-05 conditional novelty 7.0 of 10

    Augmented Lagrangian subproblems inherit low-rankness, strict complementarity, and quadratic growth from a primal simple SDP, making Burer-Monteiro gradient descent converge linearly.

  2. Solving Imperfect-Recall Games via Sum-of-Squares Optimization

    cs.GT 2026-02 conditional novelty 6.0 of 10

    Moment-SOS hierarchies provably compute behavioral optima/equilibria in imperfect-recall games, with exact convergence at level ℓ+1 for non-absentminded single-player games.

  3. RiNNAL+: a Riemannian ALM Solver for SDP-RLT Relaxations of Mixed-Binary Quadratic Programs

    math.OC 2025-07 conditional novelty 5.0 of 10

    DNN and SDP-RLT relaxations of mixed-binary quadratic programs are proved to give identical bounds, and the new hybrid Riemannian solver RiNNAL+ solves the smaller SDP-RLT form at n = 5000, typically 10 to 100 times f...

  4. A Bundle-based Augmented Lagrangian Framework: Algorithm, Convergence, and Primal-dual Principles

    math.OC 2025-02 conditional novelty 5.0 of 10

    BALA, a single-loop bundle-based augmented Lagrangian algorithm, achieves sublinear convergence for convex constrained problems and linear convergence for a class of conic programs including semidefinite programs.

  5. Maximal entropy in the moment body

    math.OC 2025-07 conditional novelty 4.0 of 10

    After preconditioning the defining linear map, global minimization of the dual log-partition function certifies moment body membership, and L-BFGS handles dense n=m=1000 instances in seconds.

Pith tools