Simple Synchronous and Asynchronous Algorithms for Distributed Minimax Optimization. Issue 6 (1st November 2017)

• Record Type: Journal Article
• Authors: Hanada, Kenta; Morita, Ryosuke; Wada, Takayuki; Fujisaki, Yasumasa
• Is Part Of: SICE journal of control, measurement, and system integration. Volume 10:Issue 6(2017)
• Page Start: 557
• Page End: 562
• Publication Date: 2017-11-01
• Subjects: distributed algorithms -- minimax optimization -- synchronous algorithms -- asynchronous algorithms
• DOI: 10.9746/jcmsi.10.557
• Languages: English
• ISSNs: 1882-4889

Abstract

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.