Distributed Optimization via Alternating Direction Method of Multipliers

Problems in areas such as machine learning and dynamic optimization on a large network lead to extremely large convex optimization problems, with problem data stored in a decentralized way, and processing elements distributed across a network. We argue that the alternating direction method of multipliers is well suited to such problems. The method was developed in the 1970s, with roots in the 1950s, and is equivalent or closely related to many other algorithms, such as dual decomposition, the method of multipliers, Douglas-Rachford splitting, Spingarn’s method of partial inverses, Dykstra’s alternating projections, Bregman iterative algorithms for ℓ₁ problems, proximal methods, and others. After briefly surveying the theory and history of the algorithm, we discuss applications to statistical and machine learning problems such as the lasso and support vector machines, and to dynamic energy management problems arising in the smart grid.

Speaker Details

Stephen Boyd is the Samsung Professor of Engineering, and Professor of Electrical Engineering in the Information Systems Laboratory at Stanford University, with courtesy appointments in the department of Computer Science and the department of Management Science and Engineering. He received the A.B. degree in Mathematics from Harvard University in 1980, and the Ph.D. in Electrical Engineering and Computer Science from the University of California, Berkeley, in 1985, and then joined the faculty at Stanford. His current research focus is on convex optimization applications in control, signal processing, and circuit design.

Professor Boyd is the author of many research articles and three books: Convex Optimization (with Lieven Vandenberghe, 2004), Linear Matrix Inequalities in System and Control Theory (with L. El Ghaoui, E. Feron, and V. Balakrishnan, 1994), and Linear Controller Design: Limits of Performance (with Craig Barratt, 1991). His group has produced several open source tools, including CVX (with Michael Grant), a widely used parser-solver for convex optimization.

Professor Boyd has received many awards and honors for his research in control systems engineering and optimization, including an ONR Young Investigator Award, a Presidential Young Investigator Award, and the AACC Donald P. Eckman Award, given annually for the greatest contribution to the field of control engineering by someone under the age of 35. In 2013, he received the IEEE Control Systems Award, given for outstanding contributions to control systems engineering, science, or technology. In 2012, Michael Grant and he were given the Mathematical Optimization Society’s Beale-Orchard-Hays Award, given every three years for excellence in computational mathematical programming. He is a Fellow of the IEEE, and a Distinguished Lecturer of the IEEE Control Systems Society. He has been invited to deliver more than 60 plenary and keynote lectures at major conferences in control, optimization, and machine learning.