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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Various first order approaches have been proposed in the literature to solveLinear Programming (LP) problems, recently leading to practically efficientsolvers for large-scale LPs. From a theoretical perspective, linear convergencerates have been established for first order LP algorithms, despite the factthat the underlying formulations are not strongly convex. However, theconvergence rate typically depends on the Hoffman constant of a large matrixthat contains the constraint matrix, as well as the right hand side, cost, andcapacity vectors.  We introduce a first order approach for LP optimization with a convergencerate depending polynomially on the circuit imbalance measure, which is ageometric parameter of the constraint matrix, and depending logarithmically onthe right hand side, capacity, and cost vectors. This provides much strongerconvergence guarantees. For example, if the constraint matrix is totallyunimodular, we obtain polynomial-time algorithms, whereas the convergenceguarantees for approaches based on primal-dual formulations may havearbitrarily slow convergence rates for this class. Our approach is based on afast gradient method due to Necoara, Nesterov, and Glineur (Math. Prog. 2019);this algorithm is called repeatedly in a framework that gradually fixesvariables to the boundary. This technique is based on a new approximate versionof Tardos's method, that was used to obtain a strongly polynomial algorithm forcombinatorial LPs (Oper. Res. 1986).

A First Order Method for Linear Programming Parameterized by Circuit Imbalance