University of Minnesota
University Relations
http://www.umn.edu/urelate
612-624-6868
myU OneStop


Go to unit's home.

Home | Seminars and Symposia | Past seminars/symposia: Thursday, January 23, 2014

DTC Seminar Series

Linearly-Convergent Decentralized Algorithms for Multi-Agent Network Optimization

by

Qing Ling
USTC
P.R. China

Thursday, January 23, 2014
3:00 p.m. reception
3:30 p.m. seminar

401/402 Walter Library

Qing Ling

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, and spectrum sensing of a cognitive radio network, 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 which implies low communication cost over the network and simple implementation that translates to low computation cost for the agents.

This talk discusses (nearly) linear convergence of three decentralized multi-agent network optimization algorithms, the alternating direction method of multipliers (ADMM), the gradient descent method (GDM), and the linearized alternating direction method of multipliers (LADMM). In the existing literature, convergence rate of ADMM is unknown and that of the GDM is sublinear. We prove that if the local cost functions are strongly convex and have Lipschitz continuous gradients, the ADMM converges linearly to the optimal solution. Under the same conditions, we prove that the GDM converges linearly to a neighborhood of the optimal solution. We propose a new decentralized algorithm, the LADMM, which combines the merits of ADMM and GDM. LADMM offers the GDM's simple computation and the ADMM's exact linear convergence. The convergence properties of the three algorithms are determined by the condition numbers of the cost functions, the algorithm parameters, as well as the network topology. Our work not only provides guidelines of tuning parameters to achieve better convergence, but also reveals the connections between different decentralized algorithms.

 

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, 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. 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. His current research focuses on decentralized optimization of networked multi-agent systems and sparse optimization.