HPR-QP: A dual Halpern Peaceman-Rachford method for solving large-scale convex composite quadratic programming
Preprint
Abstract
In this paper, we introduce HPR-QP, a dual Halpern Peaceman-Rachford (HPR) method designed for solving large-scale convex composite quadratic programming. One distinctive feature of HPR-QP is that, instead of working with the primal formulations, it builds on the novel restricted Wolfe dual introduced in recent years. It also leverages the symmetric Gauss-Seidel technique to simplify subproblem updates without introducing auxiliary slack variables that typically lead to slow convergence. By restricting updates to the range space of the Hessian of the quadratic objective function, HPR-QP employs proximal operators of smaller spectral norms to speed up the convergence. Shadow sequences are elaborately constructed to deal with the range space constraints. Additionally, HPR-QP incorporates adaptive restart and penalty parameter update strategies, derived from the HPR method's $O(1/k)$ convergence in terms of the Karush-Kuhn-Tucker residual, to further enhance its performance and robustness. Extensive numerical experiments on benchmark data sets using a GPU demonstrate that our Julia implementation of HPR-QP significantly outperforms state-of-the-art solvers in both speed and scalability.
Keywords
All Related Versions
This publication has 31 references indexed in Scilit:
- A Practical and Optimal First-Order Method for Large-Scale Convex Quadratic ProgrammingMathematical Programming, 2025
- An Accelerated Proximal Alternating Direction Method of Multipliers for Optimal Decentralized Control of Uncertain SystemsJournal of Optimization Theory and Applications, 2024
- Faster first-order primal-dual methods for linear programming using restarts and sharpnessMathematical Programming, 2022
- OSQP: an operator splitting solver for quadratic programsMathematical Programming Computation, 2020
- QSDPNAL: a two-phase augmented Lagrangian method for convex quadratic semidefinite programmingMathematical Programming Computation, 2018
- A block symmetric Gauss–Seidel decomposition theorem for convex composite quadratic programming and its applicationsMathematical Programming, 2018
- Conic Optimization via Operator Splitting and Homogeneous Self-Dual EmbeddingJournal of Optimization Theory and Applications, 2016
- A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensionsMathematical Programming, 2014
- A new bound for the quadratic assignment problem based on convex quadratic programmingMathematical Programming, 2001
- On the Douglas—Rachford splitting method and the proximal point algorithm for maximal monotone operatorsMathematical Programming, 1992