LEARNING CONTEXT-AWARE ADAPTIVE SOLVERS TO ACCELERATE QUADRATIC PROGRAMMING

Haewon Jung, Junyoung Park, Jinkyoo Park

TL;DR

The alternating direction method of multipliers (ADMM) is a popular first-order solver for convex quadratic programs (QPs), but its convergence speed critically hinges on choosing the right step-size parameter $\rho$. The authors introduce CA-ADMM (Context-aware Adaptive ADMM), a reinforcement learning framework that extracts both spatial structure (variable/constraint relationships via a heterogeneous graph) and temporal history (iteration trajectories via a GRU) to adaptively adjust a vector of $\rho$ values. Trained exclusively on tiny toy problems ($10 \le N \le 15$), CA-ADMM achieves a $2\times$ to $8\times$ reduction in iteration counts compared to standard solvers, generalizing seamlessly across problem types and scaling to problems with thousands of variables.

What Problem Does This Paper Address?

Convex quadratic programming appears throughout robotics, control, portfolio management, and machine learning. First-order methods like ADMM are widely preferred for large-scale QPs due to their low per-iteration computational footprint. However, tuning ADMM's penalty/step-size parameter $\rho$ is notoriously tricky: poor choices lead to slow convergence or oscillations.

Existing approaches rely on heuristic rules (such as residual balancing in OSQP) or narrow theoretical bounds that rarely apply to general problems. While recent work applied reinforcement learning (RLQP) to dynamically update $\rho$, it suffered from critical blind spots:

  1. It assigned a single global scalar $\rho$ rather than adapting step sizes per constraint.
  2. It ignored the problem’s cost and constraint matrices ($P, q, A$).
  3. It considered only the immediate optimization state, ignoring the temporal trajectory and non-stationary dynamics of the iterative process.

Methods

CA-ADMM frames the iterative solution process as a contextual Markov Decision Process (MDP), where the context represents the QP's structural parameters ($P, q, A, l, u$) and the ADMM operator:

  • Heterogeneous Graph Representation (Spatial Context): The QP is mapped to a directed heterogeneous graph. Primal nodes represent decision variables (tracking dual residuals and infinity norms), while dual nodes represent constraints (tracking primal residuals, multiplier values, bounds, and constraint types). Directed edges encode couplings: primal-to-primal edges reflect nonzero entries in the quadratic cost matrix $P$, while bipartite edges reflect nonzero entries in the constraint matrix $A$. Problems are scaled beforehand to ensure invariance to scalar reformulations.
  • Heterogeneous Graph Attention (HGA): A custom message-passing layer aggregates information across node and edge types using typed attention weights.
  • Recurrent Encoding (Temporal Context): To capture trajectory dynamics (analogous to momentum in classical optimization), the model maintains a history window ($l=3$). Node embeddings across steps are passed through a Gated Recurrent Unit (GRU) to produce a spatio-temporal context vector $C_t$.
  • Vectorized Policy via DDPG: An actor network $\pi_\theta(G_t, C_t)$ outputs an adaptive step-size vector $\rho_t \in \mathbb{R}^M$ for all $M$ constraints simultaneously. Actions are updated every 10 ADMM iterations to avoid the computational overhead of refactorizing the linear system at every step.
       [ QP State & Structure ]
                  │
        (Heterogeneous Graph)
                  │
         ┌────────┴────────┐
         ▼                 ▼
   Spatial GNN       History Window
         │                 │
         └────────┬────────┘
                  ▼
              GRU Cell  --> Spatio-Temporal Context (C_t)
                  ▼
         Actor Network (DDPG)
                  ▼
   Per-constraint step sizes (ρ_t) --> ADMM Linear Solver

Datasets

The authors evaluated the method across diverse synthetic and standard benchmarks:

  • Synthetic QP Domains: Seven standard problem formulations—Random QP, Equality-constrained QP (EqQP), Portfolio Optimization, Support Vector Machines (SVM), Huber Fitting, Optimal Control, and Lasso. Training was conducted on tiny instances ($10 \le N \le 15$).
  • Maros & Mészáros Benchmark Suite: 134 diverse, publicly available real-world and challenging QP benchmark instances.
  • Linear Programming (LP): 100 randomly generated LP instances (formulated as QPs with $P = 0$) to test out-of-class generalization.

Key Insights and Ideas

  • Per-Constraint Step Sizes Matter: Rather than forcing a single global step size, learning a distinct $\rho_m$ for each constraint allows the solver to balance primal and dual residuals across heterogeneous constraints effectively.
  • Temporal Context Prevents Premature Plateaus: Ablation studies showed that without the GRU, policies hit an early plateau in scheduling $\rho_t$. The temporal context is particularly essential when generalizing to large-scale problems ($N > 15$).
  • Exteme Generalization from Micro-Problems: Even though the policy was trained strictly on synthetic problems with 10–15 variables, the combination of graph permutation equivariance and temporal tracking allows zero-shot scaling to problems with $N = 1000$ variables without retraining.

Key Results

  • In-Domain Iteration Speedup: On synthetic benchmarks of size $10 \le N \le 15$, CA-ADMM achieved convergence in substantially fewer iterations than baselines (e.g., on Random QP: 27.44 iterations vs. 69.42 for RLQP and 81.12 for OSQP).
  • Scalability to Large Problems: On Random QPs scaled up to $N = 1000$ variables, CA-ADMM converged in $\sim 50$ iterations, whereas RLQP degraded to $\sim 260$ and OSQP required $\sim 130$.
  • Public Benchmark Superiority: On the 134 Maros & Mészáros benchmark problems, CA-ADMM achieved the lowest iteration count on 85 instances, outperforming both RLQP and OSQP.
  • Cross-Problem Transfer to Linear Programming: When evaluated on 100 random LP problems, CA-ADMM solved 100% of instances in an average of 79.94 iterations. OSQP only solved 58% (averaging 2432.74 iterations), and RLQP averaged 139.28 iterations.
  • Wall-Clock Trade-offs: For small problems ($N < 400$), neural network inference overhead makes OSQP faster in wall-clock seconds. However, for large-scale problems ($N \ge 400$), linear system factorization dominates per-step runtime; here, CA-ADMM's drastic iteration reduction leads to lower total computation time.

Limitations and Future Work

  • Inference Overhead on Small QPs: Graph construction and GNN/GRU passes add latency that offsets iteration gains on small problems where linear system solves are nearly instantaneous.
  • Failed Solves on Ill-Conditioned Problems: On certain challenging Maros & Mészáros instances (e.g., DTOC3, QGROW15), CA-ADMM, like other learning-based solvers, still fails to converge.
  • Heuristic Update Interval: Updating $\rho$ requires factorizing the KKT matrix. The authors fixed the update interval to every 10 iterations to balance factorization cost and adaptability; dynamically learning when to update $\rho$ remains an open direction.

Summary updated

Abstract

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},
}

Loading related content...

Figure