Data-driven Projection Generation for Efficiently Solving Heterogeneous Quadratic Programming Problems
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Bilevel OptimizationGraph Neural NetworkSimilar Papers 제목 키워드 기반
Solving Satisfiability of Polynomial Formulas By Sample-Cell Projection
A new algorithm for deciding the satisfiability of polynomial formulas over the reals is proposed. The key point of the algorithm is a new projection operator, called sample-cell projection operator, custom-made for Conf…
Generalization Bound and Learning Methods for Data-Driven Projections in Linear Programming
How to solve high-dimensional linear programs (LPs) efficiently is a fundamental question. Recently, there has been a surge of interest in reducing LP sizes using random projections, which can accelerate solving LPs inde…
Generalization BoundsAnalog In-Memory Computing Attention Mechanism for Fast and Energy-Efficient Large Language Models
Transformer networks, driven by self-attention, are central to Large Language Models. In generative Transformers, self-attention uses cache memory to store token projections, avoiding recomputation at each time step. How…
GPUQuantized Frank-Wolfe: Faster Optimization, Lower Communication, and Projection Free
How can we efficiently mitigate the overhead of gradient communications in distributed optimization? This problem is at the heart of training scalable machine learning models and has been mainly studied in the unconstrai…
Distributed OptimizationQuantizationStochastic OptimizationTransformation-driven generation of comparable projection images from multimodal anatomical scenes
This work addresses the computational problem of generating reproducible projection-space observations from heterogeneous anatomical scenes whose components may undergo independent spatial transformations. We propose a t…