Shiqian Ma

Winner: Shiqian Ma, Columbia University

Paper: Fast Multiple Splitting Algorithms for Convex Optimization

Authors: Donald Goldfarb and Shiqian Ma

The authors provide for the first time optimal complexity bounds for two general classes of K-splitting methods for solving convex optimization problems. They show that the number of iterations to obtain an $\epsilon$-optimal solution is $\cal{O}(1/\epsilon)$ for a standard method, and $\cal{O}(1/\sqrt{\epsilon})$ for an accelerated method. The complexity results are optimal in the sense that they are the best that can be achieved for first-order methods. The authors extend the algorithms to optimization problems involving linear operators such as those that arise in variational formulations of partial differential equations and in optimal control problems. The paper concludes with some impressive computational results showing that the proposed splitting method outperforms MOSEK by an order of magnitude on instances of the Fermat-Weber problem, an important test problem arising in facility location.

The paper combines elegant theory with an effective practical implementation. It establishes new surprising complexity results for a family of classical optimization techniques. The methods and results of this paper are not only significant from a theoretical point of view, but also have tremendous potential for the development of parallel optimization algorithms for emerging multicore architectures.

Selection Committee

Miguel Anjos, Alper Atamturk, Sven Leyffer (chair)