Learning context-aware adaptive solvers to accelerate quadratic programming

Haewon Jung, Junyoung Park, Jinkyoo Park

Abstract

Convex quadratic programming (QP) is an important sub-field of mathematical optimization. The alternating direction method of multipliers (ADMM) is a successful method to solve QP. Even though ADMM shows promising results in solving various types of QP, its convergence speed is known to be highly dependent on the step-size parameter $\rho$. Due to the absence of a general rule for setting $\rho$, it is often tuned manually or heuristically. In this paper, we propose CA-ADMM (Context-aware Adaptive ADMM) which learns to adaptively adjust $\rho$ to accelerate ADMM. CA-ADMM extracts the spatio-temporal context, which captures the dependency of the primal and dual variables of QP and their temporal evolution during the ADMM iterations. CA-ADMM chooses $\rho$ based on the extracted context. Through extensive numerical experiments, we validated that CA-ADMM effectively generalizes to unseen QP problems with different sizes and classes (i.e., having different QP parameter structures). Furthermore, we verified that CA-ADMM could dynamically adjust $\rho$ considering the stage of the optimization process to accelerate the convergence speed further.

Introduction

Quadratic Programming (QP) is a cornerstone of modern engineering, essential for applications ranging from portfolio optimization and robot control to machine learning models like Support Vector Machines (SVMs). The Alternating Direction Method of Multipliers (ADMM) is one of the most popular algorithms for solving these problems due to its robustness and efficiency. However, ADMM's convergence speed is notoriously sensitive to a user-defined step-size parameter, $\rho$.

Currently, practitioners rely on hand-tuned heuristics, such as those implemented in the OSQP solver, or simple adaptive rules. These heuristics often fail to generalize across diverse problem types or different stages of the optimization process. Previous attempts to apply Reinforcement Learning (RL) to this tuning problem were limited by treating $\rho$ as a global scalar and ignoring the specific structural context of the constraints. CA-ADMM addresses these limitations by learning to "see" the optimization problem's structure and history.

Methods: Context-Aware Adaptation

The core innovation of CA-ADMM is the extraction of spatio-temporal context to inform the adjustment of $\rho$. The architecture consists of three primary components:

  1. Spatial Context (Heterogeneous Graph Neural Network): The QP problem is represented as a graph where primal variables and dual variables (constraints) are nodes. The mathematical relationships defined by matrices $P$ and $A$ serve as edges. A Heterogeneous Graph Attention (HGA) network embeds this structure, allowing the model to understand how specific constraints interact.
  2. Temporal Context (RNN): To capture the evolution of the solver, a Gated Recurrent Unit (GRU) tracks the history of the solver’s state (primal and dual residuals) over previous iterations. This helps the model identify if the solver is stalled or approaching convergence.
  3. RL Policy: The model is trained using the Deep Deterministic Policy Gradient (DDPG) algorithm. To maintain computational efficiency, the model updates $\rho$ every 10 ADMM iterations rather than at every step.
Figure 1: The CA-ADMM architecture integrates spatial context from HGA and temporal context from GRU to adaptively tune the step-size parameter $\rho$.

Experimental Results

The authors evaluated CA-ADMM against state-of-the-art heuristics (OSQP) and previous RL baselines (RLQP) across a wide range of benchmarks, including synthetic canonical QPs (SVM, Lasso, Huber Fitting) and the Maros & Meszaros public dataset.

Generalization and Scalability

A key strength of CA-ADMM is its ability to generalize. While the model was trained on very small problems (10–15 variables), it successfully accelerated problems with up to 1,000 variables—a 100x increase in scale. As shown in the figure below, CA-ADMM maintains a consistently low iteration count as problem size grows, whereas the iteration counts for OSQP and RLQP increase significantly.

Figure 3: Comparison of ADMM iterations across problem sizes. CA-ADMM (blue) maintains a low, stable iteration count compared to OSQP (green) and RLQP (orange) as problem size increases beyond the training range (shaded).

Performance Highlights

  • Speedup: CA-ADMM achieved 2x to 8x faster convergence compared to the OSQP heuristic on in-domain benchmarks.
  • Zero-Shot Transfer: Models trained on random QPs performed effectively on entirely different problem classes like Lasso or SVM without additional training.
  • Public Benchmarks: On the 134 instances of the Maros & Meszaros dataset, CA-ADMM achieved the lowest iteration count in 85 cases.
  • Cross-Domain Generalization: When applied to Linear Programming (LP) problems, CA-ADMM solved them approximately 30x faster than OSQP in terms of iteration count.

Conclusion and Future Work

CA-ADMM demonstrates that learning the spatio-temporal context of an optimization problem can significantly accelerate solver convergence. While the neural network forward pass introduces per-iteration overhead, the substantial reduction in total iterations leads to overall wall-clock time improvements for large-scale problems. Future research will focus on optimizing the update interval and leveraging hardware acceleration to further reduce the computational cost of the GNN components.

Summary updated

Abstract

Convex quadratic programming (QP) is an important sub-field of mathematical optimization. The alternating direction method of multipliers (ADMM) is a successful method to solve QP. Even though ADMM shows promising results in solving various types of QP, its convergence speed is known to be highly dependent on the step-size parameter $\rho$. Due to the absence of a general rule for setting $\rho$, it is often tuned manually or heuristically. In this paper, we propose CA-ADMM (Context-aware Adaptive ADMM)) which learns to adaptively adjust $\rho$ to accelerate ADMM. CA-ADMM extracts the spatio-temporal context, which captures the dependency of the primal and dual variables of QP and their temporal evolution during the ADMM iterations. CA-ADMM chooses $\rho$ based on the extracted context. Through extensive numerical experiments, we validated that CA-ADMM effectively generalizes to unseen QP problems with different sizes and classes (i.e., having different QP parameter structures). Furthermore, we verified that CA-ADMM could dynamically adjust $\rho$ considering the stage of the optimization process to accelerate the convergence speed further.
BibTeX
@inproceedings{jung2023learning,
  author = {Haewon Jung and Junyoung Park and Jinkyoo Park},
  title = {{Learning context-aware adaptive solvers to accelerate quadratic programming}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=p5cvsNww5dB},
}
Figure