Designing Fast Distributed Iterations via Semidefinite Programming

Speaker: Dr. Stephen Boyd, Stanford University
Abstract: The general setting we consider involves a process, iteration, or method in which the computation or communication at each step is local, determined by a given graph, and involves some parameters or coefficients that affect its convergence speed. Examples include a Markov chain on a graph, where the transition probabilities affect the mixing rate of the chain; distributed averaging, where the local weights affect the global speed of convergence to the average; and distributed weighted gradient methods for resource allocation, where the weights affect the speed of convergence to the optimal allocation. We show how semidefinite programming can be used to choose the coefficients or parameters in these methods to yield fastest (or in some cases, just fast) convergence. We also show how weights suggested by the celebrated Metropolis-Hastings algorithm (for fast convergence in Monte Carlo Markov Chain simulation) transcribe well to other applications, such as distributed averaging.
Biography: Stephen P. Boyd is the Samsung Professor of Engineering, and Professor of Electrical Engineering in the Information Systems Laboratory at Stanford University. His current research focus is on convex optimization applications in control, signal processing, and circuit design. Professor Boyd received an AB degree in Mathematics, summa cum laude, from Harvard University in 1980, and a PhD in EECS from U. C. Berkeley in 1985. In 1985 he joined the faculty of Stanford’s Electrical Engineering Department. He has held visiting Professor positions at Katholieke University (Leuven), McGill University (Montreal), Ecole Polytechnique Federale (Lausanne), Qinghua University (Beijing), Universite Paul Sabatier (Toulouse), Royal Institute of Technology (Stockholm), and Kyoto University. Professor Boyd is the author of many research articles and three books: Linear Controller Design: Limits of Performance (with Craig Barratt, 1991), Linear Matrix Inequalities in System and Control Theory (with L. El Ghaoui, E. Feron, and V. Balakrishnan, 1994), and Convex Optimization (with Lieven Vandenberghe, 2004). 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 an IBM faculty development award. In 1992 he received the AACC Donald P. Eckman Award, which is given annually for the greatest contribution to the field of control engineering by someone under the age of 35. In 1993 he was elected Distinguished Lecturer of the IEEE Control Systems Society, and in 1999, he was elected Fellow of the IEEE, with citation: "For contributions to the design and analysis of control systems using convex optimization based CAD tools." He has been invited to deliver more than 20 plenary and keynote lectures at major conferences in both control and optimization. In addition to teaching large graduate courses on Linear Dynamical Systems, Nonlinear Feedback Systems, and Convex Optimization, Professor Boyd has regularly taught introductory undergraduate Electrical Engineering courses on Circuits, Signals and Systems, Digital Signal Processing, and Automatic Control. In 1994 he received the Perrin Award for Outstanding Undergraduate Teaching in the School of Engineering, and in 1991, an ASSU Graduate Teaching Award. In 2003, he received the AACC Ragazzini Education award, for contributions to control education, with citation: "For excellence in classroom teaching, textbook and monograph preparation, and undergraduate and graduate mentoring of students in the area of systems, control, and optimization."
Presented On: Friday, October 7, 2005
Videotape: <Not available.>