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 low-dimensional subproblems efficiently and to high precision. Inequality constraints are handled directly, without explicitly maintaining slack variables in the algorithm. 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 over 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.
From: Jan Schwiddessen [view email]
[v1]
Sun, 27 Jul 2025 19:03:54 UTC (3,302 KB)
[v2]
Tue, 16 Jun 2026 20:37:05 UTC (3,305 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。