Computational Guarantees for Restarted PDHG for LP based on "Limiting Error Ratios" and LP Sharpness

Understand

In recent years, there has been growing interest in solving linear optimization problems - or more simply "LP" - using first-order methods in order to avoid the costly matrix factorizations of traditional methods for huge-scale LP instances.

• The restarted primal-dual hybrid gradient method (PDHG) - together with some heuristic techniques - has emerged as a powerful tool for solving huge-scale LPs.
• However, the theoretical understanding of the restarted PDHG and the validation of various heuristic implementation techniques are still very limited.
• Existing complexity analyses have relied on the Hoffman constant of the LP KKT system, which is known to be overly conservative, difficult to compute, and fails to offer insight into instance-specific characteristics of the LP problems.