让任意二次规划求解器可微,支持神经网络与双层优化。
Differentiation Through Black-Box Quadratic Programming Solvers
- 基于约束活跃集重构线性系统,实现求解与求导解耦。
- 支持15个以上主流求解器,计算开销极低。
- 适合需要可微优化的深度学习与复杂优化任务。
可微优化受到广泛关注,尤其在二次规划(QP)领域。现有方法通常依赖特定集成求解器,限制了其应用范围,难以用于神经网络架构或双层优化,且求解器选择受限。为此,我们提出dQP——一种模块化、求解器无关的即插即用式可微框架,适用于几乎所有QP求解器。核心洞察在于:一旦确定不等式约束的活跃集,解及其梯度均可通过共享同一矩阵的简化线性系统表示,从而完全解耦求解与求导过程。基于此,我们提供轻量级开源实现(https://github.com/cwmagoon/dQP),无缝集成超过15个先进求解器。全面基准测试表明,dQP具备强鲁棒性与可扩展性,尤其在大规模稀疏问题上表现突出。
原文摘要 · Abstract (English)
Differentiable optimization has attracted significant research interest, particularly for quadratic programming (QP). Existing approaches for differentiating the solution of a QP with respect to its defining parameters often rely on specific integrated solvers. This integration limits their applicability, including their use in neural network architectures and bi-level optimization tasks, restricting users to a narrow selection of solver choices. To address this limitation, we introduce dQP, a modular and solver-agnostic framework for plug-and-play differentiation of virtually any QP solver. A key insight we leverage to achieve modularity is that, once the active set of inequality constraints is known, both the solution and its derivative can be expressed using simplified linear systems that share the same matrix. This formulation fully decouples the computation of the QP solution from its differentiation. Building on this result, we provide a minimal-overhead, open-source implementation ( https://github.com/cwmagoon/dQP ) that seamlessly integrates with over 15 state-of-the-art solvers. Comprehensive benchmark experiments demonstrate dQP's robustness and scalability, particularly highlighting its advantages in large-scale sparse problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。