CS Paper Radar

An Adaptive Multi-Parameter ADMM Algorithm for Embedded MPC

Alberto Zaupa, Mikael Johansson

eess.SY math.OC ·submitted 2026-09-11 15:54 UTC · v1
publishedbenchmark

Abstract

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.

Comment
Accepted for publication at CDC 2026

Closest papers

Nearest neighbours by meaning across the whole index.

Parallelizable Interior-Point ADMM for Block-Structured Nonconvex Programs

cs.LG math.OC ·2026-11-16 ·Zherong Pan
similarity 0.61
Abstract

Physics simulation is an increasingly important computational primitive for AI, and local--global/ADMM splitting exposes its parallel structure but lacks matching finite-time convergence guarantees. We close this gap with two ADMM variants, Interior-Point ADMM (IP-ADMM), for block-structured nonconvex composite programs with smooth nonlinear inequality and affine constraints. A one-sided finite-activation wall keeps each constraint split state strictly feasible while the original-space infeasibility vanishes, giving closed-form constraint updates, one proximal call per objective block, and one equality-constrained quadratic consensus solve per iteration. \rev{To our knowledge, this makes IP-ADMM the first single-loop method that updates nonconvex inequality constraints locally and in parallel with finite-time convergence guarantees.} Ordinary IP-ADMM attains a CQ-free best-iterate weak-KKT rate of $O(K^{-1/3})$ or a banded Fritz--John rate of $O(K^{-1/4})$, which converts to KKT at $O(K^{-1/4})$ under a uniform constraint qualification; these are nearby-point certificates that reduce to conventional KKT for smooth blocks. A checkpoint variant, IP-ADMM-Ckpt, improves the asymptotic KKT exponent to $O(K^{-1/3})$. We also show how the bounds scale with the objective- and constraint-block counts and the coupling norm.

0.24

A Local-Linearly Convergent Algorithm for Nonconvex Equality-Constrained Optimization

cs.LG math.OCstat.ML ·2026-08-12 ·Frank E. Curtis, Lingjun Guo, Daniel P. Robinson
similarity 0.58
Abstract

For solving nonconvex equality-constrained optimization problems, a recent Gradient-Eigenstep Algorithm by Goyens et al.~is an iteration-efficient approach, based on minimizing Fletcher's augmented Lagrangian function, for finding an approximate second-order stationary point from an arbitrary starting point. In this paper, the analysis of this algorithm is extended, offering a two-fold contribution. First, it is shown that a local-linear rate of convergence can be obtained by this method if it is initiated sufficiently close to a strong second-order stationary point and employs a sufficiently small step-size parameter and sufficiently large penalty parameter. In this case, the algorithm reduces to a gradient descent algorithm applied to minimize Fletcher's augmented Lagrangian. Second, as a particularly useful application of the first result, it is shown that the Gradient-Eigenstep algorithm can be used as an iteration-efficient subproblem solver in the context of a progressive sampling strategy for solving equality-constrained optimization problems when the objective and constraint functions are defined by large sample averages, ultimately offering an algorithm with an improved worst-case sample complexity when compared to an approach that solves a full-sample problem directly.

0.04

AccelMPC: High-Rate, Low-Power FPGA-Accelerated Model Predictive Control for Tiny Drones

cs.RO eess.SY ·2026-09-08 ·Andrea Grillo, Brian Plancher
code/data similarity 0.55
Abstract · 8 pages, 8 figures, 2 tables

Unlocking the potential of tiny aerial robots requires order of magnitude improvements in the performance of embedded edge control. In particular, although recent cached model predictive control (MPC) solvers can handle the fast system dynamics and complex constraints required for agile drone flight, their computational demands remain prohibitive for resource-constrained robots, forcing prior implementations to operate at reduced control rates. AccelMPC overcomes this challenge through an end-to-end co-design approach that jointly optimizes the solver algorithm, numerical representation, hardware mapping, and physical integration. AccelMPC pairs a co-designed FPGA-accelerated alternating direction method of multipliers (ADMM)-based MPC solver with a custom 6g PCB, providing high-bandwidth communication for deployment on a 35g Crazyflie. Hardware experiments demonstrate 1 kHz onboard constrained MPC with dynamic obstacles, up to 15.6x faster solve times and 195.4x improvement in energy-delay product over state-of-the-art embedded microcontroller-based solvers, all while scaling to optimization problems with over 20,000 optimization variables and a comparable number of constraints. We release our PCB design files, firmware, and FPGA solver code open source.

0.42

AI-Assisted Discovery and Construction of a Counterexample to the Convergence of Three-Block ADMM with the Identity Matrix as its Third Constraint Block

cs.AI math.OC ·2026-08-14 ·Kenan Xu, Xiangfeng Wang
similarity 0.54
Abstract · 34 pages

The alternating direction method of multipliers (ADMM), as a landmark algorithm, has attracted tremendous research attention and extensive practical applications over the past two decades. It is well known that, although the two-block ADMM enjoys well-established theoretical convergence guarantees, its direct extension to the three-block case may fail to converge, as demonstrated by existing counterexamples [5]. However, to the best of our knowledge, the case in which the third constraint block is the identity remains unresolved: the existing literature gives neither a general convergence proof nor a counterexample for this subclass. In this paper, we give a negative answer: direct three-block ADMM may fail even when the first two blocks are strongly convex quadratics. Using Codex with GPT-5.6 Sol, we construct an explicit rational counterexample candidate and verify it along a piecewise-affine reduction path; exact checks show that direct three-block ADMM on this instance produces a bounded nonconvergent orbit of period 66. Within the same Codex workflow, we further guide a study of multiplier relaxation and clarify when convergence can be restored at the fixed-instance and class levels: a problem-dependent small dual step can restore convergence, whereas no positive relative step works uniformly over the whole class. Furthermore, we also test the recent Kimi Code with Kimi K3 model without the Codex candidate or project-specific route guidance; along a different path it produces an exact locally attracting period-23 certificate, convertible to an equivalent all-identity instance. The comparison suggests that different research-harness configurations can shape the mathematical objects explored and the certificates pursued.

0.40

Efficient Learning of Differentiable MPC Policies on the GPU via Smoothed ADMM and First-Order Reinforcement Learning

cs.RO cs.AIcs.LG ·2026-10-13 ·Jianghan Zhang, Roland Schwan, Gabriel Bravo-Palacios, John Zhang, Thomas Lew +1 more
code/data similarity 0.54
Abstract

Differentiable model predictive control (MPC) enables structured, constraint-aware policies to be optimized end-to-end. However, learning MPC policies faces two bottlenecks: (1) nonsmooth sensitivities at active-set transitions and (2) expensive policy evaluation, since each requires an optimization solve. We first introduce SmoothedTurboMPC, a GPU-parallel differentiable MPC solver combining sequential quadratic programming (SQP) with a log-barrier-smoothed alternating direction method of multipliers (ADMM) inner solver. Its design enables smooth gradients, exact sensitivities at convergence, and efficient execution on GPUs. Second, to efficiently train MPC policies, we pair our solver with first-order reinforcement learning (FORL) using Short-Horizon Actor-Critic (SHAC), which reuses rollout MPC solutions instead of repeatedly re-evaluating them. Comparisons with state of the art solvers show that the approach achieves up to $4.4\times$ higher end-to-end training throughput. On a vehicle racing task, our method achieves higher returns than MPC PPO with a $46\times$ speedup, training on 3.3 million transitions in only 7 minutes. Finally, we use the framework to train a more reliable MPC racing policy via RL with domain randomization, and validate it on a full-scale race car. We integrate our advances into the open-source TurboMPC solver.

0.20

Accelerating Branch MPC with Two-Level Parallel Direct Solves on GPUs

eess.SY math.OC ·2026-09-24 ·Fenglong Song, Luyao Zhang, Liang Wu, Ján Drgoňa, Colin N. Jones
similarity 0.52
Abstract

Branch model predictive control optimizes multiple future trajectories coupled through shared decisions, with computational demands increasing as the number of scenarios and prediction horizon grow. We present a GPU-accelerated direct linear solver for branch MPC formulations in which all trajectories share a single root decision node and evolve independently thereafter. By operating at the linear-algebra level, the solver provides a reusable backend for multiple optimization algorithms whose reduced systems have the required symmetric positive-definite structure. The solver exploits two levels of parallelism: across scenarios and along each prediction horizon. A tailored variable ordering enables horizon-parallel Cholesky factorization while preserving a single root-tail coupling block per scenario in the factor. Numerical experiments demonstrate substantial speedups over state-of-the-art sparse direct solvers, achieving factorization speedups of up to 6.0$\times$ over cuDSS and 27.6$\times$ over eight-thread PARDISO, with triangular solve speedups of up to 3.5$\times$ and 15.8$\times$, respectively.

0.16

lapanda: A Matrix-Free Differentiable Solver for Nonconvex Constrained Optimization Layers

cs.LG math.OCeess.SY ·2026-09-27 ·Yuankun Chen, Zifei Nie, Kangyu Lin, Ján Drgoňa, Liang Wu
similarity 0.52
Abstract

Differentiable optimization brings the structural guarantees of mathematical optimization to network pipelines, allowing them to be trained end-to-end. However, its application remains challenging for nonconvex constrained problems, as existing differentiable solvers often suffer from limited modeling expressiveness due to their reliance on specialized problem structures, while also incurring substantial computation time and memory overhead in both the forward and backward passes. To address these challenges, we propose lapanda, a matrix-free differentiable solver for nonconvex optimization with general constraints. It reformulates the problem to a sequence of augmented Lagrangian subproblems, each handled by a first-order inner solver through a proximal averaged quasi-Newton algorithm with adaptive linesearch, thus enabling efficient forward optimization. We establish local well-posedness of the solution map and convergence of the outer iterations, and further derive a sensitivity alignment between the original problem and the final subproblem in the backward pass, demonstrating that the subproblem sensitivity, which can be computed efficiently in a matrix-free manner, provides a principled approximation to the exact optimizer sensitivity. We evaluate lapanda on nonconvex constrained Rosenbrock benchmarks, imitation learning with several representative constrained optimal control problems, and embedded robotic obstacle-avoidance tasks. Compared with state-of-the-art differentiable solvers, lapanda delivers substantial reductions in computation time and memory footprint while maintaining reliable constraint satisfaction and learning performance.

0.18

An Adaptive, Parallel, and Inexact Newton Method for Large-scale Nonlinear Optimal Control

eess.SY math.OC ·2026-09-27 ·Luke Bhan, Michael W. Mahoney, Sen Na
theory similarity 0.52
Abstract · 31 pages

We design adaptive overlapping temporal decomposition (AOTD), a parallel sequential quadratic programming (SQP) method for long-horizon nonlinear optimal control problems (OCPs). As designed, AOTD is the first overlapping temporal decomposition (OTD) algorithm that adapts the overlap size online, eliminating the need to fix a suitable overlap a priori. Specifically, at each iteration, it partitions the long horizon into overlapping nonlinear subproblems, performs one SQP step on each in parallel, and adaptively selects both the overlap size and the accuracy to which the resulting local KKT systems are solved. Two conditions govern the accepted step: an adaptive residual condition bounding the distance from the concatenated inexact direction to the exact Newton direction of the full problem, and a descent condition on the adaptive penalty parameters that certifies descent for a carefully chosen exact augmented Lagrangian. The residual condition is solver independent and accommodates both deterministic iterative solvers and randomized sketching solvers. Under standard regularity assumptions, we prove that the KKT residual converges to zero from any initialization and establish a local linear rate for sequences converging to a strict local minimizer. We validate AOTD on a power-system frequency regulation OCP and a Burgers PDE OCP, attaining a reduction in estimated FLOPs of approximately $2.5\times$ to the best fixed-overlap variant while converging across multiple horizon lengths with a single parameter setting.

0.28