Restarted Nesterov Acceleration for Projection-Based Linear Programming: Convergence Analysis and Dual Warm Starts

摘要: We propose a projection-based first-order framework for large-scale linear pro gramming (LP). For a sufficiently large projection parameter, projecting a point shifted along the negative objective direction onto the feasible set yields an LP optimal solution. We solve the resulting quadratic projection subproblems through a smooth partial dual formulation using restarted Nesterov acceleration, obtaining the RNALP method. Although the dual objective need not be strongly convex, we establish R-linear convergence of its objective gap for the speed restarted variant. To reduce the cost of a single projection with a large parameter, we develop rRNALP, which combines repeated projections with restarted acceler ation in the outer loop. With exact projections, rRNALP terminates finitely at an optimal solution for any fixed positive projection parameter. For inexact projec tions, a uniform primal perturbation estimate shows that geometrically decaying inner feasibility residuals yield R-linear convergence to the LP optimal solution set. We warm-start the inner solves by carrying the final dual iterate from one outer iteration to the next. On most tested instances, dual warm starts reduce the inner iteration count. The inner iterations use matrix–vector multiplications, box projections, and vector operations suited to GPU computation. Numerical experiments on GPU hardware demonstrate substantial objective improvement with small primal feasibility residuals at modest solver cost.