Parallel Dynamic Programming for Conic Linear Quadratic Control
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Parallel Shooting Sequential Quadratic Programming for Nonlinear MPC Problems
In this paper, we propose a parallel shooting algorithm for solving nonlinear model predictive control problems using sequential quadratic programming. This algorithm is built on a two-phase approach where we first test …
Model Predictive ControlGeneralization Bounds for Learning with Linear, Polygonal, Quadratic and Conic Side Knowledge
In this paper, we consider a supervised learning setting where side knowledge is provided about the labels of unlabeled examples. The side knowledge has the effect of reducing the hypothesis space, leading to tighter gen…
Generalization BoundsFlexible Differentiable Optimization via Model Transformations
We introduce DiffOpt.jl, a Julia library to differentiate through the solution of optimization problems with respect to arbitrary parameters present in the objective and/or constraints. The library builds upon MathOptInt…
Hyperparameter OptimizationmodelSupermodularity and valid inequalities for quadratic optimization with indicators
We study the minimization of a rank-one quadratic with indicators and show that the underlying set function obtained by projecting out the continuous variables is supermodular. Although supermodular minimization is, in g…
validAn Approximate, Efficient LP Solver for LP Rounding
Many problems in machine learning can be solved by rounding the solution of an appropriate linear program. We propose a scheme that is based on a quadratic program relaxation which allows us to use parallel stochastic-co…
BIG-bench Machine Learning