Distributed stochastic mirror descent algorithm for resource allocation problem
- PDF / 2,867,560 Bytes
- 9 Pages / 595.276 x 790.866 pts Page_size
- 83 Downloads / 219 Views
RESEARCH ARTICLE
Distributed stochastic mirror descent algorithm for resource allocation problem Yinghui Wang1,2 · Zhipeng Tu1,2 · Huashu Qin1,2 Received: 3 July 2020 / Revised: 8 September 2020 / Accepted: 8 September 2020 / Published online: 19 November 2020 © South China University of Technology, Academy of Mathematics and Systems Science, CAS and Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract In this paper, we consider a distributed resource allocation problem of minimizing a global convex function formed by a sum of local convex functions with coupling constraints. Based on neighbor communication and stochastic gradient, a distributed stochastic mirror descent algorithm is designed for the distributed resource allocation problem. Sublinear convergence to an optimal solution of the proposed algorithm is given when the second moments of the gradient noises are summable. A numerical example is also given to illustrate the effectiveness of the proposed algorithm. Keywords Distributed · Resource allocation problem · Stochastic gradient · Mirror descent
1 Introduction Distributed resource alloction, where agents cooperatively optimize a sum of separable convex functions with coupling constraints, plays an important part in distributed optimization due to its applications in economic systems, sensor networks, and power grids. Various algorithms, including distributed primal-dual algorithms [1, 2], distributed alternating direction method of multipliers (ADMM) algorithm [3], have been designed to solve distributed resource allocation problems. Most of above references assume that gradients of local objective functions in distributed resource allocation problems are exactly known by agents over the network. However, this assumption may not be true because data uncertainties are quite common in many practical applications. For example, in [4], the returns of investments are subject to some uncertain risks. Therefore, distribute stochastic algorithms [5–7], which take uncertainties into account, are very important for resource allocation problems. To mention a * Zhipeng Tu [email protected] 1
Key Lab of Systems and Control, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China
University of Chinese Academy of Sciences, Beijing 100190, China
2
few, [5] designed a distributed initialization-dependent decentralized algorithm with a constant stepsize and provided near-optimal convergence guarantees. With diminishing stepsizes, [6] provided convergence with probability one for a distributed stochastic primal-dual algorithm, and [7] further designed � � an algorithm over directed networks, for which an O √1 convergence rate was derived with strictly T
convex functions. The aforementioned algorithms (both deterministic and stochastic) were based on Euclidean projection, whose local projections could be easily computed. In these cases, the local constraints sets could only be described by simple sets, such as balls, hyperplanes, and bounded constraints
Data Loading...
