A Low-Rank Augmented Lagrangian Method for Doubly Nonnegative Relaxations of Mixed-Binary Quadratic Programs
提出RiNNAL算法，利用低秩结构将双非负松弛中的二次约束转化为仿射约束，降低复杂度并解决Slater条件违反问题，适用于大规模混合二元二次规划。
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.