精读笔记
Problem Setting
这篇论文实际处理的是 conic optimal control / MPC 中反复出现的 LQ 子问题求解，而不是重新提出一种完整 MPC 框架。难点在于 LQ 的 KKT / Riccati 结构虽然高度可利用，但天然沿时间串行；当 horizon 很长或每阶段约束很多时，单核/少核 Riccati 成为实时 bottleneck。以前方法卡在两个地方：一类方法高效但串行，另一类 parallel-in-time 方法能切时间但对 conic constraints 支持不足或 consensus/factorization 代价高。关键矛盾是：想要并行就必须切断时间依赖，但 optimal control 的信息传播恰恰沿时间发生；论文的目标是在不破坏 LQ 精确结构的前提下，把时间依赖压缩到边界变量上。
Motivation
已有 conic solvers 如 operator splitting / sparse LDLᵀ 能处理约束，但没有充分利用 LQ temporal structure；传统 Riccati 利用结构但难以并行。Wright 系列 PDP/PRI 和后续 temporal parallelization 说明时间切分是可行的，但很多工作不处理 constraints，或者在 constrained LQ 上付出较高 factorization 代价。作者看到的缺口是：conic constraints 本身可以外包给 ADMM projection，而 ADMM 的 primal update 仍是一个标准 LQ；因此真正需要优化的是这个 LQ 核。换言之，论文不是发明新的 conic projection，而是把 conic ADMM 里的最重计算核改造成 parallel-in-time dynamic programming。
Core Idea
核心思想是把一个全时域 LQ primal update 分解成若干 fixed-end LQ 子问题。每个子问题不只是给定初始状态向前解，而是同时以初始状态和终端状态为参数；这样它能在内部独立做 Riccati-like reduction，并输出一个关于两端 linkage states 的二次 conditional value function。
这件事理论上成立，因为对 LQ 问题，消去内部轨迹后得到的 value function 仍是二次形式，边界状态足以精确携带跨段耦合信息。和 prior 的本质区别在于，它把 conic constraint handling 与 temporal decomposition 分层：ADMM 负责把 cone 变成投影，PDP-style reduction 负责把 LQ 时间结构并行化。相比直接 sparse factorization，它不是解一个大 KKT；相比普通 Riccati，它改变了信息流组织方式，从逐 stage 串行传播变成“块内并行压缩 + 块间低维协调”。
Method
方法的必要机制可以概括为三步。第一，conic ADMM reformulation：把 cone feasibility 放进 slack projection，把 primal update 写成带增强二次项的 unconstrained LQ。这样做的价值是把复杂约束从 Riccati 内核中剥离出来，避免在每个 stage 直接处理 cone KKT。
第二，fixed-end reduction：每个时间块固定首尾状态，对内部 states/controls 做动态规划消元，并保留终端 multiplier 依赖。它解决的是时间切分后“块内最优轨迹如何依赖块边界”的问题；核心变化是每个块只向 consensus 暴露少量矩阵参数，而不是暴露整段轨迹。
第三，linkage consensus：把各块 conditional value functions 拼成关于 linkage states 的小型优化问题，通过结构化 backward elimination 求解边界状态和 multipliers。它解决的是并行子问题之间的一致性恢复。load balancing 的作用更工程化：fixed-end 子问题比最后的 free-end 子问题贵，如果均匀切分会造成线程等待，因此需要让最后一段更长来减少 straggler。
Key Insight / Why It Works
最核心的 insight 是：对 LQ，长时域轨迹的跨段影响可以被精确压缩成边界状态上的二次 value function；因此 temporal decomposition 不必牺牲最优性。这个压缩是方法成立的数学原因，也是它比一般并行 sparse factorization 更有结构优势的地方。
真正有效的部分大概率是“ADMM primal LQ + fixed-end Riccati reduction + low-dimensional consensus”的组合，而不是某个线性代数 kernel。ADMM 让 conic constraints 不进入 Riccati recursion；fixed-end value function 让每段可以独立；consensus 让块间耦合维度从 O(N) 降到 O(J n_x)。这本质上是 memory reuse / latent structure compression，而不是 learning-style scaling。
但性能增益并不完全来自算法思想。square-root Riccati、Cholesky 而非 LDLᵀ、矩阵 packing、OpenMP 线程预绑定、load balancing 都是强 engineering 因素。尤其和 ProxLQR 的差异，部分来自 factorization 对象不同：ProxLQR 为了数值稳定处理更大的 stage matrix，而本文在 ADMM primal update 中做较小的 Cholesky。这里的“更快”不等价于“更稳”或“更通用”。
另一个重要判断是：parallelism 只在额外 fixed-end cost 和 consensus cost 被 amortized 时成立。短 horizon 且 constraint 少时，切分可能不划算；约束多时，stage constraint 形成的额外 flop 提高了块内工作量，反而更容易掩盖切分开销。也就是说，这个方法偏好 compute-heavy per-stage LQ，而不是所有 LQ 都天然受益。
Relation To Prior Work
这篇最接近 Wright 的 PDP、endpoint-explicit / temporal parallel Riccati，以及 Jallet et al. 的 ProxLQR。它不是从零发明 parallel dynamic programming，而是在 conic ADMM 的 LQ primal step 上重新组合这些思想，并用 square-root Riccati 与更轻的 consensus factorization 做到更高效。
和传统 Riccati / acados-style LQR 的本质差异是时间信息流：传统方法沿 horizon 串行后退/前推，本文先在块内并行压缩，再在 linkage states 上协调。和 sparse LDLᵀ / QDLDL 的差异是结构利用粒度：后者把问题当带状 KKT，本文把它当可动态规划消元的 LQ。和 ProxLQR 的差异更微妙：两者都做 parallel constrained LQ，但本文通过 ADMM 约束分离和 fixed-end square-root reduction，避免在 stage 上 factorize 更大的 constrained matrix；代价是依赖 ADMM 外层和特定 primal LQ 形式。
实质创新主要在于：把 conic ADMM 的 primal update 与 fixed-end PDP-style reduction 对接，并给出适合该形式的 Riccati recursion 与 consensus 公式。看似新的部分中，divide-and-conquer、conditional value function、linkage state consensus 都有明确前史；真正新增的信息是它们在 conic LQ solver 中的组合方式和性能工程化边界。
Dataset / Evaluation
evaluation 选择了两个工程问题：quadrotor hover 代表短 horizon、多 box constraints；low-thrust orbital transfer 代表长 horizon、SOC constraint。这覆盖了作者最希望证明的两个 regime，但场景数仍然少，不能说明对一般 robotics / aerospace MPC 都稳定有效。
实验主要验证的是单次 LQ solve 的 computational kernel，而不是完整 conic MPC pipeline。作者报告的 speedup 对“parallel-in-time LQ primal update 更快”是有说服力的，但对“完整 conic optimal control 更快、更稳、更实时”支持不足。尤其 ADMM 迭代次数、termination criterion、warm start、不同 cone projection 成本、outer SQP/DDP 交互，都没有成为评估重点。
benchmark 设置相对认真，包括固定硬件、Google Benchmark、禁用 Turbo Boost、线程预创建与绑核。但这也意味着结果对 implementation 和硬件拓扑敏感。它证明了在 8-core laptop CPU 上能拿到实际加速，不等于证明算法在更大规模、多 socket、GPU 或嵌入式硬件上自然扩展。
Limitation
第一，方法的上限由 Amdahl law 很直接地限制：reduction 可并行，但 consensus 与 forward recovery 仍有串行/同步成分；当 J 增大或 N 不够长时，consensus factorization 会成为瓶颈。
第二，fixed-end 子问题本身比 free-end Riccati 贵。并行收益依赖每块足够长、每阶段计算足够重、线程开销足够低。短 horizon、低维、少约束场景下，所谓 parallelization 可能只是增加 overhead。
第三，文中未充分说明完整 ADMM 收敛行为。单次 primal LQ 更快不保证总 solve 更快；如果参数选择导致迭代数上升，或 cone projection / residual balancing 成为瓶颈，整体收益会下降。
第四，数值稳定性和鲁棒性讨论不够。ProxLQR 使用更重的 LDLᵀ 可能是为了处理更一般或更病态的结构；本文更快的 Cholesky/square-root 路线隐含了较好的正定性/regularization 条件。遇到 ill-conditioned dynamics、弱控制可达性、退化 cone constraints 时表现如何，文中未充分说明。
第五，增益归因不完全清晰。算法结构、factorization choice、cache locality、thread pinning、load balancing 都同时变化；因此 speedup 不能简单归因于 parallel dynamic programming 本身。
Takeaway
- 最值得记住的不是“Riccati 可以并行”，而是：conic MPC 中最重的 primal LQ step 可以通过 ADMM constraint splitting 变成一个适合 temporal decomposition 的对象。
- fixed-end value function 是可迁移的核心抽象：只要子问题消元后能把跨块依赖压缩到边界变量，就可以把长时域 optimal control 改造成 reduction + consensus。
- 未来真正值得做的是端到端 solver 视角：把 ADMM / ALM / IPM 外层迭代数、warm start、numerical conditioning 和 parallel LQ kernel 联合优化，而不是只优化单次 LQ solve。
- 这条路线更像结构化并行数值优化，而不是新的控制理论；它的价值在于把现代多核硬件能力引入原本串行的 MPC 内核。
一句话总结
《Parallel Dynamic Programming for Conic Linear Quadratic Control》（arXiv preprint / 2026）把 conic ADMM 的 LQ primal update 重组为 fixed-end parallel dynamic programming 加低维 linkage consensus，是对 PDP/Riccati 系列在 conic MPC 计算核上的一次结构化并行化推进。