An Efficient Unsupervised Framework for Convex Quadratic Programs via Deep Unrolling

• URL: http://arxiv.org/abs/2412.01051v1
• Date: Mon, 02 Dec 2024 02:22:44 GMT
• Title: An Efficient Unsupervised Framework for Convex Quadratic Programs via Deep Unrolling
• Authors: Linxin Yang, Bingheng Li, Tian Ding, Jianghua Wu, Akang Wang, Yuyi Wang, Jiliang Tang, Ruoyu Sun, Xiaodong Luo,
• Abstract summary: We focus on unrolling "PDQP", a PDHG algorithm specialized for convex Quadratic programs (QPs) We propose a neural network model called "PDQP-net" to learn optimal QP solutions. We show that PDQP-net trained in this unsupervised manner can effectively approximate optimal QP solutions.
• Score: 33.4994203652726
• License:
• Abstract: 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.

Related papers

• Deep Distributed Optimization for Large-Scale Quadratic Programming [15.773581194857085]
  This paper introduces a novel deep learning-aided distributed optimization architecture designed for tackling large-scale Quadratic programming (QP) problems. DeepDistributedQP demonstrates strong generalization by training on small problems and scaling to solve much larger ones (up to 50K variables and 150K constraints) using the same policy.
  arXiv  Detail & Related papers  (2024-12-11T09:45:00Z)
• Differentiation Through Black-Box Quadratic Programming Solvers [16.543673072027136]
  We introduce dQP, a modular framework that enables plug-and-play differentiation for any quadratic programming (QP) solver. Our solution is based on the core theoretical insight that knowledge of the active constraint set at the QP optimum allows for explicit differentiation. Our implementation, which will be made publicly available, interfaces with an existing framework that supports over 15 state-of-the-art QP solvers.
  arXiv  Detail & Related papers  (2024-10-08T20:01:39Z)
• NeuralQP: A General Hypergraph-based Optimization Framework for Large-scale QCQPs [8.503330120957052]
  This paper introduces NeuralQP, a general hypergraph-based framework for large-scale Quadratically Constrained Quadratic Programs (QCQPs) We prove that our framework UniEGNN with our hypergraph representation is equivalent to the Interior-Point Method (IPM) for quadratic programming. Experiments on two benchmark problems and large-scale real-world instances from QPLIB demonstrate that NeuralQP outperforms state-of-the-art solvers.
  arXiv  Detail & Related papers  (2024-09-28T10:42:47Z)
• 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)
• Rethinking Model Selection and Decoding for Keyphrase Generation with Pre-trained Sequence-to-Sequence Models [76.52997424694767]
  Keyphrase Generation (KPG) is a longstanding task in NLP with widespread applications. Seq2seq pre-trained language models (PLMs) have ushered in a transformative era for KPG, yielding promising performance improvements. This paper undertakes a systematic analysis of the influence of model selection and decoding strategies on PLM-based KPG.
  arXiv  Detail & Related papers  (2023-10-10T07:34:45Z)
• Differentially Private Deep Q-Learning for Pattern Privacy Preservation in MEC Offloading [76.0572817182483]
  attackers may eavesdrop on the offloading decisions to infer the edge server's (ES's) queue information and users' usage patterns. We propose an offloading strategy which jointly minimizes the latency, ES's energy consumption, and task dropping rate, while preserving pattern privacy (PP) We develop a Differential Privacy Deep Q-learning based Offloading (DP-DQO) algorithm to solve this problem while addressing the PP issue by injecting noise into the generated offloading decisions.
  arXiv  Detail & Related papers  (2023-02-09T12:50:18Z)
• Bridging the gap between QP-based and MPC-based RL [1.90365714903665]
  We approximate the policy and value functions using an optimization problem, taking the form of Quadratic Programs (QPs) A generic unstructured QP offers high flexibility for learning, while a QP having the structure of an MPC scheme promotes the explainability of the resulting policy. We illustrate the workings of our proposed method with the resulting structure using a point-mass task.
  arXiv  Detail & Related papers  (2022-05-18T10:41:18Z)
• Accelerating Quadratic Optimization with Reinforcement Learning [39.64039435793601]
  We show how Reinforcement Learning can learn a policy to tune parameters to accelerate convergence. Our policy, RLQP, significantly outperforms state-of-the-art QP solvers by up to 3x. RLQP generalizes surprisingly well to previously unseen problems with varying dimension and structure from different applications.
  arXiv  Detail & Related papers  (2021-07-22T17:59:10Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network. We design two optimal algorithms that attain these lower bounds. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-08T15:54:44Z)
• 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)
• APQ: Joint Search for Network Architecture, Pruning and Quantization Policy [49.3037538647714]
  We present APQ for efficient deep learning inference on resource-constrained hardware. Unlike previous methods that separately search the neural architecture, pruning policy, and quantization policy, we optimize them in a joint manner. With the same accuracy, APQ reduces the latency/energy by 2x/1.3x over MobileNetV2+HAQ.
  arXiv  Detail & Related papers  (2020-06-15T16:09:17Z)

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.