Title: Linearly-Convergent Decentralized Algorithms for Multi-Agent Network Optimization
Speaker: Dr. Qing Ling, University of Science and Technology of China
Abstract: In multi-agent optimization, a group of networked agents collaboratively minimize the summation of their local cost functions with respect to a common optimization variable. Its applications include coordination of an aircraft or vehicle network, data processing of a wireless sensor network, spectrum sensing of a cognitive radio network, etc, in which transmitting distributed data to a fusion center is prohibitive and the network relies on collaboration of neighboring agents to fulfill the optimization task. A favorable multi-agent network optimization algorithm requires fast convergence that means low communication cost over the network and simple implementation that means low computation cost on the agents.
This talk discusses (nearly) linear convergence of two decentralized multi-agent network optimization algorithms, the alternating direction method of multipliers (ADMM) and the gradient descent method (GDM). In the existing literature, the convergence rate of the ADMM is unknown and that of the GDM is sublinear. We prove that when the local cost functions are strongly convex and have Lipschitz continuous gradients, the ADMM converges linearly to the optimal solution. The rate of convergence is determined by the properties of the cost functions, the ADMM stepsize, and the network topology. Under the same conditions, we prove that the GDM converges linearly to a neighborhood of the optimal solution. The rate of convergence and the size of the neighborhood are both determined by the properties of the cost functions, the GDM stepsize, and a topology-dependent mixing matrix. The analysis provides guidelines for designing multi-agent network optimization algorithms and tuning algorithm parameters.
Biography: Qing Ling received the B.S. degree in automation and the Ph.D. degree in control theory and control engineering from University of Science and Technology of China, Hefei, China, in 2001 and 2006, respectively. From 2006 to 2009, he was a Post-Doctoral Research Fellow in the Department of Electrical and Computer Engineering, Michigan Technological University, Houghton, Michigan, USA. Since 2009, he has been an Associate Professor in the Department of Automation, University of Science and Technology of China. Now he is a Visiting Scholar in the Department of Electrical and Systems Engineering, University of Pennsylvania, Philadelphia, Pennsylvania, USA. His current research focuses on decentralized optimization of networked multi-agent systems and sparse optimization.