A Low-Rank Augmented Lagrangian Method for Doubly Nonnegative Relaxations of Mixed-Binary Quadratic Programs

Low-Rank Approaches to Large-Scale DNN Optimization Doubly nonnegative (DNN) relaxations are a powerful tool for approximating large-scale mixed-binary quadratic programs, but their size—often involving millions of constraints—makes them difficult to solve. We propose RiNNAL, a Riemannian augmented Lagrangian method that exploits the low-rank structure often present in optimal solutions. By applying a low-rank decomposition, RiNNAL reformulates most quadratic constraints into simpler affine ones, reducing problem complexity and mitigating issues caused by violations of Slater’s condition. A key innovation is showing that the required metric projection onto a certain algebraic variety, although nonconvex in form, can be solved as a convex optimization problem under mild regularity conditions, enforced through constraint reformulation. RiNNAL is versatile, handling not only DNN relaxations but also general semidefinite programs with polyhedral constraints. Extensive experiments on challenging benchmarks confirm its efficiency and robustness, making RiNNAL a promising solver for large-scale optimization problems.