Abstract
In this paper, we develop a regularized Fenchel dual gradient method (RFDGM), which allows nodes in a time-varying undirected network to find a common decision, in a fully distributed fashion, for minimizing the sum of their local objective functions subject to their local constraints. Different from most existing distributed optimization algorithms that also cope with time-varying networks, RFDGM is able to handle problems with general convex objective functions and distinct local constraints, and still has non-asymptotic convergence results. Specifically, under a standard network connectivity condition, we show that RFDGM is guaranteed to reach ϵ-accuracy in both optimality and feasibility within iterations. Such iteration complexity can be improved to if the local objective functions are strongly convex but not necessarily differentiable. Finally, simulation results demonstrate the competence of RFDGM in practice.
Disclosure statement
No potential conflict of interest was reported by the author(s).
Notes
1 We may simply choose to be n.
2 The comparison excludes the existing algorithms that require identical or more restricted network assumptions than Assumption 2.1.
Additional information
Funding
Notes on contributors
Xuyang Wu
Xuyang Wu received the B.S. degree in Information and Computing Science from Northwestern Polytechnical University, Xi'an, China in 2015, and the Ph.D. degree from the School of Information Science and Technology at ShanghaiTech University, Shanghai, China in 2020. He is currently a Postdoctoral Researcher in the Division of Decision and Control Systems at KTH Royal Institute of Technology, Stockholm, Sweden. His research interests include distributed/parallel optimization and machine learning.
Kin Cheong Sou
Kin Cheong Sou received a Ph.D. degree in Electrical Engineering and Computer Science at Massachusetts Institute of Technology in 2008. From 2008 to 2010 he was a Postdoctoral Researcher at Lund University, Lund, Sweden. From 2010 to 2012 he was a Postdoctoral Researcher at KTH Royal Institute of Technology, Stockholm, Sweden. Between 2013 and 2016 he was an Assistant Professor with the department of Mathematical Sciences, Chalmers University of Technology and the University of Gothenburg, Sweden. He is currently an Associate Professor with the department of Electrical Engineering at the National Sun Yat-sen University in Taiwan. His research interests include optimization and system analysis with power systems applications.
Jie Lu
Jie Lu received the B.S. degree in Information Engineering from Shanghai Jiao Tong University, China in 2007, and the Ph.D. degree in Electrical and Computer Engineering from the University of Oklahoma, USA in 2011. She is currently an Associate Professor with the School of Information Science and Technology, ShanghaiTech University, China. Before she joined ShanghaiTech University in 2015, she was a Postdoctoral Researcher with the KTH Royal Institute of Technology, Sweden, and with the Chalmers University of Technology, Sweden from 2012 to 2015. Her research interests include distributed optimization, optimization theory and algorithms, and networked dynamical systems.