TY - CHAP
T1 - Distributed bregman-distance algorithms for min-max optimization
AU - Srivastava, Kunal
AU - Nedić, Angelia
AU - Stipanović, Dušan
PY - 2013
Y1 - 2013
N2 - We consider a min-max optimization problem over a time-varying network of computational agents, where each agent in the network has its local convex cost function which is a private knowledge of the agent. The agents want to jointly minimize the maximum cost incurred by any agent in the network, while maintaining the privacy of their objective functions. To solve the problem, we consider subgradient algorithms where each agent computes its own estimates of an optimal point based on its own cost function, and it communicates these estimates to its neighbors in the network. The algorithms employ techniques from convex optimization, stochastic approximation and averaging protocols (typically used to ensure a proper information diffusion over a network), which allow time-varying network structure. We discuss two algorithms, one based on exact-penalty approach and the other based on primal-dual Lagrangian approach, where both approaches utilize Bregman-distance functions.We establish convergence of the algorithms (with probability one) for a diminishing step-size, and demonstrate the applicability of the algorithms by considering a power allocation problem in a cellular network.
AB - We consider a min-max optimization problem over a time-varying network of computational agents, where each agent in the network has its local convex cost function which is a private knowledge of the agent. The agents want to jointly minimize the maximum cost incurred by any agent in the network, while maintaining the privacy of their objective functions. To solve the problem, we consider subgradient algorithms where each agent computes its own estimates of an optimal point based on its own cost function, and it communicates these estimates to its neighbors in the network. The algorithms employ techniques from convex optimization, stochastic approximation and averaging protocols (typically used to ensure a proper information diffusion over a network), which allow time-varying network structure. We discuss two algorithms, one based on exact-penalty approach and the other based on primal-dual Lagrangian approach, where both approaches utilize Bregman-distance functions.We establish convergence of the algorithms (with probability one) for a diminishing step-size, and demonstrate the applicability of the algorithms by considering a power allocation problem in a cellular network.
UR - http://www.scopus.com/inward/record.url?scp=84890067050&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84890067050&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-34097-0_7
DO - 10.1007/978-3-642-34097-0_7
M3 - Chapter
AN - SCOPUS:84890067050
SN - 9783642340963
T3 - Studies in Computational Intelligence
SP - 143
EP - 174
BT - Agent-Based Optimization
PB - Springer
ER -