SCQPTH: an efficient differentiable splitting method for convex quadratic programming

• URL: http://arxiv.org/abs/2308.08232v1
• Date: Wed, 16 Aug 2023 09:06:54 GMT
• Title: SCQPTH: an efficient differentiable splitting method for convex quadratic programming
• Authors: Andrew Butler
• Abstract summary: SCQPTH is a differentiable first-order splitting method for convex quadratic programs. The SCQPTH software is made available as an open-source python package. For large scale QPs, SCQPTH can provide a $1times - 10times$ improvement in computational efficiency.
• Score: 1.3597551064547502
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present SCQPTH: a differentiable first-order splitting method for convex quadratic programs. The SCQPTH framework is based on the alternating direction method of multipliers (ADMM) and the software implementation is motivated by the state-of-the art solver OSQP: an operating splitting solver for convex quadratic programs (QPs). The SCQPTH software is made available as an open-source python package and contains many similar features including efficient reuse of matrix factorizations, infeasibility detection, automatic scaling and parameter selection. The forward pass algorithm performs operator splitting in the dimension of the original problem space and is therefore suitable for large scale QPs with $100-1000$ decision variables and thousands of constraints. Backpropagation is performed by implicit differentiation of the ADMM fixed-point mapping. Experiments demonstrate that for large scale QPs, SCQPTH can provide a $1\times - 10\times$ improvement in computational efficiency in comparison to existing differentiable QP solvers.

Related papers

• Covariance-Aware Transformers for Quadratic Programming and Decision Making [25.76921238593292]
  We show that the linear attention mechanism can provably solve unconstrained QPs by tokenizing the matrix variables.<n>We introduce Time2Decide: a generic method that enhances a time series foundation model.<n>We find that Time2Decide uniformly outperforms the base TSFM model for the classical portfolio optimization problem.
  arXiv  Detail & Related papers  (2026-02-16T06:39:24Z)
• A Penalty Approach for Differentiation Through Black-Box Quadratic Programming Solvers [29.582959310549594]
  dXPP is a penalty-based differentiation framework that decouples QP solving from differentiation.<n>We evaluate dXPP on various tasks, including randomly generated QPs, large-scale sparse projection problems, and a real-world portfolio optimization task.
  arXiv  Detail & Related papers  (2026-02-15T14:05:36Z)
• The Geometry of LLM Quantization: GPTQ as Babai's Nearest Plane Algorithm [52.89358421626026]
  GPTQ emerged as one of the standard methods for one-shot post-training quantization at LLM scale.<n>We show that GPTQ is mathematically identical to Babai's nearest plane algorithm for the classical closest vector problem.
  arXiv  Detail & Related papers  (2025-07-24T16:22:18Z)
• Mix-QSAM: Mixed-Precision Quantization of the Segment Anything Model [0.0]
  Mix-QSAM is a mixed-precision Post-Training Quantization (PTQ) framework for the Segment Anything Model (SAM)<n>We introduce a layer-wise importance score, derived using Kullback-Leibler (KL) divergence, to quantify each layer's contribution to the model's output.<n>We also introduce cross-layer synergy, a novel metric based on causal mutual information, to capture dependencies between adjacent layers.
  arXiv  Detail & Related papers  (2025-05-08T00:08:31Z)
• An Efficient Unsupervised Framework for Convex Quadratic Programs via Deep Unrolling [33.4994203652726]
  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.
  arXiv  Detail & Related papers  (2024-12-02T02:22:44Z)
• Extending Quantum Perceptrons: Rydberg Devices, Multi-Class Classification, and Error Tolerance [67.77677387243135]
  Quantum Neuromorphic Computing (QNC) merges quantum computation with neural computation to create scalable, noise-resilient algorithms for quantum machine learning (QML) At the core of QNC is the quantum perceptron (QP), which leverages the analog dynamics of interacting qubits to enable universal quantum computation.
  arXiv  Detail & Related papers  (2024-11-13T23:56:20Z)
• 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)
• Soft Convex Quantization: Revisiting Vector Quantization with Convex Optimization [40.1651740183975]
  We propose Soft Convex Quantization (SCQ) as a direct substitute for Vector Quantization (VQ) SCQ works like a differentiable convex optimization (DCO) layer. We demonstrate its efficacy on the CIFAR-10, GTSRB and LSUN datasets.
  arXiv  Detail & Related papers  (2023-10-04T17:45:14Z)
• Numerical Methods for Convex Multistage Stochastic Optimization [86.45244607927732]
  We focus on optimisation programming (SP), Optimal Control (SOC) and Decision Processes (MDP) Recent progress in solving convex multistage Markov problems is based on cutting planes approximations of the cost-to-go functions of dynamic programming equations. Cutting plane type methods can handle multistage problems with a large number of stages, but a relatively smaller number of state (decision) variables.
  arXiv  Detail & Related papers  (2023-03-28T01:30:40Z)
• Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
  This paper develops a class of low-complexity device scheduling algorithms for over-the-air learning via the method of federated learning. Compared to the state-of-the-art proposed scheme, the proposed scheme poses a drastically lower efficiency system. The efficiency of the proposed scheme is confirmed via experiments on the CIFAR dataset.
  arXiv  Detail & Related papers  (2022-06-14T08:14:14Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  We consider online statistical inference of constrained nonlinear optimization problems. We apply the Sequential Quadratic Programming (StoSQP) method to solve these problems.
  arXiv  Detail & Related papers  (2022-05-27T00:34:03Z)
• Fast Differentiable Matrix Square Root and Inverse Square Root [65.67315418971688]
  We propose two more efficient variants to compute the differentiable matrix square root and the inverse square root. For the forward propagation, one method is to use Matrix Taylor Polynomial (MTP), and the other method is to use Matrix Pad'e Approximants (MPA) A series of numerical tests show that both methods yield considerable speed-up compared with the SVD or the NS iteration.
  arXiv  Detail & Related papers  (2022-01-29T10:00:35Z)
• Convex Optimization for Parameter Synthesis in MDPs [19.808494349302784]
  Probabilistic model checking aims to prove whether a Markov decision process satisfies a temporal logic specification. We develop two approaches that iteratively obtain locally optimal runtime solutions. We demonstrate the approaches on a satellite parameter synthesis problem with hundreds of thousands of parameters and their scalability on a wide range of commonly used benchmarks.
  arXiv  Detail & Related papers  (2021-06-30T21:23:56Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  We consider the problem of learning the optimal policy for infinite-horizon Markov decision processes (MDPs) Some variant of Mirror Descent is proposed for convex programming problems with Lipschitz-continuous functionals. We analyze this algorithm in a general case and obtain an estimate of the convergence rate that does not accumulate errors during the operation of the method.
  arXiv  Detail & Related papers  (2021-02-27T19:28:39Z)
• An Adaptive Stochastic Sequential Quadratic Programming with Differentiable Exact Augmented Lagrangians [17.9230793188835]
  We consider the problem of solving nonlinear optimization programs with objective and deterministic equality. We propose a sequential quadratic programming (SQP) that uses a differentiable exact augmented Lagrangian as the merit function. The proposed algorithm is the first SQP that allows a line search procedure and the first line search procedure.
  arXiv  Detail & Related papers  (2021-02-10T08:40:55Z)
• Efficient algorithms for multivariate shape-constrained convex regression problems [9.281671380673306]
  We prove that the least squares estimator is computable via solving a constrained convex programming (QP) problem with $(n+1)d$ variables and at least $n(n-1)$ linear inequality constraints. For solving the generally very large-scale convex QP, we design two efficient algorithms, one is the symmetric Gauss-Seidel based alternating direction method of multipliers (tt sGS-ADMM), and the other is the proximal augmented Lagrangian method (tt pALM) with the subproblems solved by the semismooth Newton method (t
  arXiv  Detail & Related papers  (2020-02-26T11:18:43Z)

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.