Paperlane

no. 15 · Monday 16 November 2026

Costate-Conditioned Dynamic Programming for Parallel-in-Time Solution of Equality-Constrained Optimal Control Problems

Tom Lefebvre

math.OC · v2

Abstract

Gradient based trajectory optimisation algorithms spend most of their per-iteration time on a structured Newton–KKT system. The system corresponds to an equality-constrained linear-quadratic optimal control problem and dedicated Riccati-type solvers exhibit linear complexity in the horizon length. Parallel-in-time algorithms exhibit the potential to reduce the complexity to logarithmic in the horizon by distributing several subtrajectories over multiple cores and then stitch together the results by means of an associative scan. Existing exact formulations condition each subtrajectory on its terminal state. Each subproblem then carries the reachability to that terminal state explicitly as constraint rows. The associated reachability decision however is ill-conditioned for weakly actuated systems. In this work we condition each subtrajectory on the terminal costate instead. The resulting subproblems can now be computed by a free-end Riccati recursion without reachability carrying rows. This approach effectively compensates for the ill-conditioning of weakly actuated systems but requires additional bookkeeping with Lagrangian multipliers when stitching together the various subproblems. Numerically the method reproduces a direct solution of the primal-dual Newton-KKT system to $10^{-12}$ in relative terms, on a weakly controllable chain of masses. The accurracy rivals that of a sequential recursion, whereas terminal-state conditioning loses up to six digits or fails. Operation counts on a problem with 64 subtrajectories and a horizon of 4096 stages gives a speed-up of 26 compared with a sequential solve.

fields
Optimization and Control
pdf ↗ page arXiv:2611.10286 ↗