用神经网络生成投影矩阵，快速求解复杂优化问题
Data-driven Projection Generation for Efficiently Solving Heterogeneous Quadratic Programming Problems
- 用图神经网络为每个优化问题定制投影，减少变量数
- 新方法在未见问题上仍能快速生成高质量可行解
- 适合需要实时求解大规模优化的工程应用
我们提出一种数据驱动框架，通过实例特定的投影降低高维二次规划（QP）问题的变量数量，从而高效求解。基于图神经网络设计的模型可为每个QP实例生成定制化投影，使我们在未见过的问题上也能获得高质量解。模型在异构QP数据集上训练，目标是最小化投影解的期望目标值。该过程被建模为双层优化：内层使用QP求解器在给定投影下求解，外层更新模型参数。我们开发了高效算法，在不反向传播通过求解器的前提下计算参数梯度。理论分析证明了神经网络生成的投影矩阵具备泛化能力。实验表明，该方法在显著降低计算时间的同时，产生高质量可行解，优于现有方法。
原文摘要 · Abstract (English)
We propose a data-driven framework for efficiently solving quadratic programming (QP) problems by reducing the number of variables in high-dimensional QPs using instance-specific projection. A graph neural network-based model is designed to generate projections tailored to each QP instance, enabling us to produce high-quality solutions even for previously unseen problems. The model is trained on heterogeneous QPs to minimize the expected objective value evaluated on the projected solutions. This is formulated as a bilevel optimization problem; the inner optimization solves the QP under a given projection using a QP solver, while the outer optimization updates the model parameters. We develop an efficient algorithm to solve this bilevel optimization problem, which computes parameter gradients without backpropagating through the solver. We provide a theoretical analysis of the generalization ability of solving QPs with projection matrices generated by neural networks. Experimental results demonstrate that our method produces high-quality feasible solutions with reduced computation time, outperforming existing methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。