Return to Search Results Print

This paper develops the first accessible iteration bound for the restarted primal-dual hybrid gradient method (rPDHG), a method that has emerged as a particularly successful alternative for solving large-scale linear programs. The bound is expressed in closed form using quantities tied directly to the optimal solution and basis, making it both theoretically rigorous and practically computable. The analysis sheds new light on the method’s two-stage performance, sensitivity to perturbations, and practical heuristics, and is further supported by numerical experiments. This single-authored student paper stands out for its accessible analysis, important results, and current relevance, making it a deserving recipient of this prize.

Print Abstract