用惩罚法实现对黑箱QP求解器的高效微分
A Penalty Approach for Differentiation Through Black-Box Quadratic Programming Solvers
- 用惩罚项将QP解映射为平滑近似问题，分离求解与微分步骤
- 后向传播只需解小型线性系统，比传统方法快数倍
- 适用于大规模稀疏投影和实际投资组合优化任务
对二次规划（QP）解的微分是可微优化中的核心问题。现有方法多基于卡鲁什-库恩-塔克（KKT）系统，但在大规模场景下计算成本高且数值稳定性差。为此，本文提出dXPP，一种基于惩罚的微分框架，将QP求解与微分过程解耦。求解阶段（前向）对任意黑箱QP求解器无感；微分阶段（反向）将解映射至平滑近似惩罚问题，并隐式微分，仅需求解一个规模小得多的原始变量线性系统。该方法规避了显式KKT微分的困难，显著提升效率与鲁棒性。我们在随机生成的QP、大规模稀疏投影问题及真实多周期投资组合优化任务上评估dXPP，结果表明其性能优于或媲美基于KKT的方法，在大规模问题上实现显著加速。代码开源：https://github.com/mmmmmmlinghu/dXPP。
原文摘要 · Abstract (English)
Differentiating through the solution of a quadratic program (QP) is a central problem in differentiable optimization. Most existing approaches differentiate through the Karush--Kuhn--Tucker (KKT) system, but their computational cost and numerical robustness can degrade at scale. To address these limitations, we propose dXPP, a penalty-based differentiation framework that decouples QP solving from differentiation. In the solving step (forward pass), dXPP is solver-agnostic and can leverage any black-box QP solver. In the differentiation step (backward pass), we map the solution to a smooth approximate penalty problem and implicitly differentiate through it, requiring only the solution of a much smaller linear system in the primal variables. This approach bypasses the difficulties inherent in explicit KKT differentiation and significantly improves computational efficiency and robustness. We evaluate dXPP on various tasks, including randomly generated QPs, large-scale sparse projection problems, and a real-world multi-period portfolio optimization task. Empirical results demonstrate that dXPP is competitive with KKT-based differentiation methods and achieves substantial speedups on large-scale problems. Our implementation is open source and available at https://github.com/mmmmmmlinghu/dXPP.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。