Robert Freund

Robert Freund is the Theresa Seley Professor in Management Science at the Sloan School of Management at MIT. He received his B.A. in Mathematics from Princeton University and M.S. and Ph.D. degrees in Operations Research at Stanford University. He served a term as Deputy Dean for Faculty at MIT Sloan (2008-11). His main research interests are in continuous optimization and related mathematical systems, plus applications in machine learning and data science. Professor Freund has served as Co-Editor of the journal Mathematical Programming and as Associate Editor of several optimization and operations research journals. He received the Longuet-Higgins Prize in computer vision (2007), and has received numerous teaching and education awards at MIT in conjunction with the MBA course Data, Models, and Decisions. He is the former Co-Director of MIT Operations Research Center, the MIT Program in Computation for Design and Optimization, and the former Chair of the INFORMS Optimization Section.

Title of talk: The Role of Level-Set Geometry on the Performance of PDHG for Conic Convex Optimization

In joint work with Zikai Xiong, we consider solving huge-scale instances of (convex) conic linear optimization problems, at the scale where matrix-factorization-free methods are attractive or necessary. The restarted primal-dual hybrid gradient method (rPDHG)—with heuristic enhancements and GPU implementation—has been very successful in solving these huge-scale LP problems; however, its performance can have substantial variance, and an intuitive understanding of the drivers of its performance has been lacking. We present a new theoretical analysis of rPDHG for general (convex) conic linear optimization and for LP as a special case thereof. We show a relationship between geometric measures of the primal-dual (sub-)level sets and the convergence rate of rPDHG. We then specialize our results to the case of LP with unique optima.  Under unique optima, we present an iteration bound that is “accessible” in the sense that computing the bound is no more difficult than computing the optimal solution itself. This furthermore enables an analysis of the “two-stage performance” of rPDHG: we present a bound on the number of iterations of the first stage (which identifies the optimal basis), and also a bound on the second stage (which computes a nearly-optimal solution). Furthermore, computational tests mostly confirm the tightness of these iteration bounds. We also show a reciprocal relation between the iteration bounds and three equivalent types of condition measures: (i) stability under data perturbation, (ii) proximity to multiple optima, and (iii) the LP sharpness of the instance.