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

Doubly nonnegative (DNN) programming problems are challenging to solve because of their huge number of $\mathrm{\Omega }(n^2)$ constraints and $\mathrm{\Omega }(n^2)$ variables. In this work, we introduce RiNNAL, a method for solving DNN relaxations of large-scale mixed-binary quadratic programs by leveraging their solutions’ possible low-rank property. RiNNAL is a globally convergent Riemannian augmented Lagrangian method (ALM) that penalizes the nonnegativity and complementarity constraints while preserving all other constraints as an algebraic variety. After applying the low-rank decomposition to the ALM subproblem, the resulting feasible region becomes an algebraic variety with favorable geometric properties. Our low-rank decomposition model improves upon the standard Burer-Monteiro (BM) model by equivalently reformulating most quadratic constraints after the BM decomposition into fewer, more manageable affine constraints, which also helps to alleviate Slater’s condition violations in the primal DNN problem. Moreover, we make the crucial step to show that the metric projection onto the algebraic variety, although nonconvex, can be transformed into a solvable convex optimization problem under certain regularity conditions, which can be ensured by a constraint reformulation strategy. RiNNAL is able to handle general semidefinite programming (SDP) with additional polyhedral cone constraints, thus serving as a prototype algorithm for solving general DNN problems. Numerous numerical experiments are conducted to validate the efficiency of the proposed RiNNAL method.

Funding: This research was supported by the Ministry of Education, Singapore, under its Academic Research Fund Tier 3 grant call [Grant MOE-2019-T3-1-010].

Supplemental Material: All supplemental materials, including the code, data, and files required to reproduce the results, are available at https://doi.org/10.1287/opre.2024.1137.