Accelerating Restarted PDHCG Using Numerical Linear Algebra Techniques

*]:pointer-events-auto scroll-mt-[calc(var(--header-height)+min(200px,max(70px,20svh)))]" dir="auto" data-turn-id="request-WEB:c2988fde-d775-491e-814c-57ea702469ee-1" data-testid="conversation-turn-4" data-scroll-anchor="true" data-turn="assistant">   *]:pointer-events-auto scroll-mt-[calc(var(--header-height)+min(200px,max(70px,20svh)))]" dir="auto" data-turn-id="request-WEB:c2988fde-d775-491e-814c-57ea702469ee-1" data-testid="conversation-turn-4" data-scroll-anchor="true" data-turn="assistant"> The restarted Primal-Dual Hybrid Conjugate Gradient (PDHCG) method is a recent first-order algorithm for solving large convex quadratic programs that combines primal-dual updates with inexact Conjugate Gradient (CG) steps and restarts to improve convergence. Most of the runtime arises from repeatedly solving linear systems during the primal update, making this step the primary computational bottleneck. This project studies three approaches for addressing this cost: the standard PDHCG method using CG, a direct method based on exact eigenvalue decomposition, and a preconditioned CG method using a Nyström-based preconditioner. Our results show that the exact eigendecomposition approach can substantially reduce runtime by eliminating the CG bottleneck, but it becomes impractical in very high dimensions due to the cost of computing the full decomposition. The most effective practical approach was preconditioned CG, which significantly improved efficiency when the eigenvalues exhibited favorable decay and an appropriate rank parameter was chosen. We also extend this study to a real-world portfolio optimization problem, further illustrating when these approaches are most effective.