TY - CHAP
T1 - Decentralized consensus optimization and resource allocation
AU - Nedich, Angelia
AU - Olshevsky, Alexander
AU - Shi, Wei
N1 - Funding Information:
The work of A.N. and A.O. was supported by the Office of Naval Research grant N000014-16-1-2245. The work of A.O. was also supported by the NSF award CMMI-1463262 and AFOSR award FA-95501510394.
Funding Information:
Fig. 10.4 Plots of the normalized residual ‖x0−x∗‖F‖xk−x∗‖F. The step sizes for Mirror-Push-DIGing are roughly hand tuned. rc is the connectivity ratio and ra is the activation ratio Acknowledgements The work of A.N. and A.O. was supported by the Office of Naval Research grant N000014-16-1-2245. The work of A.O. was also supported by the NSF award CMMI-1463262 and AFOSR award FA-95501510394.
Publisher Copyright:
© 2018, Springer Nature Switzerland AG.
PY - 2018
Y1 - 2018
N2 - We consider the problems of consensus optimization and resource allocation, and we discuss decentralized algorithms for solving such problems. By “decentralized”, we mean the algorithms are to be implemented in a set of networked agents, whereby each agent is able to communicate with its neighboring agents. For both problems, every agent in the network wants to collaboratively minimize a function that involves global information, while having access to only partial information. Specifically, we will first introduce the two problems in the context of distributed optimization, review the related literature, and discuss an interesting “mirror relation” between the problems. Afterwards, we will discuss some of the state-of-the-art algorithms for solving the decentralized consensus optimization problem and, based on the “mirror relationship”, we then develop some algorithms for solving the decentralized resource allocation problem. We also provide some numerical experiments to demonstrate the efficacy of the algorithms and validate the methodology of using the “mirror relation”.
AB - We consider the problems of consensus optimization and resource allocation, and we discuss decentralized algorithms for solving such problems. By “decentralized”, we mean the algorithms are to be implemented in a set of networked agents, whereby each agent is able to communicate with its neighboring agents. For both problems, every agent in the network wants to collaboratively minimize a function that involves global information, while having access to only partial information. Specifically, we will first introduce the two problems in the context of distributed optimization, review the related literature, and discuss an interesting “mirror relation” between the problems. Afterwards, we will discuss some of the state-of-the-art algorithms for solving the decentralized consensus optimization problem and, based on the “mirror relationship”, we then develop some algorithms for solving the decentralized resource allocation problem. We also provide some numerical experiments to demonstrate the efficacy of the algorithms and validate the methodology of using the “mirror relation”.
KW - Consensus optimization
KW - Convex constrained problems
KW - Decentralized algorithms
KW - Resource allocation
UR - http://www.scopus.com/inward/record.url?scp=85056630361&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85056630361&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-97478-1_10
DO - 10.1007/978-3-319-97478-1_10
M3 - Chapter
AN - SCOPUS:85056630361
T3 - Lecture Notes in Mathematics
SP - 247
EP - 287
BT - Lecture Notes in Mathematics
PB - Springer Verlag
ER -