CS Paper Radar

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

Luke Bhan, Michael W. Mahoney, Sen Na

eess.SY math.OC ·submitted 2026-09-27 04:45 UTC · v1
theory

Abstract

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.

Comment
31 pages

Closest papers

Nearest neighbours by meaning across the whole index.

FanCyqlone: A Parallelized Solver for Multi-Horizon Optimal Control

eess.SY math.OC ·2026-11-12 ·Matisse Teuwen, Pieter Pas, Mathijs Schuurmans, Panagiotis Patrinos
similarity 0.64
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.

0.24

Parallel Policy-Gradient Methods for Parameter Optimization of Nonlinear Feedback Controllers

eess.SY math.OC ·2026-09-12 ·An Nguyen, Leilei Cui
similarity 0.63
Abstract

Structured feedback controllers provide rigorous stability guarantees, but often require manual parameter tuning to achieve good closed-loop performance. Policy-gradient methods offer a systematic approach to parameter optimization; however, conventional gradient evaluation requires sequential forward state rollout and backward costate propagation. This letter develops a time-parallel policy-gradient framework for discrete-time nonlinear control-affine systems. We derive the policy-gradient expression where the state and costate rollouts required for policy-gradient evaluation are formulated as residual-minimization problems and solved using Gauss-Newton (GN) iterations with parallel associative scans. For closed-loop systems that are globally asymptotically stable and locally exponentially stable, we show that the residual-minimization problems satisfy a local Polyak-Lojasiewicz (PL) inequality and that the GN iterates converge locally at a quadratic rate. Moreover, the PL constant, the size of the convergence neighborhood, and the quadratic convergence bound are independent of the rollout horizon T. We also prove that, for any finite horizon T, the state solver recovers the exact trajectory from any initialization in at most T iterations. Finally, an inertia-wheel pendulum example with interconnection and damping assignment passivity-based control (IDA-PBC) demonstrates improved closed-loop performance and the computational benefits of the proposed parallel policy-gradient framework.

0.19

Moving Horizon Estimation for Quadrotors: An $\mathcal{L}_1$ Adaptive Optimizer Approach

cs.RO eess.SY ·2026-09-25 ·Thinh Nguyen, Minkyung Kim, Sandeep Banik, Jinrae Kim, Naira Hovakimyan
published similarity 0.62
Abstract

Moving Horizon Estimation (MHE) is a state estimation method based on finite-horizon optimization that can offer higher accuracy at the cost of increased computation compared to Kalman filter-based approaches. We present a linear smoothing MHE formulation as a dense Quadratic Program (QP), and a solver consisting of a continuous-time Newton's method augmented with the $\mathcal{L}_1$ Adaptive Optimizer ($\mathcal{L}_1$-AO). While MHE is inherently time-varying, conventional approaches treat it as a sequence of independent, time-invariant problems and employ iterative solvers at each time step, which can be both inaccurate and computationally burdensome. In contrast, time-varying solvers track the optimal solution with fewer iterations by exploiting the temporal evolution of the problem, thereby reducing the computational load. In this research, we enhance both the performance and efficiency of MHE through a time-varying solver with an $\mathcal{L}_1$-AO augmentation that compensates for the prediction inaccuracy, which is common in practice due to noisy sensors and the lack of prior knowledge of the system. Simulation results on a quadrotor platform show that the $\mathcal{L}_1$-AO-augmented approach solves the MHE optimization problem more efficiently than the baseline time-invariant solver and achieves higher estimation accuracy under challenging conditions, compared with both the Extended Kalman Filter and the standard MHE.

0.28

Square Root Gauss-Newton iLQR

cs.RO math.OC ·2026-09-17 ·Maximilian Haas-Heger, Jur van den Berg
similarity 0.59
Abstract · 16 pages, 2 figures, ISRR 2026

The iterative Linear Quadratic Regulator (iLQR) is a widely used algorithm for nonlinear trajectory optimization. At each iteration, it solves a local linear-quadratic approximation of the problem via dynamic programming, propagating a quadratic cost-to-go function. If the Hessian of the cost-to-go approximation is positive-semidefinite, one can derive a square root formulation of iLQR that propagates its Cholesky factor instead. This offers significant numerical advantages - much as square root Kalman filters improve upon their conventional counterparts - particularly when iLQR is used within an augmented Lagrangian framework for handling constraints, where large penalties degrade conditioning. Previous square root formulations of iLQR and related algorithms exist, but they are either numerically suboptimal, algorithmically complex, or both. In this paper, we show that the key to an effective square root formulation lies in the Gauss-Newton (weighted least-squares) structure of the cost function: this yields a positive semidefiniteness property that extends beyond the Hessian to the full augmented cost-to-go matrix, and enables a backward pass of remarkable simplicity in which each step reduces to a single QR-decomposition, from which the feedback gain and propagated Cholesky factor are extracted directly.

0.23

Primal Acceleration of Newton's Method

cs.AI math.OCcs.LG ·2026-08-21 ·Nikita Doikov
similarity 0.59
Abstract

We develop a new direct accelerated Newton method for minimizing convex functions with Lipschitz continuous Hessian. The algorithm uses only primal variables and performs just one linear solve per iteration. With a simple predetermined choice of parameters, it achieves the global convergence rate of $O(1/k^3)$ in terms of the functional residual. To the best of our knowledge, this is the first second-order method for this problem class attaining this rate while relying solely on one linear system solve per iteration (without solving auxiliary nonlinear regularized subproblems, such as cubic regularization, performing nonlinear parameter searches, or using dual extragradient corrections). Our method can be implemented in a Hessian-free way, using an inexact linear system solver, while preserving the fast global rate. We further extend our construction to arbitrary geometry through Bregman divergence, and to composite optimization problems.

0.11

Characterizing Identifiability and Generalization for Inverse Receding-Horizon Linear-Quadratic Regulator Problems

eess.SY math.OC ·2026-09-12 ·Zhiyuan Jin, Jingqi Li, David Fridovich-Keil
theoryhot direction similarity 0.57
Abstract · 6 pages, 1 figure. Submitted to IEEE Control Systems Letters (L-CSS) with the ACC presentation option

We consider the problem of objective inference in the context of receding-horizon linear-quadratic regulator (LQR). In this setting, we are given sequential state-action observations, where each observed action is the first control of a newly solved finite-horizon LQR problem. We characterize when the objective of that problem is uniquely identifiable from these observations and when additional observations provide no new information about the objective. We then analyze action prediction at unseen states and show that all objectives reproducing the observed actions yield identical actions throughout the affine hull of the observed states; outside this hull, we derive an upper bound on the prediction error. % and deriving a prediction-error bound outside this hull. Additionally, we show that, when only the linear objective terms are unknown, exact prediction holds at every state. Finally, numerical results show that, even under stochastic observation noise, re-optimizing an inferred objective enables accurate action prediction at unseen states across different planning horizons.

0.30

A Scalable Learned Iterative Solver for Nonlinear MPC via Temporal Decomposition

cs.LG math.OCeess.SY ·2026-10-09 ·Lukas Lüken, Sergio Lucia
benchmark similarity 0.57
Abstract · 16 pages, 7 figures, 7 tables

Nonlinear model predictive control (NMPC) can be applied to large nonlinear systems with complex objectives while enforcing constraints, but the cost of solving the underlying optimization problems limits real-time application for systems with fast dynamics or many states. Neural networks can reduce this online cost by approximating the control law, but may violate constraints and typically require many precomputed optimizer solutions for training. The learning-based iterative solver for constrained optimization (LISCO) instead learns to predict primal-dual steps toward satisfaction of the Karush-Kuhn-Tucker (KKT) conditions through self-supervised training without precomputed solutions, but its dense, monolithic architecture grows with the prediction horizon. We remove this horizon dependence by exploiting the temporal structure of the problem in the solver architecture, which makes the network size independent of the horizon while leaving the training loss and the solver iteration unchanged. A closed-loop resampling strategy further aligns the training distribution with closed-loop operation at no additional sampling cost. On an economic NMPC benchmark of a CSTR cascade, the proposed solver scales to larger problems than monolithic LISCO and achieves median speedups of up to a factor of four over IPOPT. In closed loop, it achieves comparable control performance to IPOPT with no observed constraint violations.

0.32

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.56
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.36