Title: Rescaled coordinate descent methods for Linear Programming
Speaker: Dr. Giacomo Zambelli
Affiliation: Department of Management – London School of Economics and Political Science
Location: SALC 10 Sherfield Building
Time: 4:00pm

Abstract. Simple coordinate descent 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 coordinate descent steps and rescaling steps, so that either the descent step leads 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 invariant of the LP problem, used as a proxy for the condition measure, that appears to be novel in the literature. This is joint work with Daniel Dadush (CWI) and László Végh (LSE)

About the speaker. Dr Zambelli is an Associate Professor (Reader) in the Department of Mathematics at the London School of Economics and Political Science, which he joined in September 2010. Previously he was Assistant Professor at the University of Padova. He completed his PhD in Algorithms, Combinatorics and Optimization at the Tepper School of Business, Carnegie Mellon University. He is a co-recipient of the 2015 INFORMS Lanchester Prize.