让大型锥优化求解器可学习、可加速,实现50倍提速。
Scalable Deep Unfolding of Conic Optimizers
- 提出无矩阵隐式微分法,内存从O(n²)降至O(n)
- 用Dalečkii-Krein方法解决特征值重合时的数值不稳问题
- 在机器人路径规划等任务中实现30-50倍加速,适合高维优化场景
深度展开(DU)通过引入可学习组件并训练展开迭代来加速迭代优化器,但将其扩展到机器人中常见的大规模半定规划(SDP)仍受限。以COSMO为代表的全更新锥求解器在展开时面临两大挑战:每轮迭代的线性系统求解反向传播导致内存随问题规模呈O(n²)增长,且正定锥投影的反向传播在特征值重合时数值不稳定。本文提出一种完全基于矩阵-向量乘积的无矩阵隐式微分规则,将内存降至O(n),解决了内存瓶颈;同时采用基于Dalečkii–Krein表示的导数反向传播方法,确保特征值重复时仍稳定。两者结合使轻量级超参数策略和热启动方案成为可能。在非线性协方差导向问题(通过顺序凸规划求解)以及各类独立的SDP和二阶锥规划(包括max-cut、Lovász θ SDP、鲁棒估计与控制问题)上验证,所学策略优于现有最优求解器,提速最高达50倍;作为顺序凸规划子程序时,相比COSMO提升超30倍。
原文摘要 · Abstract (English)
Deep unfolding (DU) accelerates iterative optimizers by introducing learnable components and training them through unrolled iterations, but extending DU to the large-scale semidefinite programs (SDPs) common in robotics has remained limited. Unrolling a full-update conic solver such as COSMO exposes two obstacles that prior work on learned conic solvers has not: backpropagating through the per-iteration linear-system solve incurs memory quadratic in the problem size once the coefficient matrix is formed explicitly, and backpropagating through the positive semidefinite (PSD) cone projection becomes numerically unstable when eigenvalues coincide. We address the first obstacle with a matrix-free implicit differentiation rule that operates entirely through matrix-vector products, reducing memory from $O(n^2)$ to $O(n)$ and enabling backpropagation at scales where direct factorization runs out of memory. We address the second with a backward rule based on the Dalečkii--Krein representation of the Fréchet derivative, which remains well-defined under repeated eigenvalues. Together these make it possible to learn lightweight hyperparameter policies and warm-starts for a full-update conic solver. We evaluate on nonlinear covariance steering problems solved via sequential convex programming (SCP), as well as standalone SDPs and second-order cone programs ranging from max-cut and Lovász $\vartheta$ SDPs to robust estimation and control problems. The learned policies outperform state-of-the-art solvers across all problems, and can provide up to a 50$\times$ speedup depending on the class. When used as a subroutine in SCP, the learned approach delivers over a 30$\times$ speedup compared to COSMO.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。