Speeding up Linear Programming using Randomized Linear Algebra

Abstract

Linear programming (LP) is an extremely useful tool and has been successfully applied to solve various problems in a wide range of areas, including operations research, engineering, economics, or even more abstract mathematical areas such as combinatorics. It is also used in many machine learning applications, such as ${\ell }_1$-regularized SVMs, basis pursuit, nonnegative matrix factorization, etc. Interior Point Methods (IPMs) are one of the most popular methods to solve LPs both in theory and in practice. Their underlying complexity is dominated by the cost of solving a system of linear equations at each iteration. In this paper, we consider \emph{infeasible} IPMs for the special case where the number of variables is much larger than the number of constraints. Using tools from Randomized Linear Algebra, we present a preconditioning technique that, when combined with the Conjugate Gradient iterative solver, provably guarantees that infeasible IPM algorithms (suitably modified to account for the error incurred by the approximate solver), converge to a feasible, approximately optimal solution, without increasing their iteration complexity. Our empirical evaluations verify our theoretical results on both real-world and synthetic data.

References in corpus (8)

• Alternating Direction Algorithms for ${\ell }_1$-Problems in Compressive Sensing
• Factoring nonnegative matrices with linear programs
• Sub-sampled Newton Methods with Non-uniform Sampling
• Solving Linear Programs with Sqrt(rank) Linear System Solves
• Conditional Hardness of Earth Mover Distance
• Path Finding I :Solving Linear Programs with Õ(sqrt(rank)) Linear System Solves
• Solving Tall Dense Linear Programs in Nearly Linear Time
• A Parallelizable Acceleration Framework for Packing Linear Programs

Cited by in corpus (1)

• Binarized Johnson-Lindenstrauss embeddings