A first order method for linear programming parameterized by circuit imbalance

Area of Science:

• Optimization Theory
• Computational Mathematics
• Operations Research

Background:

• First-order methods are widely used for solving large-scale Linear Programming (LP) problems.
• Existing theoretical analyses show linear convergence rates for these methods, but these rates depend on the Hoffman constant, which can be problematic.
• There is a need for LP algorithms with stronger convergence guarantees and better performance on specific matrix classes.

Purpose of the Study:

• To develop a new first-order approach for Linear Programming (LP) optimization.
• To establish stronger theoretical convergence guarantees for LP algorithms.
• To improve LP solver performance, particularly for matrices like totally unimodular ones.

Main Methods:

• A novel first-order LP optimization approach is introduced.
• The convergence rate is analyzed based on the circuit imbalance measure and logarithmic dependence on problem vectors.
• The method utilizes a repeated application of a fast gradient method within a framework that fixes variables to the boundary, inspired by Tardos's method.

Main Results:

• The proposed method exhibits a convergence rate that depends polynomially on the circuit imbalance measure and logarithmically on the right-hand side, capacity, and cost vectors.
• This leads to significantly stronger convergence guarantees compared to existing methods.
• For totally unimodular matrices, the approach yields polynomial-time algorithms, outperforming primal-dual methods for this class.

Conclusions:

• The new first-order LP optimization method offers enhanced theoretical convergence guarantees.
• The approach demonstrates particular effectiveness for specific classes of matrices, such as totally unimodular matrices.
• This work advances the theoretical understanding and practical potential of first-order methods in Linear Programming.