Faster Linear Programming with sqrtrank Linear System Solves

Zhao Song

In the authors' words

Lee and Sidford [LS19] showed that the linear program $min {c^{⊤} x : A^{⊤} x = b, l \leq x \leq u}$ over $x \in R^{m}$ , where $A \in R^{m \times n}$ , can be solved to accuracy $ϵ$ using $O (n lo g^{13} m \cdot lo g (m U / ϵ))$ solves of linear systems in $A^{⊤} D A$ for positive diagonal matrices $D$ , where $U$ bounds the magnitudes of the input and of the initial point. Theirs is the first such bound governed by $r ank (A) = n$ rather than by the number of constraints $m$ . Song [Son19] mentioned that reducing the $lo g^{13} m$ factor is an interesting future direction. Given an interior point and a finite certified magnitude bound $U$ , we give an algorithm that uses $O (n lo g^{4} m \cdot lo g (m U / ϵ))$ solves of such linear systems, improving the Lee--Sidford bound by a factor of $lo g^{9} m$ . We conjecture that $O (n lo g (m U / ϵ))$ such linear-system solves suffice.

Main resultLimitation the authors admit

Faster Linear Programming with rank​ Linear System Solves

In the authors' words

More on Optimization that day

TR-SSQP: A Trust-Region Method for Constrained Stochastic Optimization under Heavy-Tailed Noise

Disjunctive Submodular Functions: Envelopes and Applications to Inventory and 0-1 Quadratic Optimization

Optimal Prophet Inequalities for Gain from Trade

Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms

Moment Ambiguity and the Limits of Robust Stochastic Optimization

Faster Linear Programming with $r ank$ Linear System Solves