Scaling up and Speeding up Classical Optimization on Modern Computing Architectures

The rapid advancement of modern computing architectures, particularly graphics processing units (GPUs), has fundamentally reshaped the landscape of large-scale computation. While machine learning has successfully leveraged these architectures through highly parallelizable first-order methods, classical optimization, such as linear and quadratic programming, remains largely dominated by CPU-based solvers built on factorization-intensive algorithms. This dissertation aims to bridge this gap by developing scalable, GPU-compatible optimization algorithms that exploit the structural advantages of first-order methods. We begin by proposing cuPDLPx, a GPU-based first-order solver for linear programming built upon the primal-dual hybrid gradient (PDHG) framework. By carefully redesigning both the algorithmic components and implementation strategies to align with GPU architectures, cuPDLPx achieves substantial performance gains on large-scale instances, demonstrating the potential of first-order methods as a viable alternative to traditional solvers. To support and extend these empirical advances, we develop a refined theoretical understanding of PDHG for linear programming. In particular, we uncover a two-stage convergence phenomenon consisting of finite-time identification of active constraints followed by local convergence, providing new insights into the geometric structure and dynamics of PDHG iterates. We further introduce the restarted Halpern PDHG (rHPDHG) method, which incorporates restart and Halpern-type acceleration schemes to achieve improved convergence guarantees. We establish accelerated convergence rates and demonstrate enhanced performance in both optimality convergence and infeasibility detection. Finally, we extend the proposed framework to large-scale convex quadratic programming. We develop a practical and theoretically grounded first-order method based on restarted accelerated PDHG, analyze its convergence behavior through the lens of KKT residuals, and demonstrate its efficiency on standard benchmark datasets.