CS Paper Radar

FanCyqlone: A Parallelized Solver for Multi-Horizon Optimal Control

Matisse Teuwen, Pieter Pas, Mathijs Schuurmans, Panagiotis Patrinos

eess.SY math.OC ·submitted 2026-11-12 18:19 UTC · v1

Abstract

Multi-horizon optimal control aims to select optimal control sequences simultaneously for several possible future scenarios, ensuring consistency at the first stage. While this enables advanced model predictive control schemes that explicitly handle prediction uncertainty, solving these problems tends to be costly. We introduce FanCyqlone, a linear solver that exploits parallelism across both time steps and scenario branches. The method builds on Cyqlone to compute the contribution of each branch and combines these results through a shared root problem. We integrate FanCyqlone into QPALM to develop FanCyQPALM, a solver for multi-horizon optimal control problems with general linear stage-wise constraints. We compare its performance with state-of-the-art solvers on spring-mass and quadruped control benchmarks.

Closest papers

Nearest neighbours by meaning across the whole index.

FAME-QP: A GPU-Accelerated Quadratic-Programming Solver for Real-Time Model Predictive Control

cs.RO cs.GReess.SY ·2026-11-10 ·Santosh Mohan Rajkumar, Debdipta Goswami, Stephanie Stockar
similarity 0.65
Abstract

We present FAME-QP, a GPU-accelerated solver for dense quadratic programs arising in linear model predictive control. FAME-QP combines constraint-dependent operator representations with fused single- and two-kernel iterations replayed through CUDA graphs, automatically selecting the execution configuration through device calibration and problem-specific timing. It probes a cached operator bank to select the initial penalty and updates operators lazily when problem matrices change. Numerical benchmarks and simulated humanoid and quadrotor control experiments demonstrate reduced latency relative to competing GPU solvers while maintaining solution accuracy and control performance.

0.31

Fast-DeePC: Fast Data-Enabled Predictive Control using Soft-constrained Scheme

eess.SY ·2026-10-09 ·Terry Zhang, Jan Drgona, Malika Sader, Di Liu, Liang Wu
similarity 0.64
Abstract · 8 pages, submission to ACC 2027

Data-enabled predictive control (DeePC) replaces the explicit system model of model predictive control with a data-driven predictor built directly from recorded input-output trajectories, but the original hard-equality formulation keeps its coordinate vector as an online decision variable whose size grows with the offline data length, so the online problem grows more expensive as more data is used to enrich the behavioral representation. This article proposes Fast-DeePC, a framework which relaxes this consistency relation into the control objective with a quadratic ridge on the coordinate vector in place of the customary sparsity-promoting penalty, admitting a closed-form, offline elimination of the coordinate vector and reducing the online problem to a fixed-size box-constrained quadratic program solved by a structure-exploiting interior-point method. On identical soft quadratically regularized problems, the result matches a general-purpose solver's solution and is up to two orders of magnitude faster.

0.24

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.64
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

DAOCP: a dual active set solver for optimal control problems

eess.SY math.OC ·2026-09-27 ·Alberto Zaupa, Samuel Erickson, Mikael Johansson
similarity 0.63
Abstract · Submitted to ICRA 2027

We present DAOCP, a dual active set solver for linear quadratic optimal control problems with stage-wise equality and inequality constraints. Active set methods are leading Model Predictive Control benchmarks for full-body robotics, but existing solvers operate on dense QPs, while typical problem dimensions favor methods that exploit the optimal control structure. DAOCP combines the warm-starting capabilities of active set algorithms with the better computational scaling of structure exploiting solvers, by relying on a generalization of the relationship between the Riccati recursion and the Cholesky factorization of the condensed Hessian. This result enables dual active set iterations to operate directly on the original optimal control problem through recursive computations, without explicitly forming the condensed quadratic program. On robotics benchmarks, DAOCP is the fastest of four solvers in four of five scenarios, cutting average solve time on a 58-state Atlas model by 9$\times$ relative to state of the art solvers DAQP and HPIPM.

0.14

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.63
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

Scaly: an Optimizing Compiler for Optimal Control

eess.SY math.OC ·2026-10-30 ·Tudor A. Oancea, Colin N. Jones
benchmarkcode/data similarity 0.63
Abstract

We present Scaly, an open-source optimizing compiler for optimal control, written in Python, that generates fast C code. Scaly provides a modeling language embedded in Python for the parametric optimization problems that arise in model predictive control and moving horizon estimation, and computes the sparse derivatives that standard optimization solvers need. Scaly accepts general nonlinear programs but applies optimizations specific to optimal control, which preserve the repeated structure of a problem, such as the stages of a horizon, through differentiation down to the generated loops. The generated C depends only on the C math library and never allocates memory dynamically. On three benchmark problems, Scaly evaluates the Hessian of the Lagrangian up to 26 times faster than CasADi, with smaller binaries and build times that stay nearly constant with the horizon. With the same solver, Scaly shortens the solver time per control step on every benchmark, by a factor of up to 9.

0.43

Switch-Time-Aware Hybrid Model Predictive Control Using the Hybrid Minimum Principle

cs.RO eess.SY ·2026-10-16 ·Valentin Gaucher, Wenlong Zhang
similarity 0.60
Abstract · 8 pages; 4 figures, 2 tables

This article presents a time-aware hybrid model predictive control (MPC) framework that simultaneously optimizes the objective with respect to both continuous control inputs and event switching times. Rather than relying on a fixed time grid, the switching instant is lifted into the decision vector and treated as an explicit optimization variable. The resulting transcription is a smooth nonlinear program whose Karush-Kuhn-Tucker (KKT) conditions are consistent with the Hybrid Minimum Principle (HMP) event-time stationarity condition, so first-order hybrid sensitivities are recovered implicitly through the KKT system rather than by evaluating saltation matrices. Each MPC step solves a single sparse Quadratic Program (QP), jointly optimizing control inputs and impact timing in real time. On a bouncing mass landing on an oscillating platform, the method attaches in half the time of fixed-grid saltation MPC, reduces cumulative control effort by 30%, and removes the post-impact rebounds, at a 15% increase in per-cycle solve time. It matches the cumulative effort of offline time-aware solvers to within 4% while running at 2.4 ms per cycle against 281 ms for a complementarity-based formulation of the same problem, of which a 10.6x reduction is attributable to the transcription alone at a fixed solver.

0.34

Iterative State- and Control-Dependent Model Predictive Control: A Jacobian-Free Formulation for Constrained Nonlinear Systems

eess.SY math.OC ·2026-08-15 ·Mohammadreza Kamaldar
theory similarity 0.60
Abstract

This paper presents an iterative model predictive control algorithm that stabilizes constrained nonlinear systems without evaluating a single plant derivative. By factoring the exact nonlinear dynamics into a pseudo-linear form using state- and control-dependent coefficients (SCDCs), we replace the standard nonconvex optimization with a sequence of constrained linear-quadratic programs. Refreezing the coefficient matrices along the previously predicted trajectory drives the iteration. Near the origin, we prove this sequence contracts to a unique fixed point. We explicitly bound the number of iterations required to reach any stopping tolerance, and we quantify the distance from the fixed point to a true Karush-Kuhn-Tucker point, showing this optimality gap vanishes quadratically as the state approaches the origin. Inflating the discrete algebraic Riccati equation generates terminal ingredients that guarantee recursive feasibility and asymptotic stability, even when the solver terminates early. We adapt the terminal penalty online, proving it remains uniformly bounded, and we secure output feedback through the block-observable canonical form, which extracts the exact system state directly from past inputs and outputs. Retaining the block-banded structure of the subproblem forces the computational cost to scale linearly with the horizon length $\ell$. This $O(\ell)$ complexity matches the iterative linear quadratic regulator (iLQR) but sharply undercuts the $O(\ell^3)$ scaling of dense sequential quadratic programming (SQP). Numerical studies on a saturated quadrotor, a nonholonomic integrator, and a nonminimum-phase plant illustrate the theoretical bounds and map how the algorithm compares with iLQR, SQP, and linear-parameter-varying MPC.

0.34