PaperlayerView exact revision on arXiv

Source-linked AI summary

An Adaptive Multi-Parameter ADMM Algorithm for Embedded MPC

Alberto Zaupa, Mikael Johansson

arXiv:2609.12992v1eess.SYcs.SYmath.OC

TL;DR

ADMM can be slow to reach high accuracy, which matters for embedded MPC’s strict execution-time budgets. This paper introduces adaptive multi-parameter ADMM with local superlinear convergence after active-set identification, and reports competitive MPC solver performance across latency and throughput.

  • Problem

    ADMM often reaches moderate accuracy quickly but converges much more slowly to high accuracy, while embedded MPC imposes strict execution-time budgets.

    Source: §I · p. 1

  • Method

    The paper adapts a multi-parameter ADMM penalty scheme and analyzes its local convergence after active-set identification.

    Source: §I · p. 1, §III · p. 3

  • Results

    The proposed solver is competitive with state-of-the-art MPC solvers in average and worst-case solve times, and its convergence is nearly insensitive to target tolerance across the reported benchmarks.

    Source: §I · p. 1, A. Comparison with OSQP · p. 3

  • Takeaways & Limitations

    The solver’s reported latency and throughput performance makes it well-suited to latency-critical embedded MPC applications.

    Source: §V · p. 7

    The convergence analysis is restricted to box-constrained problems, although numerical evidence suggests a similar result in the general setting.

    Source: §I · p. 1

Abstract

from arXiv · show

We introduce an adaptive multi-parameter variant of ADMM and prove that it exhibits local superlinear convergence once the set of active constraints has been identified. In simulations, the proposed algorithm consistently outperforms OSQP, a standard ADMM solver, in terms of iteration count. We then implement an MPC solver based on our method and compare its runtime against a broader selection of state-of-the-art algorithms. Evaluations on challenging benchmark problems reveal that our approach delivers competitive performance both in terms of average and worst-case solve times, without being limited to coarse tolerances, as is typically the case for standard ADMM implementations and first-order methods.

I. INTRODUCTION

The paper proposes adaptive multi-parameter ADMM with local superlinear convergence, then reports an MPC solver competitive with state-of-the-art solvers in latency and throughput. The work addresses ADMM’s slower progress at high accuracy in latency-constrained embedded MPC.

I. INTRODUCTION

  • ADMM is attractive for MPC because warm starts suit successive similar problems, but embedded MPC requires accurate solutions within strict execution-time budgets.The paper notes ADMM often finds moderate-accuracy solutions quickly but is much slower to reach high accuracy.Source: §I · p. 1
  • Adaptive multi-parameter ADMM is proved to converge locally superlinearly, with the analysis restricted to box-constrained problems.The introduction says numerical evidence suggests a similar result for the general setting.Source: §I · p. 1
  • In the illustrated problem, the proposed algorithm’s convergence speed increases dramatically after active-set identification.Figure 1 plots KKT residual norm over iterations for OSQP and the proposed algorithm.Source: Figure 1 · p. 1
  • The implemented solver matches or outperforms OSQP, qpOASES, HPIPM, and QPALM in MPC benchmarks, with competitive average and worst-case solve times.The paper describes this combination of throughput and latency performance as uncommon among MPC solvers.Source: §I · p. 1

A. Model Predictive Control

The section formulates linear MPC as a finite-horizon optimization problem with plant dynamics, operational constraints, and state and control costs. It describes condensed and sparse formulations with different structure for QP solvers.

A. Model Predictive Control

  • Linear MPC solves a finite-horizon optimization problem with given initial state, system dynamics, stagewise constraints, and stage and terminal costs.The stagewise inequalities enforce operational and physical limits on the plant and actuators.Source: A. Model Predictive Control · pp. 1–2
  • Condensing eliminates state variables, producing a QP with a dense Hessian that MPC solvers such as qpOASES can solve.The decision vector stacks controls over the prediction horizon.Source: A. Model Predictive Control · p. 2
  • Retaining states preserves the sparse, structured optimal-control formulation, enabling tailored Riccati-based linear algebra for efficient QP solves.The resulting decision vector stacks states and controls, while H and G are block diagonal.Source: A. Model Predictive Control · p. 2

B. ADMM

The section presents ADMM for convex optimization and its primal-dual residual stopping criterion. It describes diagonal penalty matrices that generalize the standard scalar penalty.

B. ADMM

  • ADMM solves the reformulated convex optimization problem through iterative updates using a positive definite diagonal penalty matrix.A diagonal matrix allows different penalty parameters for different constraint components.Source: B. ADMM · p. 2
  • The primal and dual KKT residuals define the stopping test: both infinity norms must fall below ε.Under standard assumptions on f, the iterates converge to a solution for any penalty matrix ρ.Source: B. ADMM · p. 2
  • Common penalty choices are a scalar multiple of the identity or a scalar multiple of a diagonal constraint preconditioner.For some QP classes, the optimal preconditioner and scalar penalty for fastest linear convergence can be computed.Source: B. ADMM · p. 2

C. Adaptive ADMM

ADMM convergence speed can depend strongly on penalty choice, so solvers often adapt a scalar penalty during execution. A prior multi-block scheme can improve convergence for sparse box-constrained MPC, but has narrower applicability.

C. Adaptive ADMM

  • Fixed-parameter ADMM can be highly sensitive to ρ, while finding the fastest penalty and preconditioner can be impractical; solvers therefore adapt a scalar penalty.Residual balancing is described as the simplest adaptive scheme.Source: C. Adaptive ADMM · p. 2
  • A prior multi-block scheme assigns separate penalties to blocks of G and updates them independently.The block indices are denoted by Ii.Source: C. Adaptive ADMM · p. 2
  • The multi-block scheme often improves convergence for sparse, box-constrained MPC, but gains are less significant for non-box-constrained problems and it is generally inapplicable to condensed problems.Source: C. Adaptive ADMM · p. 2

III. ADAPTIVE MULTI-PARAMETER ADMM

The proposed penalty update extends square-root residual balancing to per-constraint adaptation, with an active-set-aware correction and safeguards for stability. Numerical experiments find the square-root rule often accelerates convergence and is more stable than the more aggressive SRA update.

III. ADAPTIVE MULTI-PARAMETER ADMM

  • The proposed update applies a per-constraint square-root residual-balancing rule for box-constrained problems.For general constraint matrices, it instead uses each constraint copy’s movement as a per-constraint precursor of the dual residual.Source: §III · p. 3
  • The square-root variant generally converged faster than dead-band residual balancing with fewer tuning parameters, while SRA was more aggressive and often diverged.SRA sometimes converged slightly faster than the proposed update.Source: §III · p. 3
  • The correction mildly decreases penalties for inactive constraints and increases them for active constraints, using whether the corresponding dual variable is essentially zero.The paper characterizes this as an active-set-aware correction, not a separate adaptation principle.Source: §III · p. 3
  • Clipping penalties to a prescribed interval and under-relaxing in the log domain bounds log ρ and reduces oscillations.Smaller α values interpolate geometrically between the previous penalty and the clipped candidate.Source: §III · p. 3

A. Comparison with OSQP

Across the five benchmarks, the proposed algorithm converges substantially faster than OSQP and is nearly insensitive to target tolerance. The reported convergence acceleration follows active-set identification, and OSQP misses the termination criteria on Aircraft at the two tightest listed tolerances.

A. Comparison with OSQP

  • The comparison uses single, non-warm-started instances of five benchmark MPC problems, with OSQP’s penalty-update frequency matched to the proposed method at K = 5.The authors selected K = 5 from update frequencies {5, 10, 15, 20, 25, 50} as fastest for OSQP.Source: A. Comparison with OSQP · p. 3
  • Across all benchmarks, the proposed algorithm converges substantially faster than OSQP and is nearly insensitive to target tolerance ε.The table compares iterations to convergence across five problems and tolerances; OSQP cannot meet the Aircraft criteria at ε ∈ {10−6, 10−9}.Source: A. Comparison with OSQP · p. 3, Table I · p. 4
  • After the dual-variable signs cease changing and the solution’s active set is identified, convergence accelerates sharply.The observations appear faster than linear, with each penalty update further accelerating convergence; existing active-set results do not cover adaptive ρ updates.Source: A. Comparison with OSQP · pp. 3–4
  • Figure 2 presents KKT residuals for the proposed algorithm on the Atlas problem.Source: Figure 2 · p. 4

B. Theoretical Analysis

The analysis characterizes ADMM after active-set identification and proves local superlinear convergence under stated box-constraint and smoothness assumptions. It links the rate to penalty dynamics that increase active-constraint penalties and decay inactive ones.

B. Theoretical Analysis

  • The proof assumes box constraints with G = I, post-identification iterates, and updates to ρ at every iteration.The theorem also uses idealized ρ bounds that remove clipping and assumes local smoothness and positive definiteness.Source: B. Theoretical Analysis · pp. 4–5
  • Only a couple of ρ updates, every five iterations, bring the ∞-norm KKT residual below 10^-9 after active-set identification.Before identification, the residuals are several orders of magnitude from convergence.Source: Table II · p. 4
  • After identification, penalties for active constraints increase while those for inactive constraints decay to zero, the dynamics driving superlinear convergence.The analysis characterizes this post-identification regime rather than proving that identification occurs.Source: B. Theoretical Analysis · pp. 4–5
  • After active-set identification, the proposed update yields an e^-Theta(k^2) error bound that extends to the KKT residuals.The theorem assumes a locally C2 objective with positive-definite Hessian and iterates remaining in the neighborhood.Source: B. Theoretical Analysis · pp. 4–6
  • The authors extend the rate to the sparse formulation by relating its iterates and penalty updates to those of the condensed formulation.Practical clipping remains necessary to prevent numerical ill-conditioning, although the theorem removes its effect.Source: B. Theoretical Analysis · p. 6

IV. HIGH PERFORMANCE IMPLEMENTATION

The implementation offers sparse and condensed MPC solvers, with the sparse version exploiting optimal-control structure. Across the reported benchmarks, the solvers are competitive in solve time, while warm starts can avoid penalty-update refactorizations.

IV. HIGH PERFORMANCE IMPLEMENTATION

  • Both implementations use MPC-specialized dense linear algebra kernels, while the sparse solver also exploits the OCP structure of the ADMM w-update.Source: §IV · p. 7
  • Changing the penalty can require refactorizing H + G^Tρ(k)G, but warm starts often yield convergence before the first update, avoiding that solve-time cost.The same consideration applies to the sparse formulation.Source: §IV · p. 7
  • For all comparisons, every solver uses termination tolerance ε = 10^-6; the first version is compared with HPIPM on Atlas and Quadruped, and the second with OSQP, qpOASES, and QPALM on remaining problems.Source: §IV · p. 7
  • The sparse solver outperforms HPIPM on Atlas and Quadruped, particularly in average solve time.The comparison reports average and worst-case solve times; Figure 3 covers the whole Atlas simulation.Source: §IV · p. 7, Table III · p. 7, Figure 3 · p. 7
  • The dense solver is competitive in latency and throughput against OSQP, qpOASES, and QPALM on the remaining benchmarks.On C.o.m., performance is slightly worse than QPALM; on Aircraft, OSQP and QPALM fail within the maximum iteration budget.Source: §IV · p. 7, Table IV · p. 7

V. CONCLUSION

The paper concludes that its adaptive multi-parameter ADMM algorithm converges locally superlinearly and performs compellingly on latency and throughput. Further work will extend the convergence result and investigate transient behavior.

V. CONCLUSION

  • The adaptive multi-parameter ADMM algorithm achieves significantly faster convergence than other ADMM variants and has a proved local superlinear rate.Source: §V · p. 7
  • The proposed algorithm shows compelling latency and throughput performance against state-of-the-art MPC solvers for embedded MPC applications.Source: §V · p. 7
  • Future work will extend the convergence result to non-box-constrained problems and analyze transient behavior, including active-set identification.The authors also plan to release the high-performance implementation as an open-source MPC package.Source: §V · p. 7
Loading 2609.12992v1…