Data-driven Projection Generation for Efficiently Solving Heterogeneous Quadratic Programming Problems
This work addresses computational efficiency for heterogeneous QP problems, which is incremental as it builds on existing QP solving methods with a novel projection approach.
The paper tackles the problem of efficiently solving high-dimensional quadratic programming (QP) problems by proposing a data-driven framework that uses a graph neural network to generate instance-specific projections, reducing variable count and achieving high-quality solutions with reduced computation time, as demonstrated in experiments.
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.