🔢 mathematics

Scalable Deep Unfolding of Conic Optimizers

本文引入了一种用于大规模半正定规划的可扩展深度展开框架，该框架通过无矩阵隐式微分和鲁棒的特征值感知反向规则，克服了内存与数值稳定性障碍，从而实现了学习策略，其速度较最先进的锥规划求解器提升高达 50 倍。

原作者： Alex Oshin, Rahul Vodeb Ghosh, Evangelos A. Theodorou

发布于 2026-06-15

📖 1 分钟阅读🧠 深度阅读

原作者： Alex Oshin, Rahul Vodeb Ghosh, Evangelos A. Theodorou

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下你正在试图解决一个巨大且复杂的拼图。在机器人和工程领域，这些拼图被称为优化问题（optimization problems）。它们被用来计算机器人移动的最佳方式、如何安全地驾驶汽车，或者如何管理电网。

长期以来，计算机一直使用“迭代优化器”来解决这些拼图。你可以把这些优化器想象成一个非常循规蹈矩但动作缓慢的徒步旅行者，正试图寻找山谷的底部。他们走一步，检查是否更低了，再走一步，如此重复数千次，直到到达谷底。

**深度展开（Deep Unfolding）*是一种教这个徒步旅行者从“走路”变为“奔跑”的新方法。与其仅仅遵循一套僵化的规则，不如给这位徒步旅行者配备一位“教练”（神经网络）。这位教练会通过经验进行学习，并根据以往解决拼图时的最佳实践，准确地告诉徒步旅行者应该迈出多大的步子，以及何时改变方向。这篇论文的研究重点，就是教这位教练如何应对那些最宏大、最困难*的拼图。

以下是这篇论文故事的拆解，使用了简单的类比：

问题所在：“内存墙”与“粘性地板”

研究人员尝试将这种“教练”系统应用于一种名为 COSMO 的特定求解器，它非常擅长处理大规模问题。然而，他们遇到了两个巨大的障碍，阻碍了教练的学习效率：

内存墙（线性系统）：
为了迈出一步，求解器必须解出一个涉及巨大数字矩阵的庞大数学方程。为了教导教练，计算机需要记住它是如何解出那个方程的，以便稍后能从错误中学习。
- 旧方法： 这就像是为了弄明白如何在沙滩上行走，而试图记住沙滩上的每一粒沙子。随着拼图规模的增大，计算机的内存（RAM）会爆炸式增长并导致崩溃。这是一个 $O(n^2)$ 的问题——这意味着拼图规模翻倍，所需的内存会变为原来的四倍。
- 论文的解决方法： 他们发明了一个**“无矩阵”（Matrix-Free）技巧**。他们意识到，不需要写下整个数字网格，只需要知道这个网格对一次“推力”的反应（即矩阵-向量乘积）即可。这就像是通过感受脚下沙子的触感来学习如何在沙滩上行走，而不是试图背诵整张沙滩地图。这把所需的内存从一个巨大的仓库缩减到了一个小型背包（ $O(n)$ ），使得处理以前无法处理的巨型拼图成为可能。
粘性地板（特征值问题）：
有些拼图涉及一种特殊的形状，叫做“PSD 锥”。为了解决它，计算机必须观察拼图的“特征值”（Eigenvalues，可以理解为拼图独特的频率或音调）。
- 旧方法： 当两个这样的音调完全相同时（重复特征值），用于教导教练的数学逻辑就会崩溃。这就像是在尝试计算一个完全平坦的地面的坡度；数学公式会显示“除以零”，导致计算机崩溃或给出荒谬的答案。这在他们特定的机器人问题中经常发生。
- 论文的解决方法： 他们使用了一个精密的数学工具，称为 Daleckii–Krein 公式。你可以把它想象成一个数学界的“特制搅拌机”。它不会在平坦处卡住，而是知道如何精准处理两个音调完全相同的情况，从而保持数学过程的稳定性和学习过程的持续进行。

结果：超级跑步者

一旦解决了这两个障碍，他们便训练出了这位“教练”来引导 COSMO 求解器。

加速效果： 学习后的求解器变得异常快速。在某些测试中，它的求解速度比标准的、未经训练的求解器快了 50 倍。
现实世界测试： 他们在“协方差控制”（Covariance Steering）问题上进行了测试。想象一下，一个机器人在试图引导一团不确定性（比如一群蜜蜂）从 A 点移动到 B 点，同时还要避免碰撞。当这个新求解器作为更大规划系统中的辅助工具时，它让整个过程快了 30 倍。
对比： 它甚至能与通常被认为是顶尖水平的“金标准”求解器（如 Clarabel）一较高下，但在处理机器人实时面临的特定类型问题时，它的速度要快得多。

总结

这篇论文并没有发明一种新的机器人或一种新的数学问题。相反，它修复了解决这些问题的“引擎”。

他们移除了内存瓶颈，让引擎可以在处理巨大拼图时不会因为“没油”而停下。
他们修复了数学不稳定性，让引擎在路况变得复杂时不会“熄火”。

其结果是一个“习得式”优化器，它就像一位经验丰富的资深徒步旅行者，深谙如何应对各种地形，能在极短的时间内解决复杂的机器人问题。

技术摘要：大规模锥优化器的深度展开

问题陈述

深度展开（Deep Unfolding, DU）已被证明在加速包括压缩感知和机器人技术在内的各种领域的迭代优化器方面非常有效。然而，将 DU 扩展到大规模半正定规划（SDP）——这在协方差控制（covariance steering）等机器人应用中很常见——受到了两个特定障碍的阻碍，当展开全更新 ADMM 类锥求解器（例如 COSMO）时尤为明显：

线性系统求解中的内存瓶颈： 在每次迭代中对线性系统求解进行反向传播通常需要显式构建系数矩阵。对于 ADMM，这涉及项 $A^\top A$ 。即使约束矩阵 $A$ 是稀疏的， $A^\top A$ 通常也是稠密的，导致 $O(n^2)$ 的内存复杂度。这限制了其扩展到大规模问题规模的能力，因为直接分解会耗尽内存。
PSD 投影中的数值不稳定性： 向正定（PSD）锥的投影需要特征分解。标准的自动微分通过该操作的反向传播涉及形式为 $1/(\lambda_i - \lambda_j)$ 的项。当特征值重合时（在训练过程中经常发生，尤其是在具有各向同性协方差目标的情况下），这些项会导致数值不稳定或梯度未定义（NaN）。

方法论

作者提出了一个针对 COSMO 求解器的深度展开框架，该框架通过自定义反向规则解决了上述两个障碍，从而能够学习大规模锥问题的超参数策略和热启动（warm-starts）。

1. 用于线性求解的无矩阵隐式微分

为了避免形成稠密 $A^\top A$ 矩阵带来的 $O(n^2)$ 内存开销，作者采用了基于共轭梯度（CG）线性系统求解的无矩阵隐式微分规则。

前向传递： 求解器使用间接模式，利用 CG 求解缩减后的正规方程 $(P + \sigma I + A^\top D(\rho)A)\tilde{x} = \xi$ ，该过程仅依赖于矩阵-向量乘法（matvecs）。
反向传递： 作者没有展开 CG 迭代或构建稠密雅可比矩阵，而是推导了一个基于伴随系统的规则。通过使用相同的 CG 方法求解伴随系统 $M\tilde{\lambda} = -\nabla_{\tilde{x}}L$ ，对超参数 $\rho$ 的梯度计算为 $\nabla_\rho L = (A\tilde{\lambda}) \odot (A\tilde{x})$ 。
结果： 该方法从未显式形成稠密的系数矩阵，将内存复杂度从 $O(n^2)$ 降低到 $O(n + \text{nnz}(A))$ ，从而使反向传播能够在以往方法失效的大规模规模下运行。

2. 用于 PSD 投影的稳定反向规则

为了解决特征分解在重复特征值下的不稳定性，作者使用基于 Dalečii–Krein (DK) 表示 的 Fréchet 导数反向规则取代了标准的自动微分。

机制： PSD 投影被视为一个主要矩阵函数 $T = U f(\Lambda) U^\top$ ，其中 $f(x) = \max(x, 0)$ 。DK 定理提供了一个导数公式，其中奇异项 $1/(\lambda_j - \lambda_i)$ 被分子 $f(\lambda_j) - f(\lambda_i)$ 相乘。
稳定性： 当特征值重合（ $\lambda_i = \lambda_j$ ）时，分子以相同的速率消失，从而产生一个由极限 $f'(\lambda_i)$ 定义的可去奇点。这确保了即使在存在重复特征值时，梯度仍然是有限且有定义的。
效率： 该规则复用了在前向传递中计算的特征分解，与朴素方法相比，不会产生额外的渐近计算成本，这与使用 Newton-Scholz 迭代进行展开的替代方案不同。

核心贡献

可扩展的线性系统微分： 一种无矩阵隐式微分规则，将内存使用量从 $O(n^2)$ 降低到 $O(n)$ ，实现了大规模 SDP 上全更新锥求解器的深度展开。
数值稳定的 PSD 投影： 一种基于 Dalečii–Krein 定理的反向规则，在重复特征值下保持定义良好，这是训练协方差控制和其他 SDP 问题的关键要求。
经验验证： 证明了这些规则允许展开 COSMO 求解器以学习轻量级超参数策略和热启动。所学习的方法在独立的 SDP/SOCP 以及作为非线性协方差控制中序列凸规划（SCP）的子程序进行了评估。

结果

作者在多个问题类别上，将学习到的 COSMO 求解器与标准 COSMO 求解器（带有自适应启发式算法）以及最先进的内点求解器 Clarabel 进行了对比评估：

独立 SDP 和 SOCP： 学习到的策略根据问题类实现了显著的加速：
- Lovász $\vartheta$ SDPs： 墙钟时间（wall-clock time）最高提升达 50.4 倍。
- Max-cut SDPs： 2.62 倍 加速。
- 鲁棒卡尔曼滤波器（Robust Kalman Filters）： 4.91 倍 加速。
- Lyapunov LMIs： 1.16 倍 加速。
非线性协方差控制 (SCP)： 当作为非线性系统（双积分器和单轮车动力学）中 SCP 的子程序使用时，学习到的方法相比原始 COSMO 实现了 30 倍 的加速。
内存扩展性： 实验表明，虽然基准方法在变量数 $n \approx 20\text{--}50k$ 时就会耗尽 GPU 内存（24 GB），但所提出的无矩阵方法呈线性扩展，即使在 $n=50k$ 时也保持在 300 MB 以下。

意义与局限性

本文声称这些贡献使得将深度展开应用于大规模锥优化成为可能，而此前该领域一直受到内存和数值稳定性约束的限制。学习到的策略为需要固定计算预算的实时机器人应用提供了实质性的加速。

作者指出了具体的局限性：

可扩展性： 虽然线性求解是无矩阵的，但 PSD 投影仍然需要针对每个大小为 $p$ 的半正定块进行稠密的 $O(p^3)$ 特征分解。扩展性的增益体现在变量/约束的数量上，而非块的大小本身。
精度区间： 该方法针对的是低到中等精度（ $\epsilon \approx 10^{-3}$ ），这在实时控制中很常见。它并不声称在紧致容差下能超越内点求解器（如 Clarabel），因为一阶方法在紧致容差下的收敛速度较慢。
训练开销： 每个问题族都需要训练一个单独的策略，这会产生预先成本（大约每个类别 100 个问题），该成本必须在多次求解中进行摊销。目前的工作尚未展示跨家族的迁移能力，也未展示向训练时规模大幅增加的实例进行扩展的能力。