A Low-Rank Augmented Lagrangian Method for Doubly Nonnegative Relaxations of Mixed-Binary Quadratic Programs
Operations Research · 2026-05 · 74 (3) · 1626-1647
DOI: 10.1287/opre.2024.1137 ↗Kurz gefasst
Fachartikel in der Zeitschrift Operations Research, 2026-05. Verfasst von Di Hou und 2 weiteren Autor:innen. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 63 Literaturangaben.
Abstract (Originalsprache)
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.
Zitieren
APA
Hou, D., Tang, T., & Toh, K. (2026). A Low-Rank Augmented Lagrangian Method for Doubly Nonnegative Relaxations of Mixed-Binary Quadratic Programs. Operations Research, 74(3), 1626-1647. https://doi.org/10.1287/opre.2024.1137
Vancouver
Hou D, Tang T, Toh K. A Low-Rank Augmented Lagrangian Method for Doubly Nonnegative Relaxations of Mixed-Binary Quadratic Programs. Operations Research. 2026;74(3):1626-1647. doi:10.1287/opre.2024.1137
BibTeX
@article{Hou2026,
author = {Hou, Di and Tang, Tianyun and Toh, Kim-Chuan},
title = {A Low-Rank Augmented Lagrangian Method for Doubly Nonnegative Relaxations of Mixed-Binary Quadratic Programs},
journal = {Operations Research},
year = {2026},
volume = {74},
number = {3},
pages = {1626--1647},
doi = {10.1287/opre.2024.1137}
}
EUVIMED