Sanjay Mehrotra (left), Damek Davis, and Serhat Aybat.
Damek Davis (UCLA) is selected as the winner of the 2014 INFORMS Optimization Society Student Paper Prize for his paper “Convergence rate analysis of several splitting schemes,” arXiv preprint arXiv:1406.4834 (2014), with Wotao Yin.
This paper considers several well-known splitting schemes for monotone inclusion and convex optimization problems. The objective is to analyze their convergence rates, and to provide examples showing the tightness of the results. In particular, Douglas-Rachford (DRS), Peaceman-Rachford (PRS), and Alternating Direction Method of Multipliers (ADMM) iterations are all special cases Krasnosel’skiǐ-Mann (KM) iterations; and it is shown that the sequence of fixed-point residuals (FPR) of the KM iterations of non-expansive operators converges with rate o(1/(k+1)). By providing examples, it is also shown that this rate is optimal, and improves on the known Big-O rate. In the rest of the paper, the derived rate result on the FPR sequence is used to analyze the convergence rate of DRS, PRS and ADMM iterates in objective value. The paper makes a very significant contribution to the theory of optimization by using a rigorous and unified convergence rate analysis of important splitting schemes.
Damek Davis was invited to give a short talk (about 15 minutes) at the INFORMS Annual Meeting. Here is the link to the recording of the talk.
Santanu Dey (chair), Serhat Aybat, Güzin Bayraksan, François Margot