arXiv:2412.01051math.OCcs.LG2024-12被引 7

用神经网络无监督学习求解凸二次规划,加速优化过程。

An Efficient Unsupervised Framework for Convex Quadratic Programs via Deep Unrolling

  • 将PDHG算法思想融入神经网络,构建可端到端训练的PDQP-net。
  • 无监督训练下,预测解使原对偶间隙缩小,比传统方法快45%。
  • 无需真实解标签,适合大规模或分布外问题的快速求解。

二次规划(QPs)广泛应用于机器学习、金融和控制等领域。近期,基于学习的原始对偶混合梯度(PDHG)方法在处理大规模线性规划方面展现出巨大潜力,但尚未扩展至二次规划。本文聚焦于专用于凸二次规划的PDHG算法——PDQP,并提出一种名为PDQP-net的神经网络模型来学习最优解。理论上证明,多项式规模的PDQP-net可与PDQP算法对齐,返回最优原对偶解对。我们提出一种无监督方法,将KKT条件嵌入损失函数。不同于依赖求解器生成标签的标准学习优化框架,该方法直接通过原对偶间隙评估调整网络权重。此方法有两个优势:一是原对偶间隙作为目标函数,有助于生成更优解;二是无需依赖求解器。实验表明,以PDQP-net预测结果作为初始值,可使原算法在QP实例上提速最高达45%,在分布外实例上提速14%至31%。

原文摘要 · Abstract (English)

Quadratic programs (QPs) arise in various domains such as machine learning, finance, and control. Recently, learning-enhanced primal-dual hybrid gradient (PDHG) methods have shown great potential in addressing large-scale linear programs; however, this approach has not been extended to QPs. In this work, we focus on unrolling "PDQP", a PDHG algorithm specialized for convex QPs. Specifically, we propose a neural network model called "PDQP-net" to learn optimal QP solutions. Theoretically, we demonstrate that a PDQP-net of polynomial size can align with the PDQP algorithm, returning optimal primal-dual solution pairs. We propose an unsupervised method that incorporates KKT conditions into the loss function. Unlike the standard learning-to-optimize framework that requires optimization solutions generated by solvers, our unsupervised method adjusts the network weights directly from the evaluation of the primal-dual gap. This method has two benefits over supervised learning: first, it helps generate better primal-dual gap since the primal-dual gap is in the objective function; second, it does not require solvers. We show that PDQP-net trained in this unsupervised manner can effectively approximate optimal QP solutions. Extensive numerical experiments confirm our findings, indicating that using PDQP-net predictions to warm-start PDQP can achieve up to 45% acceleration on QP instances. Moreover, it achieves 14% to 31% acceleration on out-of-distribution instances.

二次规划无监督学习神经网络优化加速求解

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。