Faster algorithms for linear programming using rank based steps
Faster Linear Programming with $\sqrt{\mathrm{rank}}$ Linear System Solves
Data Structures and Algorithms
Summary
Linear programming is a way to find the best solution given some rules, and solving it usually involves steps called linear system solves. Previous work linked the number of these steps to the number of constraints, but Lee and Sidford showed it actually depends on the problem’s rank, which is often smaller. This paper improves on their method by reducing a big logarithmic factor, making the process faster without needing more guesses or assumptions. The authors also conjecture that even fewer steps might be enough in the future.
What this means in practice
- •For operations research teams: Solve large-scale optimization problems more efficiently by reducing the computational cost of linear system solves.
- •For data engineers: Speed up constrained optimization tasks in data pipelines that rely on linear programming formulations.
Authors
Zhao Song
Abstract
Lee and Sidford [LS19] showed that the linear program $\min\{c^\top x\ :\ A^\top x=b,\ l\leq x\leq u\}$ over $x\in\mathbb{R}^m$, where $A\in\mathbb{R}^{m\times n}$, can be solved to accuracy $ε$ using $O(\sqrt n\log^{13}m\cdot\log(mU/ε))$ solves of linear systems in $A^\top\mathbf DA$ for positive diagonal matrices $\mathbf D$, where $U$ bounds the magnitudes of the input and of the initial point. Theirs is the first such bound governed by $\mathrm{rank}(A)=n$ rather than by the number of constraints $m$. Song [Son19] mentioned that reducing the $\log^{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(\sqrt n\log^{4}m\cdot\log(mU/ε))$ solves of such linear systems, improving the Lee--Sidford bound by a factor of $\log^{9}m$. We conjecture that $O(\sqrt n\log(mU/ε))$ such linear-system solves suffice.