Accelerating Restarted PDHCG Using Numerical Linear Algebra Techniques

<div class="flex flex-col text-sm pb-25"> <section class="text-token-text-primary w-full focus:outline-none [--shadow-height:45px] has-data-writing-block:pointer-events-none has-data-writing-block:-mt-(--shadow-height) has-data-writing-block:pt-(--shadow-height) [&amp;:has([data-writing-block])&gt;*]: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"> <div class="text-base my-auto mx-auto pb-10 [--thread-content-margin:var(--thread-content-margin-xs,calc(var(--spacing)*4))] @w-sm/main:[--thread-content-margin:var(--thread-content-margin-sm,calc(var(--spacing)*6))] @w-lg/main:[--thread-content-margin:var(--thread-content-margin-lg,calc(var(--spacing)*16))] px-(--thread-content-margin)"> <div class="[--thread-content-max-width:40rem] @w-lg/main:[--thread-content-max-width:48rem] mx-auto max-w-(--thread-content-max-width) flex-1 group/turn-messages focus-visible:outline-hidden relative flex w-full min-w-0 flex-col agent-turn"> <div class="flex max-w-full flex-col gap-4 grow"> <div class="min-h-8 text-message relative flex w-full flex-col items-end gap-2 text-start break-words whitespace-normal outline-none keyboard-focused:focus-ring [.text-message+&amp;]:mt-1" dir="auto" tabindex="0" data-message-author-role="assistant" data-message-id="3f3d7b9a-dad5-449d-b9fa-03954c024de0" data-message-model-slug="gpt-5-3" data-turn-start-message="true"> <div class="flex w-full flex-col gap-1 empty:hidden"> <div class="markdown prose dark:prose-invert w-full wrap-break-word dark markdown-new-styling">&nbsp;</div> </div> </div> </div> <div class="mt-3 w-full empty:hidden"> <div class="text-center"> <div class="flex flex-col text-sm pb-25"> <section class="text-token-text-primary w-full focus:outline-none [--shadow-height:45px] has-data-writing-block:pointer-events-none has-data-writing-block:-mt-(--shadow-height) has-data-writing-block:pt-(--shadow-height) [&amp;:has([data-writing-block])&gt;*]: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"> <div class="text-base my-auto mx-auto pb-10 [--thread-content-margin:var(--thread-content-margin-xs,calc(var(--spacing)*4))] @w-sm/main:[--thread-content-margin:var(--thread-content-margin-sm,calc(var(--spacing)*6))] @w-lg/main:[--thread-content-margin:var(--thread-content-margin-lg,calc(var(--spacing)*16))] px-(--thread-content-margin)"> <div class="[--thread-content-max-width:40rem] @w-lg/main:[--thread-content-max-width:48rem] mx-auto max-w-(--thread-content-max-width) flex-1 group/turn-messages focus-visible:outline-hidden relative flex w-full min-w-0 flex-col agent-turn"> <div class="flex max-w-full flex-col gap-4 grow"> <div class="min-h-8 text-message relative flex w-full flex-col items-end gap-2 text-start break-words whitespace-normal outline-none keyboard-focused:focus-ring [.text-message+&amp;]:mt-1" dir="auto" tabindex="0" data-message-author-role="assistant" data-message-id="3f3d7b9a-dad5-449d-b9fa-03954c024de0" data-message-model-slug="gpt-5-3" data-turn-start-message="true"> <div class="flex w-full flex-col gap-1 empty:hidden"> <div class="markdown prose dark:prose-invert w-full wrap-break-word dark markdown-new-styling"> <p data-start="90" data-end="439">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&ouml;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. </div> </div> </div> </div> </div> </div> </section> </div> </div> </div> </div> </div> </section> </div>