Simple Synchronous and Asynchronous Algorithms for Distributed Minimax Optimization
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 decisi...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Taylor & Francis Group
2017-11-01
|
| Series: | SICE Journal of Control, Measurement, and System Integration |
| Subjects: | |
| Online Access: | http://dx.doi.org/10.9746/jcmsi.10.557 |
| _version_ | 1797661055288082432 |
|---|---|
| author | Kenta Hanada Ryosuke Morita Takayuki Wada Yasumasa Fujisaki |
| author_facet | Kenta Hanada Ryosuke Morita Takayuki Wada Yasumasa Fujisaki |
| author_sort | Kenta Hanada |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-11T18:38:44Z |
| format | Article |
| id | doaj.art-5eb1c2ca739f417983bd907c9d0c5d91 |
| institution | Directory Open Access Journal |
| issn | 1884-9970 |
| language | English |
| last_indexed | 2024-03-11T18:38:44Z |
| publishDate | 2017-11-01 |
| publisher | Taylor & Francis Group |
| record_format | Article |
| series | SICE Journal of Control, Measurement, and System Integration |
| spelling | doaj.art-5eb1c2ca739f417983bd907c9d0c5d912023-10-12T13:43:54ZengTaylor & Francis GroupSICE Journal of Control, Measurement, and System Integration1884-99702017-11-0110655756210.9746/jcmsi.10.55712103177Simple Synchronous and Asynchronous Algorithms for Distributed Minimax OptimizationKenta Hanada0Ryosuke Morita1Takayuki Wada2Yasumasa Fujisaki3Graduate School of Information Science and Technology, Osaka UniversityFaculty of Engineering, Gifu UniversityGraduate School of Information Science and Technology, Osaka UniversityGraduate School of Information Science and Technology, Osaka UniversitySynchronous 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.http://dx.doi.org/10.9746/jcmsi.10.557distributed algorithmsminimax optimizationsynchronous algorithmsasynchronous algorithms |
| spellingShingle | Kenta Hanada Ryosuke Morita Takayuki Wada Yasumasa Fujisaki Simple Synchronous and Asynchronous Algorithms for Distributed Minimax Optimization SICE Journal of Control, Measurement, and System Integration distributed algorithms minimax optimization synchronous algorithms asynchronous algorithms |
| title | Simple Synchronous and Asynchronous Algorithms for Distributed Minimax Optimization |
| title_full | Simple Synchronous and Asynchronous Algorithms for Distributed Minimax Optimization |
| title_fullStr | Simple Synchronous and Asynchronous Algorithms for Distributed Minimax Optimization |
| title_full_unstemmed | Simple Synchronous and Asynchronous Algorithms for Distributed Minimax Optimization |
| title_short | Simple Synchronous and Asynchronous Algorithms for Distributed Minimax Optimization |
| title_sort | simple synchronous and asynchronous algorithms for distributed minimax optimization |
| topic | distributed algorithms minimax optimization synchronous algorithms asynchronous algorithms |
| url | http://dx.doi.org/10.9746/jcmsi.10.557 |
| work_keys_str_mv | AT kentahanada simplesynchronousandasynchronousalgorithmsfordistributedminimaxoptimization AT ryosukemorita simplesynchronousandasynchronousalgorithmsfordistributedminimaxoptimization AT takayukiwada simplesynchronousandasynchronousalgorithmsfordistributedminimaxoptimization AT yasumasafujisaki simplesynchronousandasynchronousalgorithmsfordistributedminimaxoptimization |