用深度学习加速大规模二次规划求解,兼具速度与可靠性。
Deep Distributed Optimization for Large-Scale Quadratic Programming
- 将分裂算子法与分布式共识结合,设计可保证收敛的分布式求解器。
- 训练小规模问题后可直接求解超大规模问题(5万变量、15万约束)。
- 相比传统方法提速数十倍,且理论保障解的质量,适合工业级优化场景。
二次规划(QP)是优化领域的核心基础,广泛应用于各类现代系统,也是更复杂算法的基础。随着应用规模与复杂度不断增长,高效可靠的QP求解算法愈发重要。本文提出一种基于深度学习的分布式优化架构,用于解决大规模QP问题。首先,将先进的分裂算子二次规划(OSQP)方法与共识机制结合,构建适用于网络结构问题的分布式求解器DistributedQP,具备最优性收敛保证。随后,将该优化器展开为深度学习框架,形成DeepDistributedQP,通过学习策略在有限迭代内快速逼近目标精度。该方法基于可能近似正确(PAC-Bayes)理论,提供对未见问题期望最优性差距的泛化界。所提框架及其集中式版本DeepQP,在随机生成问题、最优控制、线性回归、运输网络等任务中显著优于标准优化方法。尤其值得注意的是,DeepDistributedQP在小规模问题上训练后,能有效扩展至大规模问题(最高达50,000变量、150,000约束),且相比OSQP实现数量级的壁钟时间提升。同时,其可证明的性能保证确保了比传统求解器更高的解质量。
原文摘要 · Abstract (English)
Quadratic programming (QP) forms a crucial foundation in optimization, encompassing a broad spectrum of domains and serving as the basis for more advanced algorithms. Consequently, as the scale and complexity of modern applications continue to grow, the development of efficient and reliable QP algorithms is becoming increasingly vital. In this context, this paper introduces a novel deep learning-aided distributed optimization architecture designed for tackling large-scale QP problems. First, we combine the state-of-the-art Operator Splitting QP (OSQP) method with a consensus approach to derive DistributedQP, a new method tailored for network-structured problems, with convergence guarantees to optimality. Subsequently, we unfold this optimizer into a deep learning framework, leading to DeepDistributedQP, which leverages learned policies to accelerate reaching to desired accuracy within a restricted amount of iterations. Our approach is also theoretically grounded through Probably Approximately Correct (PAC)-Bayes theory, providing generalization bounds on the expected optimality gap for unseen problems. The proposed framework, as well as its centralized version DeepQP, significantly outperform their standard optimization counterparts on a variety of tasks such as randomly generated problems, optimal control, linear regression, transportation networks and others. Notably, DeepDistributedQP demonstrates strong generalization by training on small problems and scaling to solve much larger ones (up to 50K variables and 150K constraints) using the same policy. Moreover, it achieves orders-of-magnitude improvements in wall-clock time compared to OSQP. The certifiable performance guarantees of our approach are also demonstrated, ensuring higher-quality solutions over traditional optimizers.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。