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

First-order primal-dual methods are appealing for their low memory overhead,fast iterations, and effective parallelization. However, they are often slow atfinding high accuracy solutions, which creates a barrier to their use intraditional linear programming (LP) applications. This paper exploits thesharpness of primal-dual formulations of LP instances to achieve linearconvergence using restarts in a general setting that applies to ADMM(alternating direction method of multipliers), PDHG (primal-dual hybridgradient method) and EGM (extragradient method). In the special case of PDHG,without restarts we show an iteration count lower bound of $\Omega(\kappa^2\log(1/\epsilon))$, while with restarts we show an iteration count upper boundof $O(\kappa \log(1/\epsilon))$, where $\kappa$ is a condition number and$\epsilon$ is the desired accuracy. Moreover, the upper bound is optimal for awide class of primal-dual methods, and applies to the strictly more generalclass of sharp primal-dual problems. We develop an adaptive restart scheme andverify that restarts significantly improve the ability of PDHG, EGM, and ADMMto find high accuracy solutions to LP problems.

Faster First-Order Primal-Dual Methods for Linear Programming using Restarts and Sharpness