pith. sign in

arxiv: 2606.24632 · v1 · pith:GYFX4NZYnew · submitted 2026-06-23 · 🧮 math.OC · cs.RO· cs.SY· eess.SY

Parallel Dynamic Programming for Conic Linear Quadratic Control

Pith reviewed 2026-06-25 22:53 UTC · model grok-4.3

classification 🧮 math.OC cs.ROcs.SYeess.SY
keywords parallel dynamic programmingconic linear quadratic controlADMMRiccati recursionmodel predictive controlmulti-core CPUoptimal controltime splitting
0
0 comments X

The pith

A parallel-in-time ADMM method splits conic LQ problems along the time horizon for independent Riccati solves via dynamic programming.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a parallel method for solving linear quadratic control problems that include conic constraints. It reformulates the inner ADMM update as an LQ problem and divides the problem into separate subproblems over segments of the time horizon. Each subproblem is then solved with a modified Riccati recursion obtained through dynamic programming. The split preserves the convergence behavior of the original ADMM iteration. Benchmarks on two real-world applications report speedups of as much as five times on multi-core CPU hardware.

Core claim

We present a parallel-in-time approach that solves computationally demanding conic optimal control problems through the use of the alternating direction method of multipliers (ADMM). In particular, we formulate the inner primal update of ADMM as an LQ problem and split the reformulated problem along the time horizon. This enables us to derive a variant of the Riccati recursion using dynamic programming to solve each subproblem in parallel.

What carries the argument

The time-horizon split of the ADMM primal LQ update, solved via a parallel Riccati recursion variant derived from dynamic programming.

If this is right

  • Conic model predictive control problems become solvable in real time on standard multi-core CPUs.
  • The method applies directly to linear control problems that include conic constraints.
  • The parallel solves maintain the optimality and convergence guarantees of the serial ADMM procedure.
  • Divide-and-conquer strategies can be applied to other ADMM-based solvers for optimal control.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same splitting idea may apply to related time-structured optimization problems outside of control.
  • Further gains could appear if the Riccati variant is adapted for GPU hardware.
  • The approach suggests a template for parallelizing other iterative solvers that rely on sequential Riccati steps.
  • Embedded systems using MPC may achieve lower latency without changes to the problem formulation.

Load-bearing premise

Splitting the reformulated LQ problem along the time horizon and solving the resulting subproblems independently with the derived Riccati variant preserves the convergence and optimality properties of the original ADMM iteration for conic problems.

What would settle it

A benchmark instance in which the parallel algorithm produces a solution that differs from the serial ADMM solution or fails to converge to the same optimal value.

Figures

Figures reproduced from arXiv: 2606.24632 by Brian Plancher, Gabriel Bravo-Palacios, Luyao Zhang, Sergio Grammatico.

Figure 1
Figure 1. Figure 1: Parallel-in-time illustration for an LQ problem [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Benchmarking results across various horizon lengths. Above-bar numbers indicate the speedups achieved by our [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Solve times for the backward pass on the quadro [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
read the original abstract

Linear Quadratic (LQ) control problems are at the heart of linear control theory and Model Predictive Control (MPC). While performant, standard approaches to solving such problems are inherently serial, limiting real-time scalability despite the parallel computing power available on modern multi-core CPUs. Contributing to addressing this challenge and motivated by ``divide and conquer'' strategies, we present a parallel-in-time approach that solves computationally demanding conic optimal control problems through the use of the alternating direction method of multipliers (ADMM). In particular, we formulate the inner primal update of ADMM as an LQ problem and split the reformulated problem along the time horizon. This enables us to derive a variant of the Riccati recursion using dynamic programming to solve each subproblem in parallel. Numerical benchmarks on two real-world applications demonstrate as much as a 5x speedup compared to existing related approaches on multi-core CPU hardware.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proposes a parallel-in-time algorithm for conic linear-quadratic control problems that reformulates the ADMM primal update as an LQ problem, splits the horizon into independent subproblems, and solves them via a derived variant of the Riccati recursion obtained through dynamic programming; numerical results on two real-world applications report up to 5x speedup versus existing serial or related parallel methods on multi-core CPUs.

Significance. If the parallel splitting exactly reproduces the serial ADMM fixed-point and convergence properties, the method would offer a practical route to real-time scalable conic MPC on commodity parallel hardware, extending divide-and-conquer ideas to the conic setting where standard Riccati solvers remain serial.

major comments (2)
  1. [Derivation of the parallel Riccati recursion (main technical section)] The central construction (reformulation of the ADMM primal step as a time-split conic LQ problem followed by independent Riccati solves) must be shown to produce a concatenated solution that satisfies the original coupled KKT system, including any dual coupling or conic constraints that cross segment boundaries. The abstract states that a “variant of the Riccati recursion” is derived but supplies no indication of the boundary conditions or dual updates required for exact equivalence; this equivalence is load-bearing for the claim that the parallel algorithm inherits the convergence guarantees of standard ADMM.
  2. [Numerical benchmarks] The numerical benchmarks section reports “as much as a 5x speedup” but does not state whether the parallel iterates achieve the same primal/dual residuals or objective values as the serial ADMM reference at termination, nor the precise baseline implementations and core counts used; without these, it is impossible to determine whether the observed wall-clock improvement occurs at equivalent solution quality.
minor comments (2)
  1. [Abstract] The abstract introduces the method and the 5x claim but contains no equation or proof sketch; a one-sentence pointer to the key technical result (e.g., “the parallel Riccati recursion is shown in §4.2 to be algebraically equivalent to the serial ADMM update”) would improve readability.
  2. [Problem formulation and splitting] Notation for the time-segment boundaries and the handling of the conic constraint multipliers across segments should be introduced explicitly when the splitting is first defined.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback. We address each major comment below and will incorporate clarifications and additional details in a revised manuscript.

read point-by-point responses
  1. Referee: [Derivation of the parallel Riccati recursion (main technical section)] The central construction (reformulation of the ADMM primal update as a time-split conic LQ problem followed by independent Riccati solves) must be shown to produce a concatenated solution that satisfies the original coupled KKT system, including any dual coupling or conic constraints that cross segment boundaries. The abstract states that a “variant of the Riccati recursion” is derived but supplies no indication of the boundary conditions or dual updates required for exact equivalence; this equivalence is load-bearing for the claim that the parallel algorithm inherits the convergence guarantees of standard ADMM.

    Authors: The derivation in Section 3 formulates each time-split subproblem such that the dual variables from the ADMM iteration serve as the boundary conditions at segment interfaces. This ensures that the concatenated primal solution, when combined with the subsequent dual update, satisfies the original coupled KKT system by construction, including any crossing conic constraints (which are handled locally within each subproblem but coupled via the shared duals). We agree that an explicit statement of these boundary conditions and a short equivalence argument would strengthen the presentation; we will add this to the revised manuscript. revision: yes

  2. Referee: [Numerical benchmarks] The numerical benchmarks section reports “as much as a 5x speedup” but does not state whether the parallel iterates achieve the same primal/dual residuals or objective values as the serial ADMM reference at termination, nor the precise baseline implementations and core counts used; without these, it is impossible to determine whether the observed wall-clock improvement occurs at equivalent solution quality.

    Authors: We will revise the numerical section to include explicit confirmation that the parallel and serial ADMM runs terminate at equivalent primal/dual residuals (within solver tolerance) and objective values. We will also specify the baseline (standard serial Riccati-based ADMM) and report the exact core counts (4–8 cores on the tested multi-core CPU) used for each timing result. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation from standard ADMM and DP is independent

full rationale

The paper derives a parallel-in-time solver by reformulating the ADMM primal step as a conic LQ problem, splitting along the time horizon, and obtaining a Riccati variant via dynamic programming. No equations reduce to fitted inputs by construction, no self-citation chains bear the central claim, and no uniqueness theorems or ansatzes are smuggled in. The reported speedups are empirical benchmarks on real-world applications, not derived quantities. This matches the default expectation that most papers are non-circular; the central construction retains independent content from standard ADMM and Riccati theory.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract supplies no explicit free parameters, axioms, or invented entities; the method is described at the level of standard ADMM and Riccati recursion.

pith-pipeline@v0.9.1-grok · 5691 in / 1010 out tokens · 14826 ms · 2026-06-25T22:53:54.169020+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

66 extracted references · 14 canonical work pages

  1. [1]

    and Posa, Michael and Hu, Yue and Escande, Adrien and Mansard, Nicolas and Prete, Andrea Del , journal=

    Wensing, Patrick M. and Posa, Michael and Hu, Yue and Escande, Adrien and Mansard, Nicolas and Prete, Andrea Del , journal=. Optimization-Based Control for Dynamic Legged Robots , year=

  2. [2]

    2010 , publisher=

    Practical methods for optimal control and estimation using nonlinear programming , author=. 2010 , publisher=

  3. [3]

    Journal of Parallel and Distributed Computing , volume=

    GPU acceleration of ADMM for large-scale quadratic programming , author=. Journal of Parallel and Distributed Computing , volume=. 2020 , publisher=

  4. [4]

    Parallel Computing , volume=

    Divide and conquer: A parallel algorithm for the solution of a tridiagonal linear system of equations , author=. Parallel Computing , volume=. 1991 , publisher=

  5. [5]

    2024 IEEE International Conference on Robotics and Automation (ICRA) , pages=

    Symmetric stair preconditioning of linear systems for parallel trajectory optimization , author=. 2024 IEEE International Conference on Robotics and Automation (ICRA) , pages=. 2024 , organization=

  6. [6]

    Elsevier , year=

    Differential dynamic programming , author=. Elsevier , year=

  7. [7]

    International Journal of Control , volume=

    A second-order gradient method for determining optimal trajectories of non-linear discrete-time systems , author=. International Journal of Control , volume=. 1966 , publisher=

  8. [8]

    2024 IEEE International Conference on Robotics and Automation (ICRA) , pages=

    Tinympc: Model-predictive control on resource-constrained microcontrollers , author=. 2024 IEEE International Conference on Robotics and Automation (ICRA) , pages=. 2024 , organization=

  9. [9]

    arXiv preprint arXiv:2403.18149 , year=

    Code generation for conic model-predictive control on microcontrollers with tinympc , author=. arXiv preprint arXiv:2403.18149 , year=

  10. [10]

    IEEE International Conference on Robotics and Automation (ICRA) , address =

    MPCGPU: Real-Time Nonlinear Model Predictive Control through Preconditioned Conjugate Gradient on the GPU , author=. IEEE International Conference on Robotics and Automation (ICRA) , address =

  11. [11]

    Autonomous Driving Motion Planning With Constrained Iterative LQR , year=

    Chen, Jianyu and Zhan, Wei and Tomizuka, Masayoshi , journal=. Autonomous Driving Motion Planning With Constrained Iterative LQR , year=

  12. [12]

    Model Predictive Control for Micro Aerial Vehicles: A Survey , year=

    Nguyen, Huan and Kamel, Mina and Alexis, Kostas and Siegwart, Roland , booktitle=. Model Predictive Control for Micro Aerial Vehicles: A Survey , year=

  13. [13]

    Prefix sums and their applications , author=

  14. [14]

    IEEE Transactions on Automatic Control , title=

    S. IEEE Transactions on Automatic Control , title=. 2023 , volume=

  15. [15]

    An efficient implementation of partial condensing for Nonlinear Model Predictive Control , year=

    Frison, Gianluca and Kouzoupis, Dimitris and Jørgensen, John Bagterp and Diehl, Moritz , booktitle=. An efficient implementation of partial condensing for Nonlinear Model Predictive Control , year=

  16. [16]

    2017 , note =

    A high-performance Riccati based solver for tree-structured quadratic programs , journal =. 2017 , note =. doi:https://doi.org/10.1016/j.ifacol.2017.08.2027 , author =

  17. [17]

    , journal=

    Chen, Yuxiao and Rosolia, Ugo and Ubellacker, Wyatt and Csomay-Shanklin, Noel and Ames, Aaron D. , journal=. Interactive Multi-Modal Motion Planning With Branch Model Predictive Control , year=

  18. [18]

    and Brown, Matthew and Gerdes, J

    Alsterda, John P. and Brown, Matthew and Gerdes, J. Christian , booktitle=. Contingency Model Predictive Control for Automated Vehicles , year=

  19. [19]

    Contingency Planning Over Probabilistic Obstacle Predictions for Autonomous Road Vehicles , year=

    Hardy, Jason and Campbell, Mark , journal=. Contingency Planning Over Probabilistic Obstacle Predictions for Autonomous Road Vehicles , year=

  20. [20]

    A Robust Scenario MPC Approach for Uncertain Multi-Modal Obstacles , year=

    Batkovic, Ivo and Rosolia, Ugo and Zanon, Mario and Falcone, Paolo , journal=. A Robust Scenario MPC Approach for Uncertain Multi-Modal Obstacles , year=

  21. [21]

    International Journal of Robust and Nonlinear Control , author =

    A dual. International Journal of Robust and Nonlinear Control , author =. 2019 , pages =. doi:10.1002/rnc.4503 , language =

  22. [22]

    Sinha, Rohan and Elhafsi, Amine and Agia, Christopher and Foutter, Matthew and Schmerling, Edward and Pavone, Marco , month = jul, year =. Real-

  23. [23]

    SIAM Journal on Optimization , author =

    Partitioned. SIAM Journal on Optimization , author =. 1991 , note =. doi:10.1137/0801037 , number =

  24. [24]

    A parallel structure exploiting factorization algorithm with applications to

    Nielsen, Isak and Axehill, Daniel , month = dec, year =. A parallel structure exploiting factorization algorithm with applications to. 2015 54th. doi:10.1109/CDC.2015.7402830 , language =

  25. [25]

    Parallel and

    Jallet, Wilson and Dantec, Ewen and Arlaud, Etienne and Carpentier, Justin and Mansard, Nicolas , month = may, year =. Parallel and

  26. [26]

    and Erb, Sven O

    Betts, John T. and Erb, Sven O. , title =. SIAM Journal on Applied Dynamical Systems , volume =. 2003 , doi =

  27. [27]

    TDR-OBCA: A Reliable Planner for Autonomous Driving in Free-Space Environment , year=

    He, Runxin and Zhou, Jinyun and Jiang, Shu and Wang, Yu and Tao, Jiaming and Song, Shiyu and Hu, Jiangtao and Miao, Jinghao and Luo, Qi , booktitle=. TDR-OBCA: A Reliable Planner for Autonomous Driving in Free-Space Environment , year=

  28. [28]

    and Shamma, Jeff S

    Laine, Forrest and Tomlin, Claire , month = dec, year =. Parallelizing. 2019. doi:10.1109/CDC40024.2019.9029974 , language =

  29. [29]

    Improving scenario decomposition algorithms for robust nonlinear model predictive control , volume =

    Martí, Rubén and Lucia, Sergio and Sarabia, Daniel and Paulen, Radoslav and Engell, Sebastian and de Prada, César , month = aug, year =. Improving scenario decomposition algorithms for robust nonlinear model predictive control , volume =. doi:10.1016/j.compchemeng.2015.04.024 , journal =

  30. [30]

    Optimal Control Applications and Methods , author =

    Massively parallelizable proximal algorithms for large-scale stochastic optimal control problems , volume =. Optimal Control Applications and Methods , author =. 2024 , note =. doi:10.1002/oca.3054 , language =

  31. [31]

    Plancher, Brian and Kuindersma, Scott , year =. A. Algorithmic. doi:10.1007/978-3-030-44051-0_38 , note =

  32. [32]

    Real-time motion planning of legged robots: A model predictive control approach , year=

    Farshidian, Farbod and Jelavic, Edo and Satapathy, Asutosh and Giftthaler, Markus and Buchli, Jonas , booktitle=. Real-time motion planning of legged robots: A model predictive control approach , year=

  33. [33]

    A parallel Newton-type method for nonlinear model predictive control , journal =

    Haoyang Deng and Toshiyuki Ohtsuka , keywords =. A parallel Newton-type method for nonlinear model predictive control , journal =. 2019 , issn =. doi:https://doi.org/10.1016/j.automatica.2019.108560 , url =

  34. [34]

    Synthesis and stabilization of complex behaviors through online trajectory optimization , year=

    Tassa, Yuval and Erez, Tom and Todorov, Emanuel , booktitle=. Synthesis and stabilization of complex behaviors through online trajectory optimization , year=

  35. [35]

    and Jackson, Brian E

    Howell, Taylor A. and Jackson, Brian E. and Manchester, Zachary , booktitle=. ALTRO: A Fast Solver for Constrained Trajectory Optimization , year=

  36. [36]

    , booktitle=

    Li, He and Yu, Wenhao and Zhang, Tingnan and Wensing, Patrick M. , booktitle=. A Unified Perspective on Multiple Shooting In Differential Dynamic Programming , year=

  37. [37]

    , series =

    Nocedal, Jorge and Wright, Stephen J. , series =. Numerical. 2006 , doi =

  38. [38]

    , year =

    Fast. Neural Computation , author =. 2002 , pages =. doi:10.1162/08997660260028683 , number =

  39. [39]

    Perceptive Locomotion Through Nonlinear Model-Predictive Control , year=

    Grandia, Ruben and Jenelten, Fabian and Yang, Shaohui and Farshidian, Farbod and Hutter, Marco , journal=. Perceptive Locomotion Through Nonlinear Model-Predictive Control , year=

  40. [40]

    A Family of Iterative Gauss-Newton Shooting Methods for Nonlinear Optimal Control , year=

    Giftthaler, Markus and Neunert, Michael and Stäuble, Markus and Buchli, Jonas and Diehl, Moritz , booktitle=. A Family of Iterative Gauss-Newton Shooting Methods for Nonlinear Optimal Control , year=

  41. [41]

    , journal=

    Wang, Allen and Jasour, Ashkan and Williams, Brian C. , journal=. Non-Gaussian Chance-Constrained Trajectory Planning for Autonomous Vehicles Under Agent Uncertainty , year=

  42. [42]

    and Kamgarpour, Maryam , journal=

    Ahn, Heejin and Chen, Colin and Mitchell, Ian M. and Kamgarpour, Maryam , journal=. Safe Motion Planning Against Multimodal Distributions Based on a Scenario Approach , year=

  43. [43]

    Automated

    Zhang, Luyao and Han, Shaohang and Grammatico, Sergio , journal =. Automated

  44. [44]

    James Bradbury and Roy Frostig and Peter Hawkins and Matthew James Johnson and Chris Leary and Dougal Maclaurin and George Necula and Adam Paszke and Jake Vander

  45. [45]

    and Zhang, John Z

    Bishop, Arun L. and Zhang, John Z. and Gurumurthy, Swaminathan and Tracy, Kevin and Manchester, Zachary , booktitle=. ReLU-QP: A GPU-Accelerated Quadratic Programming Solver for Model-Predictive Control , year=

  46. [46]

    and Anitescu, Mihai , booktitle=

    Cole, David and Shin, Sungho and Pacaud, François and Zavala, Victor M. and Anitescu, Mihai , booktitle=. Exploiting GPU/SIMD Architectures for Solving Linear-Quadratic MPC Problems* , year=

  47. [47]

    2017 , url=

    Predictive Control for Linear and Hybrid Systems , author=. 2017 , url=

  48. [48]

    Journal of Optimization Theory and Applications 99(3): 723--757

    Application of. Journal of Optimization Theory and Applications , author =. 1998 , pages =. doi:10.1023/A:1021711402723 , language =

  49. [49]

    FATROP: A Fast Constrained Optimal Control Problem Solver for Robot Trajectory Optimization and Control , year=

    Vanroye, Lander and Sathya, Ajay and De Schutter, Joris and Decré, Wilm , booktitle=. FATROP: A Fast Constrained Optimal Control Problem Solver for Robot Trajectory Optimization and Control , year=

  50. [50]

    Journal of Optimization Theory and Applications , author =

    Efficient dynamic programming implementations of. Journal of Optimization Theory and Applications , author =. 1989 , pages =. doi:10.1007/BF00940728 , language =

  51. [51]

    Efficient implementation of the Riccati recursion for solving linear-quadratic control problems , year=

    Frison, Gianluca and Jørgensen, John Bagterp , booktitle=. Efficient implementation of the Riccati recursion for solving linear-quadratic control problems , year=

  52. [52]

    Structure-Exploiting Sequential Quadratic Programming for Model-Predictive Control , year=

    Jordana, Armand and Kleff, Sébastien and Meduri, Avadesh and Carpentier, Justin and Mansard, Nicolas and Righetti, Ludovic , journal=. Structure-Exploiting Sequential Quadratic Programming for Model-Predictive Control , year=

  53. [53]

    , journal=

    Na, Sen and Shin, Sungho and Anitescu, Mihai and Zavala, Victor M. , journal=. On the Convergence of Overlapping Schwarz Decomposition for Nonlinear Optimal Control , year=

  54. [54]

    A hierarchical time-splitting approach for solving finite-time optimal control problems , year=

    Stathopoulos, Georgios and Keviczky, Tamás and Wang, Yang , booktitle=. A hierarchical time-splitting approach for solving finite-time optimal control problems , year=

  55. [55]

    Convex Optimization , publisher=

    Boyd, Stephen and Vandenberghe, Lieven , year=. Convex Optimization , publisher=

  56. [56]

    and Banjac, G

    Stellato, B. and Banjac, G. and Goulart, P. and Bemporad, A. and Boyd, S. , title =. Mathematical Programming Computation , year =

  57. [57]

    2021 , keywords =

    Journal of Optimization Theory and Applications , author =. 2021 , keywords =. doi:10.1007/s10957-021-01896-x , language =

  58. [58]

    Mathematical Programming Computation , Year =

    acados -- a modular open-source framework for fast embedded optimal control , Author =. Mathematical Programming Computation , Year =

  59. [59]

    31st AIAA/AAS Space Flight Mechanics Meeting , year =

    Kevin Tracy and Zachary Manchester , title =. 31st AIAA/AAS Space Flight Mechanics Meeting , year =

  60. [60]

    2016 , issue_date =

    Conic. Journal of Optimization Theory and Applications , author =. 2016 , pages =. doi:10.1007/s10957-016-0892-3 , language =

  61. [61]

    2024 , eprint=

    Clarabel: An interior-point solver for conic programs with quadratic objectives , author=. 2024 , eprint=

  62. [62]

    and Zeilinger, Melanie N

    Domahidi, Alexander and Zgraggen, Aldo U. and Zeilinger, Melanie N. and Morari, Manfred and Jones, Colin N. , booktitle=. Efficient interior point methods for multistage problems arising in receding horizon control , year=

  63. [63]

    QPALM-OCP: A Newton-Type Proximal Augmented Lagrangian Solver Tailored for Quadratic Programs Arising in Model Predictive Control , year=

    Løwenstein, Kristoffer Fink and Bernardini, Daniele and Patrinos, Panagiotis , journal=. QPALM-OCP: A Newton-Type Proximal Augmented Lagrangian Solver Tailored for Quadratic Programs Arising in Model Predictive Control , year=

  64. [64]

    Foundations and Trends

    Distributed optimization and statistical learning via the alternating direction method of multipliers , author=. Foundations and Trends. 2011 , publisher=

  65. [65]

    Accelerated ADMM based Trajectory Optimization for Legged Locomotion with Coupled Rigid Body Dynamics , year=

    Zhou, Ziyi and Zhao, Ye , booktitle=. Accelerated ADMM based Trajectory Optimization for Legged Locomotion with Coupled Rigid Body Dynamics , year=

  66. [66]

    Mathematical programming , volume=

    On the Douglas—Rachford splitting method and the proximal point algorithm for maximal monotone operators , author=. Mathematical programming , volume=. 1992 , publisher=