Rescaled first-order methods for linear programming

Simple first-order methods such as von Neumann's algorithm or Perceptron, both developed in the 50s, can be used to solve linear programming feasibility problems. Their convergence rate depends on the condition measure of the problem at hand, and is typically not polynomial. Recent work of Chubanov (2012, 2014), related to prior work of Betke (2004), has gathered renewed interest in the application of these methods in order to obtain polynomial-time algorithms for linear programming. We present two algorithms that fit into this line of research. Both our algorithms alternate between first-order steps and rescaling steps, so that either the first-order steps lead to a substantial improvement in terms of the convergence, or we can infer that the problem is ill-conditioned and rescale in order to improve the condition measure. In particular, both algorithms are based on the analysis of a geometrical invariants of the LP problem, used as a proxy for the condition measure, that appear to be novel in the literature. 

This is joint work with Daniel Dadush (CWI) and Giacomo Zambelli (LSE).