Data-driven Projection Generation for Efficiently Solving Heterogeneous Quadratic Programming Problems

• URL: http://arxiv.org/abs/2510.26061v1
• Date: Thu, 30 Oct 2025 01:32:21 GMT
• Title: Data-driven Projection Generation for Efficiently Solving Heterogeneous Quadratic Programming Problems
• Authors: Tomoharu Iwata, Futoshi Futami,
• Abstract summary: A graph neural network-based model is designed to generate projections tailored to each QP instance.<n>The model is trained on heterogeneous QPs to minimize the expected objective value evaluated on the projected solutions.
• Score: 23.616287934943315
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• QAOA-Predictor: Forecasting Success Probabilities and Minimal Depths for Efficient Fixed-Parameter Optimization [0.9558392439655014]
  We propose a novel approach using a Graph Neural Network (GNN) to predict Quantum Approximate Optimization Algorithm (QAOA) performance.<n>We demonstrate that the GNN accurately predicts QAOA performance within a 10% margin of the true values.
  arXiv  Detail & Related papers  (2026-03-03T13:43:44Z)
• Provably data-driven projection method for quadratic programming [18.20955065779317]
  We analyze the generalization guarantee for the data-driven projection matrix learning for convex quadratic programs (QPs)<n>We demonstrate that the solutions of convex QPs can be localized within a feasible region corresponding to a special active set.<n>We then extend our analysis to other settings, including learning to match the optimal solution and input-aware setting.
  arXiv  Detail & Related papers  (2025-09-03T14:44:25Z)
• Differentiation Through Black-Box Quadratic Programming Solvers [16.543673072027136]
  We introduce dQP, a framework for plug-and-play differentiation of virtually any QP solver.<n>Our key theoretical insight is that the solution and its derivative can each be expressed in terms of closely-related and simple linear systems.<n>Our open-source, minimal-overhead implementation will be made publicly available and seamlessly integrates with more than 15 state-of-the-art solvers.
  arXiv  Detail & Related papers  (2024-10-08T20:01:39Z)
• Self-Supervised Learning of Iterative Solvers for Constrained Optimization [0.0]
  We propose a learning-based iterative solver for constrained optimization. It can obtain very fast and accurate solutions by customizing the solver to a specific parametric optimization problem. A novel loss function based on the Karush-Kuhn-Tucker conditions of optimality is introduced, enabling fully self-supervised training of both neural networks.
  arXiv  Detail & Related papers  (2024-09-12T14:17:23Z)
• Improving the trainability of VQE on NISQ computers for solving portfolio optimization using convex interpolation [8.186804065389007]
  We improve the trainability of variational quantum eigensolver (VQE) by utilizing convexarity to solve portfolio optimization.<n>Based on convex, the location of the ground state can be evaluated by learning the property of a small subset of basis states in the Hilbert space.<n>The successfully implementation of a $40$-qubit experiment using only $10$ superconducting qubits demonstrates the effectiveness of our proposals.
  arXiv  Detail & Related papers  (2024-07-08T03:51:54Z)
• Reducing the Need for Backpropagation and Discovering Better Optima With Explicit Optimizations of Neural Networks [4.807347156077897]
  We propose a computationally efficient alternative for optimizing neural networks. We derive an explicit solution to a simple feed-forward language model. We show that explicit solutions perform near-optimality in experiments.
  arXiv  Detail & Related papers  (2023-11-13T17:38:07Z)
• Pointer Networks with Q-Learning for Combinatorial Optimization [55.2480439325792]
  We introduce the Pointer Q-Network (PQN), a hybrid neural architecture that integrates model-free Q-value policy approximation with Pointer Networks (Ptr-Nets) Our empirical results demonstrate the efficacy of this approach, also testing the model in unstable environments.
  arXiv  Detail & Related papers  (2023-11-05T12:03:58Z)
• A Deep Unrolling Model with Hybrid Optimization Structure for Hyperspectral Image Deconvolution [50.13564338607482]
  We propose a novel optimization framework for the hyperspectral deconvolution problem, called DeepMix.<n>It consists of three distinct modules, namely, a data consistency module, a module that enforces the effect of the handcrafted regularizers, and a denoising module.<n>This work proposes a context aware denoising module designed to sustain the advancements achieved by the cooperative efforts of the other modules.
  arXiv  Detail & Related papers  (2023-06-10T08:25:16Z)
• Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. One typical strategy is algorithm unrolling, which relies on automatic differentiation through the operations of an iterative solver. This paper provides theoretical insights into the backward pass of unrolled optimization, leading to a system for generating efficiently solvable analytical models of backpropagation.
  arXiv  Detail & Related papers  (2023-01-28T01:50:42Z)
• Neural Improvement Heuristics for Graph Combinatorial Optimization Problems [49.85111302670361]
  We introduce a novel Neural Improvement (NI) model capable of handling graph-based problems where information is encoded in the nodes, edges, or both. The presented model serves as a fundamental component for hill-climbing-based algorithms that guide the selection of neighborhood operations for each.
  arXiv  Detail & Related papers  (2022-06-01T10:35:29Z)
• Slowly Varying Regression under Sparsity [5.22980614912553]
  We present the framework of slowly hyper regression under sparsity, allowing regression models to exhibit slow and sparse variations. We suggest a procedure that reformulates as a binary convex algorithm. We show that the resulting model outperforms competing formulations in comparable times across various datasets.
  arXiv  Detail & Related papers  (2021-02-22T04:51:44Z)
• Offline Model-Based Optimization via Normalized Maximum Likelihood Estimation [101.22379613810881]
  We consider data-driven optimization problems where one must maximize a function given only queries at a fixed set of points. This problem setting emerges in many domains where function evaluation is a complex and expensive process. We propose a tractable approximation that allows us to scale our method to high-capacity neural network models.
  arXiv  Detail & Related papers  (2021-02-16T06:04:27Z)
• Logistic Q-Learning [87.00813469969167]
  We propose a new reinforcement learning algorithm derived from a regularized linear-programming formulation of optimal control in MDPs. The main feature of our algorithm is a convex loss function for policy evaluation that serves as a theoretically sound alternative to the widely used squared Bellman error.
  arXiv  Detail & Related papers  (2020-10-21T17:14:31Z)
• Automatically Learning Compact Quality-aware Surrogates for Optimization Problems [55.94450542785096]
  Solving optimization problems with unknown parameters requires learning a predictive model to predict the values of the unknown parameters and then solving the problem using these values. Recent work has shown that including the optimization problem as a layer in a complex training model pipeline results in predictions of iteration of unobserved decision making. We show that we can improve solution quality by learning a low-dimensional surrogate model of a large optimization problem.
  arXiv  Detail & Related papers  (2020-06-18T19:11:54Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications. Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem. In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
  arXiv  Detail & Related papers  (2020-03-11T13:52:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.