English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We study the convergence behaviors of primal-dual hybrid gradient (PDHG) forsolving linear programming (LP). PDHG is the base algorithm of a newgeneral-purpose first-order method LP solver, PDLP, which aims to scale up LPby taking advantage of modern computing architectures. Despite its numericalsuccess, the theoretical understanding of PDHG for LP is still very limited;the previous complexity result relies on the global Hoffman constant of the KKTsystem, which is known to be very loose and uninformative. In this work, we aimto develop a fundamental understanding of the convergence behaviors of PDHG forLP and to develop a refined complexity rate that does not rely on the globalHoffman constant. We show that there are two major stages of PDHG for LP: inStage I, PDHG identifies active variables and the length of the first stage isdriven by a certain quantity which measures how close the non-degeneracy partof the LP instance is to degeneracy; in Stage II, PDHG effectively solves ahomogeneous linear inequality system, and the complexity of the second stage isdriven by a well-behaved local sharpness constant of the system. This findingis closely related to the concept of partial smoothness in non-smoothoptimization, and it is the first complexity result of finite timeidentification without the non-degeneracy assumption. An interestingimplication of our results is that degeneracy itself does not slow down theconvergence of PDHG for LP, but near-degeneracy does.

On the Geometry and Refined Rate of Primal-Dual Hybrid Gradient for Linear Programming