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

• 成果类型: Article
• 署名作者: Hou, Di; Tang, Tianyun; Toh, Kim-Chuan
• 署名单位: National University of Singapore; National University of Singapore
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2024.1137
• 发表日期: 2026
• 关键词: semidefinite programming; augmented Lagrangian; doubly nonnegative programming; algebraic variety; Riemannian Optimization; FACIAL REDUCTION ALGORITHM; FEASIBLE METHOD; semidefinite; optimization; DECOMPOSITION; cone; CONVERGENCE; complexity; QPS; sdp

摘要

Doubly nonnegative (DNN) programming problems are challenging to solve because of their huge number of ohm(n2) constraints and ohm(n2) variables. In this work, introduce RiNNAL, a method for solving DNN relaxations of large-scale mixed-binary quadratic programs by leveraging their solutions' possible low-rank property. RiNNAL 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 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 conducted to validate the efficiency of the proposed RiNNAL method.