EUVIMEDEUVIMED entdecken
Crossref

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

Di Hou, Tianyun Tang, Kim-Chuan Toh

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →