Randomized Algorithms for Linear Programming

Linear Programming (LP), a special case of mathematical programming, finds applications in various fields of study. Classical methods for solving LP such as simplex method or interior point method have proved to be efficient when the problem size is moderate. We aim at proposing new algorithms designed for large-scale LP problems with little growth in time in terms of the number of variables or constraints. Our main technical tools will be based on the recently developed randomized/stochastic algorithms, promoted for great efficiency in large-scale convex optimization. Indeed, LP problem can be written equivalently as a sign-constrained least square problem. And some existing stochastic algorithms can be readily applied to solve such composite convex problem. Further improvement and theoretical analysis are expected to confirm the efficiency of this novel approach.