BPQP：加速可微凸优化层的端到端学习框架

论文：BPQP: A Differentiable Convex Optimization Framework for Efficient End-to-End Learning (NeurIPS 2024) 作者：Jianming Pan, Zeqi Ye, Xiao Yang, Xu Yang, Weiqing Liu, Lewen Wang, Jiang Bian 单位：UC Berkeley, Nankai University, Microsoft Research Asia 代码：microsoft/qlib

这篇论文是 NeurIPS 2024 上一篇关于"如何让神经网络中的优化层反向传播变快"的工作。读完后我觉得它的核心 idea 非常优雅——一句话概括是：

把反向传播中昂贵的 KKT 矩阵求逆问题，重构为一个等价的 QP 问题，用 ADMM 高效求解。

但要真正理解这句话，需要补充不少前置知识。本文面向对优化理论不太熟悉的算法工程师，会沿着"问题 → 抽象 → 前置知识 → 现有方案 → 论文方法"的路线，把整个故事讲清楚。中间会有相对详细的凸优化、KKT、隐函数定理介绍——熟悉的读者可以自行跳过。

一、背景：金融中的一个真实难题

投资组合优化

假设你是一个量化基金的投资经理，手上管理着 500 只股票，每天都要决定一件事：这些股票各应该配置多少比例的资金？

经典的解法是马科维茨的均值-方差优化（Mean-Variance Optimization, MVO）：

$$ \max_w\ \mu^\top w - \frac{\gamma}{2} w^\top \Sigma w \quad \text{s.t.}\ \mathbf{1}^\top w = 1,\ w \geq 0 $$

其中：

$w \in \mathbb{R}^{500}$ 是每只股票的投资比例（要决策的变量）
$\mu \in \mathbb{R}^{500}$ 是每只股票的预期收益率
$\Sigma$ 是收益率的协方差矩阵（衡量风险）
$\gamma$ 是风险厌恶系数
约束保证权重和为 1 且不能做空

为什么是 MVO，而不是直接最大化收益？

很多算法工程师第一次看到这个目标会困惑：为什么不直接 $\max_w\ \mu^\top w$ 把所有钱投到预期收益最高的那只股票就行了？

答案是：金融决策的目标不只是收益高，还要稳定。具体有几个层次的原因：

第一，预期收益率 $\mu$ 是预测出来的，不是真值。预测必然有噪声。如果你 all-in 一只股票，预测稍有偏差，整个组合就崩了。

第二，即使预测完全准确，“预期收益最高"和"真实收益最高"也不是一回事——预期是均值，真实结果是随机的。一只预期收益 10% 但波动 50% 的股票，和一只预期收益 8% 但波动 5% 的股票，理性投资者更可能选后者。这就是经济学里的风险厌恶。

第三，分散投资能降低组合风险。两只不完全相关的股票各投 50%，整体波动会小于单独持有任一只——这就是协方差矩阵 $\Sigma$ 在目标函数中起的作用。

所以 MVO 的目标函数 $\mu^\top w - \frac{\gamma}{2} w^\top \Sigma w$ 同时考虑了：

收益项 $\mu^\top w$：让组合的期望收益越高越好
风险项 $\frac{\gamma}{2} w^\top \Sigma w$：惩罚组合的方差（波动），$\gamma$ 决定多在乎风险

这是一个标准的凸优化问题（具体来说是 QP，后面会讲），给定 $\mu$ 和 $\Sigma$ 可以用现成求解器秒解。

真正的问题：$\mu$ 怎么来？

没人能直接观测到"明天的收益率”，所以工业界通常用神经网络来预测：

$$ \text{历史价格、成交量等特征} \xrightarrow{\text{神经网络}} \hat{\mu} $$

然后把 $\hat{\mu}$ 喂给 MVO，得到投资比例 $w^*$。这就是经典的两阶段方法。

两阶段方法的致命缺陷

这种"先预测、后优化"的两阶段方法有一个非常隐蔽的问题：

预测准 ≠ 投资好。

举个直觉：

股票 A 真实收益率 1.0%，股票 B 真实收益率 1.1%
网络预测 A = 0.5%，B = 0.6%（绝对误差挺大）
但优化器仍然会选 B（因为相对排序对了）→ 投资决策完美

反过来：

网络预测 A = 1.05%，B = 1.0%（绝对误差很小）
优化器会选 A → 投资决策错了

也就是说，神经网络在用"预测误差"作为损失训练，但真正决定我们能不能赚钱的是最终的投资决策。这两个目标并不一致。

端到端学习

理想做法是：让整个流程端到端训练。

特征 → [神经网络] → μ̂ → [MVO 优化器] → w* → 实际收益（损失函数）
                                              │
                                              └── 反向传播训练神经网络

这样神经网络的训练目标直接是"让最终决策赚的钱最多"，而不是"让 $\mu$ 预测得准"。

但这里有个问题：MVO 优化器这一层不是普通的神经网络层，它是一个"求解优化问题"的过程。怎么对它求导？怎么把损失函数的梯度从 $w^*$ 一路传回神经网络？

这就是本文要解决的核心问题。

二、抽象成数学问题：什么是可微优化层

普通神经网络层

我们熟悉的神经网络层都是显式函数，比如 $z = \sigma(Wy + b)$。输入 $y$，经过一系列直接的算术运算得到输出 $z$。求导很简单，PyTorch 的自动微分能直接搞定。

可微优化层

但 MVO 这一层不一样——它的输出是一个优化问题的最优解：

$$ z^*(y) = \arg\min_z f_y(z) \quad \text{s.t.}\ h_y(z) = 0,\ g_y(z) \leq 0 $$

其中 $y$ 是上一层的输出（在 MVO 例子里就是预测的收益率 $\hat\mu$），$z^*$ 是下一层的输入（最优投资比例 $w^*$）。

注意"下标 $y$“的写法——意思是优化问题本身的目标函数和约束都依赖参数 $y$。也就是说，$y$ 不是被代入某个公式得到 $z$，而是用来定义一个优化问题，然后这一层的输出 $z^*$ 是这个问题的最优解。

核心区别：

普通层	可微优化层
输出 = 公式直接算出来	输出 = 优化问题解出来
内部：一次前向运算	内部：调用优化求解器迭代
处理约束：困难	处理约束：天然满足
求导：链式法则	求导：???（这就是难点）

为什么不直接让网络输出 $w$？

你可能会问：神经网络是万能逼近器，为什么不直接让它输出投资比例 $w$？

理论上可以，但实际有几个大问题：

约束保证难：要保证 $\sum w_i = 1$ 且 $w_i \geq 0$ 很麻烦。Softmax 能做权重和为 1，但更复杂的约束（“换手率不超过 20%"、“行业集中度限制”）几乎不可能用普通网络层保证。
领域知识难嵌入：MVO 几十年来的金融理论积累被白白浪费。让神经网络从零学习"什么是好的风险-收益权衡"远比把它直接编码进 MVO 来得困难。
可解释性差：黑盒输出 vs “在风险约束下的最优配置”。后者向客户和监管机构解释起来容易得多。

类似的场景在工程界还有很多：能源调度（在物理约束下最小化成本）、机器人轨迹规划（在动力学约束下达到目标位置）、网络资源分配，等等。只要任务本身就包含"在约束下做最优决策"的成分，把优化问题做成一层嵌入网络就是一个很自然的选择。

前向 vs 反向

可微优化层的前向传播没什么神秘的——调用一个凸优化求解器解出 $z^*$ 就行。慢一些，但思路直接。

反向传播才是真正的难题。要做反向传播，需要计算 $\frac{\partial z^*}{\partial y}$，也就是"当 $y$ 微小变化时，最优解 $z^*$ 怎么变？“但 $z^*$ 没有显式公式——它是优化问题的解。怎么求导？

这就需要一些数学工具——KKT 条件和隐函数定理。

三、前置知识（一）：KKT 与隐函数定理

这一节会比较慢，会用一些图像化的直觉解释。如果你已经熟悉 KKT 和隐函数定理，可以直接跳到第四节。

3.1 从无约束到带约束：拉格朗日的智慧

无约束情况：导数 = 0

如果你想找一个 $x$ 让 $f(x) = (x-3)^2$ 最小，凭直觉：$x = 3$ 时 $f = 0$，最小。

数学上的方法：求导让导数为零，$f'(x) = 2(x-3) = 0 \Rightarrow x = 3$。多元情况就是梯度为零：$\nabla f(x^*) = 0$。

加入等式约束：直接求导失效

升级一下问题：

$$ \min_{x_1, x_2}\ x_1^2 + x_2^2 \quad \text{s.t.}\ x_1 + x_2 = 1 $$

几何含义：在直线 $x_1 + x_2 = 1$ 上，找离原点最近的点。凭直觉答案是 $(0.5, 0.5)$。

但如果套用"梯度 = 0”，得到 $(2x_1, 2x_2) = 0 \Rightarrow x = (0,0)$——它根本不在约束直线上！这个方法完全没用约束信息。

拉格朗日的天才想法

为什么"梯度 = 0"在这里失败？因为它适用于"全方向无下降"的情形，但带约束时，我们只需要”在约束允许的方向上无下降”。

拉格朗日的关键洞察是几何上的：在最优点，目标函数的等高线必须与约束曲线"相切"。

为什么？想象你在直线上走来走去，目标是让 $f$ 越小越好。每走到一个点看一眼当前的 $f$ 等高圆。如果等高圆和直线"穿过"（相交），你沿着直线总能继续走到一个 $f$ 更小的等高圆。只有等高圆和直线相切时，沿着约束方向再走 $f$ 不会下降——这就到了最优点。

数学上"相切"等价于：$\nabla f$ 和 $\nabla h$（约束的梯度）平行。也就是存在一个数 $\nu$（叫拉格朗日乘子）使得：

$$ \nabla f + \nu \nabla h = 0 $$

加上"约束被满足"的条件 $h(x) = 0$，两个条件合起来描述了最优点。

拉格朗日把这两个条件巧妙地"打包"成一个新函数：

$$ L(x, \nu) = f(x) + \nu \cdot h(x) $$

然后对所有变量（包括 $\nu$）求偏导 = 0：

$\frac{\partial L}{\partial x_i} = 0$ 给出 $\nabla f + \nu \nabla h = 0$（梯度平行条件）
$\frac{\partial L}{\partial \nu} = 0$ 给出 $h(x) = 0$（约束被满足）

带约束问题 → 解一组方程组。这就是拉格朗日乘子法的精髓。

顺带一提：拉格朗日乘子 $\nu$ 不是凑出来的辅助变量，它有清晰的经济学含义——约束被放松一点点，最优值能改善多少（叫"影子价格"）。在 MVO 里，约束 $\mathbf{1}^\top w = 1$ 的乘子就告诉你"再多给一块钱预算，最优收益能多多少"。

3.2 KKT 条件：处理不等式约束

再升级一次，加上不等式约束：

$$ \min_x\ f(x) \quad \text{s.t.}\ h(x) = 0,\ g(x) \leq 0 $$

不等式约束 $g(x) \leq 0$ 几何上是一堵"墙"——只有 $g(x) \leq 0$ 这一侧才允许。最优点要么"顶在墙上"（$g(x^*) = 0$），要么"远离墙"（$g(x^*) < 0$，约束没起作用）。

KKT 条件就是处理这两种情况的扩展。最优解 $x^*$ 必须满足以下四条：

稳定性：$\nabla f + \nu \nabla h + \lambda \nabla g = 0$ （目标函数的"拉力"和约束的"反作用力"平衡）
原始可行性：$h(x^*) = 0,\ g(x^*) \leq 0$ （解必须在可行域内）
对偶可行性：$\lambda \geq 0$ （不等式约束这堵"墙"只能往一个方向推，反作用力非负）
互补松弛：$\lambda_i \cdot g_i(x^*) = 0$ （要么约束起作用 $g_i = 0$（顶在墙上），要么乘子为零 $\lambda_i = 0$（约束没起作用），两者必有一个为 0）

一个具体例子

考虑 $\min (x-3)^2$ s.t. $x \leq 1$。约束是 $g(x) = x - 1 \leq 0$。

凭直觉：目标想把 $x$ 拉到 3，但被墙挡在 $x = 1$，最优点是 $x^* = 1$。

用 KKT 验证：

互补松弛分两种情况：
- $\lambda^* = 0$：稳定性给出 $2(x^* - 3) = 0 \Rightarrow x^* = 3$，但违反 $x \leq 1$ ✗
- $g(x^*) = 0$：$x^* = 1$，稳定性给出 $\lambda^* = 4 > 0$ ✓

最终 $x^* = 1$，$\lambda^* = 4$。

互补松弛与 active set

互补松弛引出一个非常重要的概念——有效集（active set）。

对于多个不等式约束 $g_1(x) \leq 0, \ldots, g_n(x) \leq 0$：

若 $g_i(x^*) = 0$（约束"紧"，顶到墙上）→ 有效约束，此时 $\lambda_i^*$ 可能 $> 0$
若 $g_i(x^*) < 0$（约束"松"，没顶到墙）→ 无效约束，此时 $\lambda_i^* = 0$

有效集就是所有"紧"约束的索引集合。这个概念后面会成为 BPQP 的核心。

3.3 KKT 条件的本质

把 KKT 条件抽象一下：

KKT 条件把"找最优解"变成了"解一组方程组"。这组方程同时涉及原变量 $x$ 和拉格朗日乘子 $\lambda, \nu$。

更重要的是，对于参数化的优化问题（参数为 $y$，最优解为 $z^*$），KKT 条件构成了一个把最优解和参数联系起来的隐式方程：

$$ \mathcal{F}(z^*, \lambda^*, \nu^*; y) = 0 $$

注意"隐式"两个字——$z^*$ 没有显式公式，但它和 $y$ 通过 KKT 方程组绑定。这正是隐函数定理的用武之地。

3.4 隐函数定理：从隐式关系求导

显式 vs 隐式

显式函数 $z = f(y) = y^2 + 3y + 1$，求 $\frac{dz}{dy}$ 直接求导。

隐式函数：$z$ 和 $y$ 不通过公式直接表达，而是满足某个方程 $F(z, y) = 0$。比如单位圆 $z^2 + y^2 - 1 = 0$。

隐式情况下能不能求 $\frac{dz}{dy}$？

关键想法：对方程两边求全导

对 $F(z(y), y) = 0$ 两边关于 $y$ 求全导数（链式法则）：

$$ \frac{\partial F}{\partial z} \cdot \frac{dz}{dy} + \frac{\partial F}{\partial y} = 0 $$

整理得：

$$ \frac{dz}{dy} = -\left(\frac{\partial F}{\partial z}\right)^{-1} \frac{\partial F}{\partial y} $$

这就是隐函数定理。它告诉我们：即使写不出 $z$ 的显式公式，只要有方程 $F(z, y) = 0$，就能求 $\frac{dz}{dy}$。

用单位圆例子验证

$F(z, y) = z^2 + y^2 - 1$，$\frac{\partial F}{\partial z} = 2z$，$\frac{\partial F}{\partial y} = 2y$，所以 $\frac{dz}{dy} = -\frac{y}{z}$。

直接从 $z = \sqrt{1-y^2}$ 求导得到的也是 $-\frac{y}{z}$——完全一致。

多元情形

$z, y$ 都是向量时，$z \in \mathbb{R}^d$，$y \in \mathbb{R}^p$，方程组 $F(z, y) = 0 \in \mathbb{R}^d$，公式变成：

$$ \frac{\partial z}{\partial y} = -\left[\frac{\partial F}{\partial z}\right]^{-1} \frac{\partial F}{\partial y} $$

核心思想一句话：隐函数定理把"隐式关系下的求导"转化成"解一个线性方程组"。

3.5 两者结合：可微优化层的求导公式

现在把两者拼起来：

KKT 条件 → 提供了 z* 和 y 的隐式方程 F(z*, λ*, ν*; y) = 0
隐函数定理 → 提供了从隐式方程求导的方法
组合起来 → 反向传播的梯度可以通过解一个线性方程组得到

具体地，对 KKT 方程组应用隐函数定理后，需要解（论文公式 3）：

$$ \underbrace{\begin{bmatrix} P & G^\top & A^\top \\ D(\lambda^*)G & D(g(z^*)) & 0 \\ A & 0 & 0 \end{bmatrix}}_{\text{KKT 矩阵 } K} \begin{bmatrix} \tilde z \\ \tilde \lambda \\ \tilde \nu \end{bmatrix} = -\begin{bmatrix} (\partial \mathcal{L}/\partial z^*)^\top \\ 0 \\ 0 \end{bmatrix} $$

各部分定义：

$P = \nabla_z^2 f + \sum \nu_i \nabla_z^2 h_i + \sum \lambda_i \nabla_z^2 g_i$（拉格朗日 Hessian）
$G = \nabla_z g(z^*)$（不等式约束的雅可比）
$A = \nabla_z h(z^*)$（等式约束的雅可比）
$D(\cdot)$：把向量放在对角线的对角矩阵

关键瓶颈：直接解这个系统需要做 $K^{-1}$，复杂度 $O(N^3)$。当 $N$ 上千甚至上万时（比如 500 只股票的 MVO），慢得无法接受。

四、现有方案与难点

针对"如何对优化层求导"，目前主流方法分两类。

方案一：显式展开法（Explicit Unrolling）

思路：既然 $z^*$ 是通过迭代算法（梯度下降、ADMM 等）算出来的，那就把每一步迭代记录下来，作为一个超长的显式计算图，让 PyTorch 自动微分。

举例：优化算法迭代了 100 步 $z_0 \to z_1 \to \cdots \to z_{100} \approx z^*$，每一步都是 $z_{k+1} = z_k - \alpha \nabla f(z_k)$，把这 100 步全部展开成计算图，然后反向传播。

优点：思路简单，套用现成自动微分框架。

缺点：

计算图随迭代次数线性增长，内存爆炸
处理约束很麻烦（要不断把解投影回可行域）
每加一步迭代，反向传播也跟着变贵

方案二：隐式微分法（Implicit Differentiation）

思路：不展开迭代过程，而是利用 KKT + 隐函数定理直接求梯度。

这就是上一节讲的方法：解线性方程组 $K \tilde x = b$，其中 $K$ 是 KKT 矩阵。

代表方法：OptNet、qpth、CvxpyLayer、Diffcp 等。

优点：

不需要存储所有迭代历史
与求解算法解耦（理论上）

缺点：

求解 KKT 系统本身很贵（$O(N^3)$ 矩阵分解）
实际中前向和后向往往紧耦合（OptNet 把内点法的状态共享给后向）
大规模问题（变量数 1000+）几乎跑不动

难点总结

把现状梳理一下：

方法	通用性	效率（小规模）	效率（大规模）
Unrolling	中	中	差
OptNet/qpth	仅 QP	好	差
CvxpyLayer	高	中	极差

核心难点：通用性和效率难以兼得，特别是在大规模场景下。

而金融场景（500 只股票的投资组合优化）正好需要"通用 + 大规模"——这就是 BPQP 的切入点。

五、前置知识（二）：凸优化与求解方法

这一节介绍凸优化的常见类型和求解方法。这是理解 BPQP 为什么"重构成 QP 后可以加速"的基础。

5.1 什么是凸优化？

凸优化的一般形式：

$$ \min_x f(x) \quad \text{s.t.}\ g_i(x) \leq 0,\ Ax = b $$

其中 $f$ 和所有 $g_i$ 都是凸函数。凸函数的几何含义是函数图像形如"碗"——任意两点的连线总在函数图像之上。

为什么凸优化重要？因为它有一个非常友好的性质：

凸优化的局部最优解 = 全局最优解。

只要找到一个满足 KKT 条件的点，就找到了全局最优。这让算法设计变得简单且可靠——不像非凸优化那样需要处理"陷在局部最优"的麻烦。

5.2 凸优化的层级

按表达能力从弱到强，常见的凸优化问题排成一个包含层级：

$$ \text{LP} \subset \text{QP} \subset \text{QCQP} \subset \text{SOCP} \subset \text{SDP} \subset \text{一般凸优化} $$

这里的"包含"是指"任何 A 类问题都能等价转化为 B 类问题"——不一定是形式上长得像，而是表达能力上包含。每往上一层都更通用，但也更难求解。

下面具体讲三种最常见的：LP、QP、SOCP。

LP（线性规划）

$$ \min_x\ c^\top x \quad \text{s.t.}\ A x = b,\ G x \leq h $$

目标和约束都是线性的。几何上，线性约束围出一个多面体，目标函数是一组平行的超平面，最优解一定在多面体的顶点上。

应用：运输问题、生产计划、资源分配、网络流。

QP（二次规划）

$$ \min_x\ \frac{1}{2} x^\top P x + q^\top x \quad \text{s.t.}\ A x = b,\ G x \leq h $$

目标是二次的（$P \succeq 0$ 半正定保证凸），约束仍然是线性的。要注意这一点——QP 的"约束"不是二次的，“约束二次"的版本叫 QCQP，是另一个层级。

几何上，目标函数是一个椭球面，最优解 = 在多面体内找到一个点，使它在椭球的最低层。

LP 是 QP 的特例（取 $P = 0$）。

应用：

投资组合优化（MVO 就是 QP！目标 $\frac{\gamma}{2}w^\top \Sigma w - \mu^\top w$ 是二次的，约束是线性的）
支持向量机（SVM）：$\min \frac{1}{2}\|w\|^2$ s.t. $y_i(w^\top x_i + b) \geq 1$
模型预测控制（MPC）：自动驾驶/机器人的实时控制
带约束的最小二乘问题

SOCP（二阶锥规划）

$$ \min_x\ c^\top x \quad \text{s.t.}\ \|A_i x + b_i\|_2 \leq c_i^\top x + d_i $$

目标线性，约束是"二阶锥约束”——即"某个向量的 2-范数 $\leq$ 某个线性函数"。每个约束限制点 $(A_i x + b_i, c_i^\top x + d_i)$ 必须在一个**二阶锥（冰淇淋锥）**内。

SOCP 比 QP 更通用——能表达椭球（QP 也能），还能表达"圆锥"这种"角度型"约束（QP 不能）。

经典应用：鲁棒线性规划。LP 假设参数 $a$ 是确定的，但实际有不确定性。如果只知道 $a$ 在某个椭球内 $\{a_0 + Pu : \|u\|_2 \leq 1\}$，“对所有 $a$ 都满足约束"会自然变成 SOCP 约束 $a_0^\top x + \|P^\top x\|_2 \leq b$。

其他应用：滤波器设计、波束成形（通信/雷达）、含不确定性的最优控制。

三者比较

特性	LP	QP	SOCP
目标	线性	二次（凸）	线性
约束	线性	线性	二阶锥
几何	多面体	椭球 ∩ 多面体	锥体 ∩ 多面体
求解难度	最易	容易	较难
表达能力	最弱	中	强（含 LP/QP）

5.3 求解方法（一）：内点法

要解上述问题，历史上发展出多种方法。先讲内点法（Interior Point Method, IPM）——它是商业求解器（Mosek、Gurobi、ECOS、OptNet 内核）的主力。

核心思想：障碍函数

把不等式约束 $g_i(x) \leq 0$ 改写为目标的一部分，加一个对数障碍：

$$ \min_x\ f(x) - \mu \sum_i \log(-g_i(x)) $$

直觉：当 $x$ 接近约束边界（$g_i(x) \to 0$）时，$\log(-g_i(x)) \to -\infty$，整个目标暴增到 $+\infty$——形成一道"墙”，逼着 $x$ 远离边界。参数 $\mu > 0$ 控制墙的强度。

路径跟踪

从一个内部点出发，先取较大的 $\mu_0$ 用牛顿法解，得到 $x_1$；逐渐减小 $\mu$（“墙"变薄），从上一步出发再用牛顿法解。这条路径叫中心路径，从内部"中心"逐渐逼近最优解。

牛顿步的代价

每次牛顿迭代要求解一个线性系统 $H \cdot \Delta x = -\nabla L$。这一步是内点法的瓶颈——需要做 $O(N^3)$ 的矩阵分解。对小到中等规模问题（变量数 $< 1000$）很快，但对大规模问题就慢了。

优缺点

优点：通用（LP/QP/SOCP/SDP 都能解）；理论复杂度好；精度极高（可达 $10^{-10}$）
缺点：每步都要做矩阵分解，对大规模稀疏问题不够快；难以并行化

5.4 求解方法（二）：一阶法 / ADMM

近 15 年的趋势：一阶法（只用梯度信息，不用 Hessian）成为大规模凸优化的主流。代表是 ADMM（交替方向乘子法）——这正是 BPQP 用的方法。

核心思想：拆分 + 交替

把复杂问题拆分成几个简单子问题，交替求解。考虑：

$$ \min_{x, z}\ f(x) + g(z) \quad \text{s.t.}\ Ax + Bz = c $$

构造增广拉格朗日函数：

$$ L_\rho(x, z, \nu) = f(x) + g(z) + \nu^\top(Ax + Bz - c) + \frac{\rho}{2}\|Ax + Bz - c\|^2 $$

ADMM 迭代：

固定 $z, \nu$，对 $x$ 求最小：$x_{k+1} = \arg\min_x L_\rho(x, z_k, \nu_k)$
固定 $x, \nu$，对 $z$ 求最小：$z_{k+1} = \arg\min_z L_\rho(x_{k+1}, z, \nu_k)$
更新乘子：$\nu_{k+1} = \nu_k + \rho (A x_{k+1} + B z_{k+1} - c)$

为什么 ADMM 适合 QP？

对 QP 问题，ADMM 的 $x$ 子问题简化为求解一个简单线性系统（矩阵正定），而这个矩阵在迭代中不变——所以可以预先做一次分解，后续每次迭代只要做矩阵-向量乘法！

OSQP 就是利用了这一点：把 QP 的求解变成"一次分解 + 多次廉价迭代”，对大规模稀疏 QP 极为高效。BPQP 默认就用 OSQP。

优缺点

优点：每步迭代廉价（只要矩阵-向量乘法）；天然适合稀疏问题；容易并行；对中低精度需求非常快
缺点：收敛速度是线性的（不像 IPM 是超线性），高精度需要的迭代次数较多

5.5 内点法 vs 一阶法

维度	内点法	一阶法（ADMM）
每步成本	高（$O(N^3)$ 矩阵分解）	低（$O(N^2)$ 或更低）
迭代次数	少（10-50 次）	多（100-1000 次）
总体快慢	中小规模快	大规模快
精度	极高	中等
并行化	难	易
利用稀疏性	部分	充分

经验法则：变量数 $< 1000$ 用内点法；$> 10000$ 用一阶法；中间地带看具体问题。

这里有一个值得记住的关键点：反向传播只需要中等精度（梯度有 $10^{-4}$ 精度就够训练了），所以一阶法的"精度差"对训练神经网络几乎不是问题；而它的"大规模快"恰恰是 BPQP 想要的。这就是 BPQP 选择 ADMM 而不是内点法的根本原因。

5.6 现代主流求解器

求解器	算法	适用	特点
Mosek	内点法	LP/QP/SOCP/SDP	商业，工业级精度
Gurobi	单纯形+内点法	LP/QP（含整数）	商业，最快的整数规划
ECOS	内点法	LP/SOCP	开源
OSQP	ADMM	QP	开源，BPQP 用这个
SCS	ADMM	LP/QP/SOCP/SDP	开源，CVXPY 默认
Clarabel	内点法	LP/QP/SOCP/SDP	开源新秀（Rust）

CVXPY 是一个 Python 库，可以用统一的语法描述凸优化问题，自动调用上述任一求解器。

六、BPQP 的核心方法

现在所有前置知识都准备好了，可以来看 BPQP 怎么巧妙解决问题。

6.1 核心洞察

BPQP 的核心 idea 一句话：

反向传播中要解的 KKT 线性系统，可以等价地重构为一个新的 QP 问题。

为什么这样做有意义？

QP 有非常成熟的高效求解器（OSQP）
求解 QP 用 ADMM，避开了 $O(N^3)$ 的矩阵分解
前向和反向完全解耦——前向用任意求解器，反向用 OSQP，互不影响

6.2 解耦：BPQP 的整体架构

┌──────────────────────────────────────────────┐
│                   前向传播                     │
│  y → [凸优化问题 + 任意求解器] → z*            │
│                                                │
│         ⋮ ─── 解耦 ─── ⋮                      │
│                                                │
│                   反向传播                     │
│  ∂L/∂y ← [OSQP 解 QP] ← [KKT→QP 重构] ← ∂L/∂z*│
└──────────────────────────────────────────────┘

之前的方法（OptNet 等）前向后向是紧耦合的——前向用什么算法决定了反向只能用配套方法。BPQP 把它们彻底解耦：前向爱用什么求解器都行，反向统一走 QP 路线。

6.3 关键转化：KKT 系统 → 等式约束 QP

这是论文的定理 1，也是最精彩的部分。我们一步步推。

步骤 1：观察 KKT 系统的结构

回顾反向传播要解的系统：

$$ \begin{bmatrix} P & G^\top & A^\top \\ D(\lambda^*)G & D(g(z^*)) & 0 \\ A & 0 & 0 \end{bmatrix} \begin{bmatrix} \tilde z \\ \tilde \lambda \\ \tilde \nu \end{bmatrix} = -\begin{bmatrix} (\partial \mathcal{L}/\partial z^*)^\top \\ 0 \\ 0 \end{bmatrix} $$

直接解需要矩阵求逆，慢。

步骤 2：写出一个等式约束 QP 的 KKT 系统

考虑新构造的一个 QP：

$$ \min_{\tilde z}\ \frac{1}{2}\tilde z^\top P' \tilde z + q'^\top \tilde z \quad \text{s.t.}\ A' \tilde z = b',\ G' \tilde z = c' $$

它对应的 KKT 系统是：

$$ \begin{bmatrix} P' & G'^\top & A'^\top \\ G' & 0 & 0 \\ A' & 0 & 0 \end{bmatrix} \begin{bmatrix} \tilde z \\ \bar \lambda \\ \bar \nu \end{bmatrix} = \begin{bmatrix} -q' \\ c' \\ b' \end{bmatrix} $$

对比两个系统——结构非常像，但中间一行不同：原 KKT 是 $D(\lambda^*)G$ 和 $D(g(z^*))$，新 QP 是 $G'$ 和 $0$。

步骤 3：用 active set 化简中间一行

回忆 KKT 的互补松弛：$\lambda_i^* g_i(z^*) = 0$。

定义有效集：$\mathcal{A} = \{i : g_i(z^*) = 0\}$（约束紧的索引集合）。

对原系统的中间行 $\lambda_i^* G_i \tilde z + g_i(z^*) \tilde \lambda_i = 0$ 分情况讨论：

不在 $\mathcal A$ 中（约束松，$g_i < 0$，$\lambda_i^* = 0$）： $0 + g_i \tilde\lambda_i = 0 \Rightarrow \tilde\lambda_i = 0$ → 这些约束对反向传播没贡献，直接丢弃
在 $\mathcal A$ 中（约束紧，$g_i = 0$，$\lambda_i^* \geq 0$）： $\lambda_i^* G_i \tilde z + 0 = 0 \Rightarrow G_i \tilde z = 0$ → 变成关于 $\tilde z$ 的等式约束

经过这步处理，原 KKT 系统中"复杂的不等式行"被压缩成"针对有效集的等式约束"。

步骤 4：化简后的系统正好是等式约束 QP 的 KKT

去除无效约束、把有效约束转为等式后：

$$ \begin{bmatrix} P & G_+^\top & A^\top \\ G_+ & 0 & 0 \\ A & 0 & 0 \end{bmatrix} \begin{bmatrix} \tilde z \\ \tilde \lambda_+ \\ \tilde \nu \end{bmatrix} = -\begin{bmatrix} (\partial \mathcal{L}/\partial z^*)^\top \\ 0 \\ 0 \end{bmatrix} $$

这正是以下等式约束 QP 的 KKT 系统：

$$ \min_{\tilde z}\ \frac{1}{2}\tilde z^\top P' \tilde z + q'^\top \tilde z \quad \text{s.t.}\ A' \tilde z = 0,\ G_+' \tilde z = 0 $$

其中：

$P' = P(z^*, \nu^*, \lambda^*)$（原问题的拉格朗日 Hessian）
$A' = A(z^*),\ G_+' = G_+(z^*)$（只保留有效集）
$q' = \partial \mathcal{L}/\partial z^*$（来自上游梯度）

这就是定理 1：反向传播的梯度可以通过解这个 QP 得到。

6.4 用 OSQP 高效求解

得到 QP 后，用 OSQP（基于 ADMM）求解。OSQP 每次迭代需要解：

$$ \begin{bmatrix} P + \sigma I & A^\top \\ A & -\text{diag}(\rho)^{-1} \end{bmatrix} \begin{bmatrix} z^{(k+1)} \\ v^{(k+1)} \end{bmatrix} = \begin{bmatrix} \sigma z^{(k)} - q \\ \lambda^{(k)} - \text{diag}(\rho)^{-1} \nu^{(k)} \end{bmatrix} $$

关键：左边的矩阵不依赖迭代步 $k$——只需分解一次，后续每次迭代只是矩阵-向量乘法。这就是 BPQP 速度优势的根源。

6.5 一个简化例子验证

考虑 $\min_z\ \frac{1}{2} z^2 - yz$ s.t. $z \leq 1$，可以直接解出：

$$ z^*(y) = \begin{cases} y & y \leq 1 \\ 1 & y > 1 \end{cases},\quad \frac{\partial z^*}{\partial y} = \begin{cases} 1 & y \leq 1 \\ 0 & y > 1 \end{cases} $$

用 BPQP 流程验证（情形 $y > 1$）：

前向得 $z^* = 1$，$\lambda^* = y - 1 > 0$
有效集 $\mathcal A = \{1\}$，转为等式约束 $\tilde z = 0$
BPQP 构造 QP：$\min_{\tilde z}\ \frac{1}{2}\tilde z^2 + \tilde z$ s.t. $\tilde z = 0$
解：$\tilde z = 0$
链式法则：$\partial \mathcal L/\partial y = (-1) \cdot 0 = 0$ ✓

完美对应。

6.6 完整流程

输入: 原问题最优解 z*, λ*, ν*（前向已得）
      上游梯度 ∂L/∂z*

步骤 1: 检测有效集 A = {i : g_i(z*) = 0}
步骤 2: 利用互补松弛去掉无效约束
步骤 3: 把有效不等式约束转为等式
步骤 4: 构造等式约束 QP（定理 1）
步骤 5: 用 OSQP 解这个 QP
步骤 6: 链式法则得到 ∂L/∂y

输出: ∂L/∂y

七、实验与回顾

7.1 实验一：模拟大规模优化

随机生成 LP、QP、SOCP 三类问题，对比 BPQP 与 CVXPY、qpth/OptNet、Alt-Diff、JAXOpt。

结果（100×20 规模，总时间 = 前向 + 反向）：

问题类型	BPQP 加速比
QP	21.02×
LP	13.54×
SOCP	1.67×

为什么 SOCP 加速比小？因为 CVXPY 处理 SOCP 时不需要做"重构成 cone program"这一步，基线本来就快。

大规模场景（5000×2000）：CVXPY、qpth/OptNet 等方法直接失败或极慢，BPQP 仍能正常运行——这正是它的核心价值。

7.2 实验二：真实投资组合优化

回到开头的金融场景：500 只股票的端到端 MVO。

方法	年化收益	Sharpe	训练时间/epoch
两阶段（先预测后优化）	9.28%	0.65	0.11 min
qpth/OptNet（端到端）	16.54%	1.25	21.2 min
BPQP（端到端）	17.67%	1.28	7.7 min

两个核心结论：

端到端确实更好：Sharpe 从 0.65 提升到 1.28，几乎翻倍
BPQP 比 OptNet 快 2.75×，且决策质量略好

7.3 整体回顾

让我们用一张图总结整篇论文：

问题：可微凸优化层反向传播太慢
   │
   ▼
原因：直接求 KKT 矩阵的逆 O(N³)
   │
   ▼
BPQP 洞察：KKT 系统 ⟺ 等式约束 QP（定理 1，依赖 active set）
   │
   ▼
求解工具：OSQP（基于 ADMM）
   │   - 矩阵分解只做一次
   │   - 利用稀疏性
   │   - 可以并行
   ▼
效果：QP 加速 21×，LP 加速 13×，SOCP 加速 1.67×
   │
   ▼
真实价值：让大规模端到端凸优化训练真正可行
         （投资组合 Sharpe 0.65 → 1.28）

7.4 论文贡献分层

理论贡献：定理 1 给出了"可微凸优化层反向传播 = 解一个等式约束 QP"的等价性。

算法贡献：基于定理 1 构造了一个通用的反向传播流程，前向后向解耦，可灵活组合任意求解器。

工程贡献：开源实现集成进 Microsoft Qlib，金融场景可直接使用。

7.5 BPQP 的位置

显式展开法（OptNet 早期、Alt-Diff）
    ↓ 不展开迭代过程
隐式微分法
    ├── 特化方法（OptNet 内点版、qpth）：仅 QP，紧耦合
    ├── 通用方法（CvxpyLayer、Diffcp）：通用但慢
    └── BPQP：通用 + 快  ←── 同时做到这两点
        关键：把 KKT 求逆 → QP 求解

八、写在最后

读完这篇论文，我有几点感受：

第一，问题的转化是核心智慧。“KKT 求逆"和"求解 QP"看似是两个不同的问题，但在适当的视角下它们等价。这种"换个角度看问题"的能力，往往比新算法本身更有价值。

第二，前置知识的重要性。要理解 BPQP，需要凸优化、KKT、隐函数定理、ADMM 等多个工具的协同。这也是为什么这种"机器学习 + 优化"的交叉论文读起来需要更多背景。对算法工程师来说，花点时间补一补凸优化基础是非常值得的——它会出现在很多看似不相关的地方（SVM、控制、运筹、金融建模、可微编程）。

第三，端到端学习并不是万能的，但当任务本身就涉及"在约束下做最优决策"时（投资、调度、规划、控制），把优化问题嵌入网络架构是非常自然且强大的做法——前提是优化层得足够高效，不能成为训练瓶颈。BPQP 正是在做这件事。

如果你也在做需要可微凸优化的工作，强烈推荐试试 microsoft/qlib 中的 BPQP 实现。

参考资料

原论文：BPQP: A Differentiable Convex Optimization Framework for Efficient End-to-End Learning (NeurIPS 2024)
OSQP：https://osqp.org/
CVXPY：https://www.cvxpy.org/
OptNet 论文：Differentiable Optimization as a Layer in Neural Networks (ICML 2017)
Boyd & Vandenberghe, Convex Optimization（凸优化经典教材，免费在线）
Markowitz, “Portfolio Selection” (1952)：MVO 的开山之作

一、背景：金融中的一个真实难题#

投资组合优化#

为什么是 MVO，而不是直接最大化收益？#

真正的问题：$\mu$ 怎么来？#

两阶段方法的致命缺陷#

端到端学习#

二、抽象成数学问题：什么是可微优化层#

普通神经网络层#

可微优化层#

为什么不直接让网络输出 $w$？#

前向 vs 反向#

三、前置知识（一）：KKT 与隐函数定理#

3.1 从无约束到带约束：拉格朗日的智慧#

无约束情况：导数 = 0#

加入等式约束：直接求导失效#

拉格朗日的天才想法#

3.2 KKT 条件：处理不等式约束#

一个具体例子#

互补松弛与 active set#

3.3 KKT 条件的本质#

3.4 隐函数定理：从隐式关系求导#

显式 vs 隐式#

关键想法：对方程两边求全导#

用单位圆例子验证#

多元情形#

3.5 两者结合：可微优化层的求导公式#

四、现有方案与难点#

方案一：显式展开法（Explicit Unrolling）#

方案二：隐式微分法（Implicit Differentiation）#

难点总结#

五、前置知识（二）：凸优化与求解方法#

5.1 什么是凸优化？#

5.2 凸优化的层级#

LP（线性规划）#

QP（二次规划）#

SOCP（二阶锥规划）#

三者比较#

5.3 求解方法（一）：内点法#

核心思想：障碍函数#

路径跟踪#

牛顿步的代价#

优缺点#

5.4 求解方法（二）：一阶法 / ADMM#

核心思想：拆分 + 交替#

为什么 ADMM 适合 QP？#