A Fenchel dual gradient method enabling regularization for nonsmooth distributed optimization over time-varying networks

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 $O(\frac{1}{{ϵ}^2}\ln \frac{1}{ϵ})$ iterations. Such iteration complexity can be improved to $O(\frac{1}{ϵ}\ln \frac{1}{ϵ})$ if the local objective functions are strongly convex but not necessarily differentiable. Finally, simulation results demonstrate the competence of RFDGM in practice.

Keywords:

• Distributed optimization
• decentralized optimization
• dual optimization method

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 We may simply choose $\overline{\lambda }$ to be n.

2 The comparison excludes the existing algorithms that require identical $X_i$ $\mathrm{\forall }i\in \mathcal{V}$ or more restricted network assumptions than Assumption 2.1.

Additional information

Funding

X. Wu and J. Lu were funded by the National Natural Science Foundation of China [grant number 61603254]. K.C. Sou was funded by the Ministry of Science and Technology (MOST) of Taiwan [grant number MOST 109-2221-E-110-016-MY2].

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.