{"ID":2889994,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.20386","arxiv_id":"2507.20386","title":"The Augmented Mixing Method: Computing High-Accuracy Primal-Dual Solutions to Large-Scale SDPs via Column Updates","abstract":"The Burer-Monteiro factorization has become a powerful tool for solving large-scale semidefinite programs (SDPs), enabling recently developed low-rank solvers to tackle problems previously beyond reach. However, existing methods are typically designed to prioritize scalability over solution accuracy. We introduce the Augmented Mixing Method, a new algorithm that combines the Burer-Monteiro factorization with an inexact augmented Lagrangian framework and a block coordinate descent scheme. Our method emphasizes solving the resulting subproblems efficiently and to high precision. Inequality constraints are handled directly, without reformulation or introducing slack variables. A novel dynamic update strategy for the penalty parameter ensures that primal and dual feasibility progress remain balanced. This approach enables our method to compute highly accurate primal-dual solutions, even for large-scale SDPs with more than ten million inequality constraints. Despite lacking theoretical convergence guarantees, the Augmented Mixing Method shows strong practical performance with default parameters, across a wide range of SDP instances. It often produces more accurate primal-dual solutions than state-of-the-art interior-point methods and scales significantly better. Our open-source Julia implementation is memory-efficient, customizable, and supports arbitrary-precision arithmetic.","short_abstract":"The Burer-Monteiro factorization has become a powerful tool for solving large-scale semidefinite programs (SDPs), enabling recently developed low-rank solvers to tackle problems previously beyond reach. However, existing methods are typically designed to prioritize scalability over solution accuracy. We introduce the A...","url_abs":"https://arxiv.org/abs/2507.20386","url_pdf":"https://arxiv.org/pdf/2507.20386v1","authors":"[\"Daniel Brosch\",\"Jan Schwiddessen\",\"Angelika Wiegele\"]","published":"2025-07-27T19:03:54Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}