Metraipolis › archive › dc_f89856eaaf60
PDNQP: A GPU-based Factorization-free Method for Large-scale Nonconvex Quadratic Programming — arXiv:2609.19557
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.19557
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-10T04:20:49.150Z
- SHA-256 of the archived text
0482d47539b5a6342e807aa694401ab0f3ef50091c77e6bdd8d5110c5575c5b2- Stable URL of this page
https://metraipolis.com/documento/dc_f89856eaaf60
How to cite
PDNQP: A GPU-based Factorization-free Method for Large-scale Nonconvex Quadratic Programming — arXiv:2609.19557 — arXiv (en), https://arxiv.org/abs/2609.19557 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f89856eaaf60 (Metraipolis archive dc_f89856eaaf60, sha256 0482d47539b5a6342e807aa694401ab0f3ef50091c77e6bdd8d5110c5575c5b2)
BibTeX
@misc{dcf89856eaaf60,
title = {PDNQP: A GPU-based Factorization-free Method for Large-scale Nonconvex Quadratic Programming — arXiv:2609.19557},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.19557},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f89856eaaf60; sha256 0482d47539b5a6342e807aa694401ab0f3ef50091c77e6bdd8d5110c5575c5b2},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.19557. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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\times$--$6.0\times$ 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.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-18 in math.OC).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.19557 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-10T04:09:28.163Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).