Parallel Dynamic Programming for Conic Linear Quadratic Control

• URL: http://arxiv.org/abs/2606.24632v1
• Date: Tue, 23 Jun 2026 14:26:38 GMT
• Title: Parallel Dynamic Programming for Conic Linear Quadratic Control
• Abstract summary: Linear Quadratic (LQ) control problems are at the heart of linear control theory and Model Predictive Control (MPC)<n>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)<n> Numerical benchmarks on two real-world applications demonstrate as much as a 5x speedup compared to existing related approaches on multi-core CPU hardware.
• Score: 11.017626990661059
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• IsoCompute Playbook: Optimally Scaling Sampling Compute for LLM RL [75.28528082188787]
  We study the compute-optimal allocation of sampling compute for on-policy reinforcement learning methods in large language models (LLMs)<n>We find that the compute-optimal number of parallel rollouts per problem increases predictably with compute budget and then saturates.<n>Our results recast RL scaling laws as prescriptive allocation rules and provide practical guidance for compute-efficient LLM RL post-training.
  arXiv  Detail & Related papers  (2026-03-12T16:49:21Z)
• Parallel-in-Time Nonlinear Optimal Control via GPU-native Sequential Convex Programming [2.8852807790754618]
  We introduce a fully GPU-native trajectory optimization framework that combines sequential convex programming with a consensus-based alternating direction method of multipliers.<n>We validate the solver on a quadrotor agile flight task and a Mars powered descent problem using an on-board edge computing platform.<n> Benchmarks reveal a sustained 4x throughput speedup and a 51% reduction in energy consumption over a heavily optimized 12-core CPU baseline.
  arXiv  Detail & Related papers  (2026-03-11T12:39:14Z)
• Para-B&B: Load-Balanced Deterministic Parallelization of Solving MIP [50.917107318582715]
  Mixed-integer programming (MIP) extends linear programming by incorporating both continuous and integer decision variables.<n>This paper presents the first fully open-source implementation of deterministic parallel branch-and-bound for HiGHS, a high-performance MIP solver.<n>Our approach introduces a novel data-parallel architecture ensuring strict determinism by replicating complete solver state across worker threads.
  arXiv  Detail & Related papers  (2026-02-10T14:17:53Z)
• Inference-Aware Meta-Alignment of LLMs via Non-Linear GRPO [55.574265038358455]
  Inference-aware meta-alignment (IAMA) is a novel approach to align large language models to diverse human preferences.<n>IAMA trains a base model such that it can be effectively aligned to multiple tasks via different inference-time alignment algorithms.<n>We propose non-linear GRPO, which provably converges to the optimal solution in the space of probability measures.
  arXiv  Detail & Related papers  (2026-02-02T03:50:42Z)
• Batched First-Order Methods for Parallel LP Solving in MIP [5.672808839120628]
  We extend the primal-dual hybrid algorithm to efficiently solve batches of related linear programming problems that arise in mixed-integer programming techniques such as strong branching and bound tightening.<n>We demonstrate the effectiveness of our approach on various case studies and identify the problem sizes where first-order methods outperform traditional simplex-based solvers depending on the computational environment one can use.
  arXiv  Detail & Related papers  (2026-01-29T17:02:46Z)
• Online Inference of Constrained Optimization: Primal-Dual Optimality and Sequential Quadratic Programming [55.848340925419286]
  We study online statistical inference for the solutions of quadratic optimization problems with equality and inequality constraints.<n>We develop a sequential programming (SSQP) method to solve these problems, where the step direction is computed by sequentially performing an approximation of the objective and a linear approximation of the constraints.<n>We show that our method global almost moving-average convergence and exhibits local normality with an optimal primal-dual limiting matrix in the sense of Hjek and Le Cam.
  arXiv  Detail & Related papers  (2025-11-27T06:16:17Z)
• Machine Learning-assisted High-speed Combinatorial Optimization with Ising Machines for Dynamically Changing Problems [0.0]
  We show a method using embedded Ising machines to solve diverse problems at high speed without parameter tuning.<n>In TDMA scheduling for wireless multi-hop networks, our demonstration has shown that the sophisticated system can adapt to changes in the problem and showed that it has a speed advantage over conventional methods.
  arXiv  Detail & Related papers  (2025-03-31T11:31:36Z)
• Parallel splitting method for large-scale quadratic programs [1.4519462317941787]
  SPLIT is a framework for decomposing large-scale quadratic programs into smaller subproblems, which are then solved in parallel.<n>We show that SPLIT is capable of providing drastic reductions in computational time, while delivering high-quality solutions.
  arXiv  Detail & Related papers  (2025-03-21T09:45:47Z)
• Beyond Quantum Annealing: Optimal control solutions to MaxCut problems [0.7864304771129751]
  Quantum Annealing (QA) relies on mixing two Hamiltonian terms, a simple driver and a complex problem Hamiltonian, in a linear combination. We present different techniques for improving on the linear-schedule along two directions, conceptually distinct but leading to similar outcomes.
  arXiv  Detail & Related papers  (2024-05-14T14:08:55Z)
• Scaling Distributed Deep Learning Workloads beyond the Memory Capacity with KARMA [58.040931661693925]
  We propose a strategy that combines redundant recomputing and out-of-core methods. We achieve an average of 1.52x speedup in six different models over the state-of-the-art out-of-core methods. Our data parallel out-of-core solution can outperform complex hybrid model parallelism in training large models, e.g. Megatron-LM and Turning-NLG.
  arXiv  Detail & Related papers  (2020-08-26T07:24:34Z)
• Accelerating Feedforward Computation via Parallel Nonlinear Equation Solving [106.63673243937492]
  Feedforward computation, such as evaluating a neural network or sampling from an autoregressive model, is ubiquitous in machine learning. We frame the task of feedforward computation as solving a system of nonlinear equations. We then propose to find the solution using a Jacobi or Gauss-Seidel fixed-point method, as well as hybrid methods of both. Our method is guaranteed to give exactly the same values as the original feedforward computation with a reduced (or equal) number of parallelizable iterations, and hence reduced time given sufficient parallel computing power.
  arXiv  Detail & Related papers  (2020-02-10T10:11:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.