2012 Tucker Prize Citation

The Tucker Prize for an outstanding doctoral thesis has been awarded to Oliver Friedmann, Department of Computer Science, Ludwig-Maximilians-Universität in Munich, Germany, for his thesis: Exponential Lower Bounds for Solving Infinitary Payoff Games and Linear Programs.

One of the most prominent mysteries in Optimization is the question of whether a linear program can be solved in strongly-polynomial time. A strongly polynomial-time method would be polynomial in the dimension and in the number of inequalities only, whereas the complexity of the known weakly-polynomial time algorithms for linear programming, like the ellipsoid method or variants of the interior-point method, also depend on the binary encoding length of the input. The simplex method, though one of the oldest methods for linear programming, still is a candidate for such a strongly polynomial time algorithm. This would require the existence of a pivoting rule that results in a polynomial number of pivot steps. Since the famous Klee-Minty example, many techniques for deriving exponential lower bounds on the number of iterations for particular pivoting rules have been found.

Some very important pivoting rules, however, have resisted a super-polynomial lower-bound proof for a very long time. Among them the Random-Facet pivoting rule and Zadeh's pivoting rule. Random-Facet has been shown to yield sub-exponential running time of the simplex method independently by Kalai as well as by Matousek, Sharir and Welzl.

Zadeh was a postdoc at Stanford in 1980, when he published a technical report with his least-entered rule: enter the improving variable that has been entered least often. In a hand-written letter to Viktor Klee he offered $1000 to the person who either showed this rule to be a polynomial pivoting rule for the simplex method, or provided a counterexample to it being a polynomial method. Consequently, Zadeh's rule is very well known in the linear-programming community.

In his thesis, Oliver Friedmann has shown super-polynomial lower bounds for pivoting rules in a groundbreaking way. The novelty of his approach is to establish a connection from policy iteration for 2-player parity games and Markov decision processes to pivoting in linear programs. In his paper Subexponential lower bounds for randomized pivoting rules for solving linear programs, coauthored with Hansen and Zwick (Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC'11, San Jose, CA, USA, 2011), Friedmann shows a super-polynomial bound on the Random-Facet pivoting rule. This paper was awarded the prestigious STOC best paper award. This line of work, initiated by Friedmann, shows that the standard strategy iteration algorithm for parity games may require an exponential number of iterations. By giving analogous results for Markov decision processes, Friedmann extends super-polynomial lower bounds to pivoting in linear programming.

The thesis of Friedmann lays out this connection of improvement strategies for games and pivoting. Two of the most prominent results are the aforementioned lower bounds for Random-Facet and Zadeh's rule. But, with this new connection, other pivoting rules that resisted super-polynomial lower-bound proofs have also been shown to be non-polynomial, like the Random-Edge rule and, in a recent publication of Friedmann, Cunningham's rule as well.

Oliver Friedmann is 27 years old (at the date of receiving the Tucker Prize). His undergraduate, master's-level and Ph.D. degrees were all undertaken in the Department of Computer Science at the Ludwig-Maximilians-Universität in Munich, and were completed in 2006, 2008 and 2011 respectively. His Ph.D. thesis was completed in only 2.5 years under supervision from Martin Hofmann and Martin Lange.

With his thesis, Friedmann has built bridges between so-far seemingly unrelated fields, enriched optimization with novel ideas and techniques and achieved groundbreaking results that settled many longstanding open problems. This thesis truly deserves to be awarded with the Tucker Prize 2012.

The other two Tucker Prize finalists chosen by this year's Tucker Prize Committee are Amitabh Basu and Guanghui Lan.

Amitabh Basu obtained his undergraduate degree in Computer Science and Engineering from the Indian Institute of Technology, Delhi in 2004, and received an M.S. in Computer Science from Stony Brook University in 2006. In May 2010, he finished a Ph.D. in Algorithms, Combinatorics and Optimization from the Tepper School of Business, Carnegie Mellon University advised by G&eactue;rard Cornuéjols. He is currently a visiting assistant professor in the Department of Mathematics at the University of California, Davis.

The thesis of Basu, entitled Corner Polyhedra and Maximal Lattice-free Convex Sets: A Geometric Approach to Cutting Planes, studies the properties of cutting planes generated from several rows of the simplex tableau, in the context of solving mixed integer linear programming problems. This new research direction is a big departure from earlier investigations in the theory of cutting planes such as the study of mixed integer cuts and split cuts, which can be generated by integrality arguments applied to a single equation.

A very interesting and promising result in the thesis is the comparison of the strength of the new cuts generated from two rows of the simplex tableau to the strength of the old cuts. Basu shows that the new cuts can be arbitrarily stronger. The thesis also revisits the foundations of cutting plane theory, studying links between cutting planes and maximal lattice-free convex sets, and gives a counterexample to a famous conjecture of Gomory and Johnson about the facets of the group polyhedron. An important result about lifting integer variables is also presented in the thesis.

Today, the most successful solvers for integer programming problems use cutting planes generated from one row of the simplex tableau and lifting techniques. The results from Basu's thesis open the way to the next generation of improvements in solvers, based on cutting planes generated from several rows of the simplex tableau.

Guanghui Lan obtained his undergraduate degree in Mechanical Engineering from the Xiangtan University, China, in 1996 and went on to complete two master's degrees, one in Mechanical Engineering at the Shanghai Jiao Tong University, China, 1999, and the other in Industrial Engineering at the University of Louisville, Kentucky, 2004. In January 2009 he completed his Ph.D. in Industrial and Systems Engineering at Georgia Institute of Technology supervised by Arkadi Nemirovski and co-advised by Renato Monteiro and Alexander Shapiro. He is currently an Assistant Professor of Industrial and Systems Engineering at the University of Florida.

Lan's dissertation, entitled Convex Optimization under Inexact First-Order Information, concerns the design and complexity analysis of first-order methods for solving convex optimization problems under a stochastic oracle. This includes several important classes of convex programming problems, such as general non-smooth problems, composite optimization problems whose objective functions are sums of smooth and non-smooth components, and problems whose feasible regions consist of simple compact convex sets intersected with affine manifolds. The novel methods proposed are accompanied by a worst-case iteration-complexity analysis. New complexity results are also given for deterministic methods in the presence of inexact gradients.

The impact of fine-tuned optimal methods for convex optimization on actual computation is prominent and significant. The outstanding contribution of Lan's thesis is an optimal method for stochastic composite optimization which closes the gap between the convergence rate of existing first-order methods and the theoretically optimal rate of convergence. It represents the first universally optimal method which covers smooth, non-smooth and stochastic convex programming as special cases and overcomes the need to handle different classes of convex optimization problems using different (sub)optimal methods. Remarkably, the optimal rate of convergence had not been attained before even for the deterministic case.