Simple Synchronous and Asynchronous Algorithms for Distributed Minimax Optimization

Abstract

Synchronous and asynchronous algorithms are presented for distributed minimax optimization. The objective here is to realize the minimization of the maximum of component functions over the standard multi-agent network, where each node of the network knows its own function and it exchanges its decision variable with its neighbors. In fact, the proposed algorithms are standard consensus and gossip based subgradient methods, while the original minimax optimization is recast as minimization of the sum of component functions by using a p-norm approximation. A scalable step size depending on the approximation ratio p is also presented in order to avoid slow convergence. Numerical examples illustrate that the algorithms with this step size work well even in the high approximation ratios.

Keywords

• distributed algorithms
• minimax optimization
• synchronous algorithms
• asynchronous algorithms