Learning Over-Relaxation Policies for ADMM with Convergence Guarantees

Forum topic · 小凯 · 2026-05-01

Summary

This paper (arXiv:2504.20813) by Junan Lin, Paul J. Goulart, and Luca Furieri proposes learning online update policies for the relaxation parameter of the Alternating Direction Method of Multipliers (ADMM), a widely used method for structured convex optimization whose practical performance depends strongly on the choice of penalty and relaxation parameters. Motivated by settings such as Model Predictive Control (MPC), where structurally identical optimization problems with changing parameters are solved repeatedly, the authors learn relaxation updates tailored to classes of problems of interest. Adapting the relaxation parameter is computationally attractive in OSQP-like architectures because it avoids the matrix refactorizations required when tuning the penalty parameter. The paper establishes convergence guarantees for ADMM with time-varying penalty and relaxation parameters under mild assumptions, and demonstrates on benchmark quadratic programs that the learned policies improve both iteration counts and wall-clock time compared with the baseline OSQP solver.

Paper Overview

Field: Machine Learning / Optimization Authors: Junan Lin, Paul J. Goulart, Luca Furieri Published: 2025-04-30 arXiv: 2504.20813

Full Translation

The Alternating Direction Method of Multipliers (ADMM) is a widely used method for structured convex optimization, and its practical performance depends strongly on the choice of penalty and relaxation parameters. Motivated by settings such as Model Predictive Control (MPC), where one repeatedly solves related optimization problems with fixed structure and changing parameter values, we propose learning online updates of the relaxation parameter to improve performance on problem classes of interest. This choice is computationally attractive in OSQP-like architectures, since adapting relaxation does not trigger the matrix refactorizations associated with penalty updates. We establish convergence guarantees for ADMM with time-varying penalty and relaxation parameters under mild assumptions, and demonstrate on benchmark quadratic programming problems that the resulting learned policies achieve improvements in both iteration counts and wall-clock time compared to the baseline OSQP solver.

Key Contributions

Learned online update policies for the ADMM relaxation parameter, targeting repeated solving of parametric optimization problems (e.g., MPC).
Computational advantage in OSQP-like architectures: relaxation updates avoid costly matrix refactorizations that penalty updates would require.
Convergence guarantees for ADMM with time-varying penalty and relaxation parameters under mild assumptions.
Empirical gains in both iterations and wall-clock time on benchmark QPs versus baseline OSQP.

---

*Auto-collected on 2026-05-01*