PDNQP: A GPU-based Factorization-free Method for Large-scale Nonconvex Quadratic Programming
Abstract
Large-scale nonconvex quadratic programming remains challenging because the sparse matrix factorizations used by many existing solvers can incur substantial computational and memory costs and are difficult to parallelize efficiently on GPUs. We present PDNQP, a factorization-free first-order solver for finding stationary points of large-scale nonconvex quadratic programs. The method combines a proximal augmented-Lagrangian framework with restarted accelerated primal--dual hybrid gradient to solve the resulting strongly convex QP subproblems. Its key ingredients are a residual-form reformulation that avoids penalty-dependent normal matrices and preserves a fixed sparse constraint operator across outer iterations, and an adaptive strategy that coordinates inner-solve accuracy with outer progress. The resulting computations rely on sparse matrix--vector products, projections, and vector operations suited to GPU execution. On $107$ nonconvex CUTEst instances, PDNQP achieves the highest success rate among the tested solvers at both accuracy levels. With absolute and relative tolerances set to 10−4, it achieves speedups of 2.6×--6.0× in shifted geometric mean runtime; at 10−6, its aggregate runtime remains comparable to that of the fastest tested solvers. On $30$ large-scale synthetic nonconvex QPs with approximately one million variables each, PDNQP returns points satisfying the common external termination criteria on $27$ instances, while none of the other tested solvers succeeds under the same experimental protocol.
Related
- A method for global minimization of nonconvex quadratic functions
- A sequential quadratic programming method for optimization with expectation objective functions, deterministic inequality constraints and robust subproblems
- A One-Factorization Predictor-Corrector Long-Step Arc-Search Method and a Curvature-Amplified Variant for Semidefinite Programming with a Homogeneous Self-Dual Embedding
- Dynamical Systems and Nonconvex Quadratic Programs
- Spectral Deflation for Factorization-Free Matrix Filtering in Muon and Semidefinite Programming
BibTeX
@misc{chen2026pdnqp,
title = {{PDNQP: A GPU-based Factorization-free Method for Large-scale Nonconvex Quadratic Programming}},
author = {Zixi Chen and Haihao Lu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.19557},
eprint = {2609.19557},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.19557},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - PDNQP: A GPU-based Factorization-free Method for Large-scale Nonconvex Quadratic Programming
AU - Zixi Chen
AU - Haihao Lu
PY - 2026
DA - 2026/09/17
PB - arXiv
DO - 10.48550/arxiv.2609.19557
UR - https://arxiv.org/abs/2609.19557
AB - Large-scale nonconvex quadratic programming remains challenging because the sparse matrix factorizations used by many existing solvers can incur substantial computational and memory costs and are difficult to parallelize efficiently on GPUs. We present PDNQP, a factorization-free first-order solver for finding stationary points of large-scale nonconvex quadratic programs. The method combines a proximal augmented-Lagrangian framework with restarted accelerated primal--dual hybrid gradient to solve the resulting strongly convex QP subproblems. Its key ingredients are a residual-form reformulation that avoids penalty-dependent normal matrices and preserves a fixed sparse constraint operator across outer iterations, and an adaptive strategy that coordinates inner-solve accuracy with outer progress. The resulting computations rely on sparse matrix--vector products, projections, and vector operations suited to GPU execution. On $107$ nonconvex CUTEst instances, PDNQP achieves the highest success rate among the tested solvers at both accuracy levels. With absolute and relative tolerances set to 10^−4, it achieves speedups of 2.6×--6.0× in shifted geometric mean runtime; at 10^−6, its aggregate runtime remains comparable to that of the fastest tested solvers. On $30$ large-scale synthetic nonconvex QPs with approximately one million variables each, PDNQP returns points satisfying the common external termination criteria on $27$ instances, while none of the other tested solvers succeeds under the same experimental protocol.
ER -