Distributed min-max optimization in networks

We consider a setup where we are given a network of agents with their local objective functions which are coupled through a common decision variable. We provide a distributed stochastic gradient algorithm for the agents to compute an optimal decision variable that minimizes the worst case loss incurred by any agent. We establish almost sure conver-gence of the agent’s estimates to a common optimal point. We demonstrate the use of our algorithm to a problem of min-max fair power allocation in a cellular network. Index Terms — Distributed network optimization, min-max problem, subgradient algorithm, stochastic approxima-tion. 1