REVIEW 7 cited by
A Practical and Optimal First-Order Method for Large-Scale Convex Quadratic Programming
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
Convex quadratic programming (QP) is an important class of optimization problem with wide applications in practice. The classic QP solvers are based on either simplex or barrier method, both of which suffer from the scalability issue because their computational bottleneck is solving linear equations. In this paper, we design and analyze a first-order method for QP, called restarted accelerated primal-dual hybrid gradient (rAPDHG), whose computational bottleneck is matrix-vector multiplication. We show that rAPDHG has a linear convergence rate to an optimal solution when solving QP, and the obtained linear rate is optimal among a wide class of primal-dual methods. Furthermore, we connect the linear rate with a sharpness constant of the KKT system of QP, which is a standard quantity to measure the hardness of a continuous optimization problem. Numerical experiments demonstrate that both restarts and acceleration can significantly improve the performance of the algorithm. Lastly, we present PDQP.jl, an open-source solver based on rAPDHG that can be run on both GPU and CPU. With a numerical comparison with SCS and OSQP on standard QP benchmark sets and large-scale synthetic QP instances, we demonstrate the effectiveness of rAPDHG for solving QP.
Forward citations
Cited by 7 Pith papers
-
New Understandings and Computation on Augmented Lagrangian Methods for Low-Rank Semidefinite Programming
Augmented Lagrangian subproblems inherit low-rankness, strict complementarity, and quadratic growth from a primal simple SDP, making Burer-Monteiro gradient descent converge linearly.
-
HPR-QP: A dual Halpern Peaceman-Rachford method for solving large-scale convex composite quadratic programming
HPR-QP solves large-scale convex composite quadratic programs with a dual Halpern Peaceman-Rachford iteration on the restricted Wolfe dual, obtaining O(1/k) KKT residual and strong GPU benchmark results.
-
PDHCG: A Scalable First-Order Method for Large-Scale Competitive Market Equilibrium Computation
A restarted primal-dual method with a per-buyer bisection inner solve, run on GPUs, computes Fisher equilibria at ten-million-buyer scale and extends to Arrow-Debreu markets via fixed-point iteration.
-
Scalable First-order Method for Certifying Optimal k-Sparse GLMs
A FISTA-based method with a custom PAVA computes perspective-relaxation dual bounds for k-sparse GLMs in O(p log p) per prox evaluation, enabling larger optimality certificates.
-
Nonconvex Optimization Framework for Group-Sparse Feedback Linear-Quadratic Optimal Control: Penalty Approach
A penalty-based PALM algorithm solves a group-ℓ0 regularized LQ problem and converges to a critical point under explicit parameter conditions.
-
Enhanced Trust Region Sequential Convex Optimization for Multi-Drone Thermal Screening Trajectory Planning in Urban Environments
An enhanced TR-SCO algorithm with adaptive trust-region filtering and higher-order soft trust regions is applied to multi-drone thermal screening, showing improved path length and computation time in two simulated scenarios.
-
An Overview of GPU-based First-Order Methods for Linear Programming and Extensions
A survey of GPU-based first-order LP solvers focusing on cuPDLP, its PDHG core, theory, benchmarks, and extensions to QP, SDP, and conic programming.
Discussion (0). Continue with ORCID to comment.