Randomized Feasibility-Update Algorithms for Variational Inequality Problems
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910600464957440 |
|---|---|
| author | Chakraborty, Abhishek Nedić, Angelia |
| author_facet | Chakraborty, Abhishek Nedić, Angelia |
| contents | This paper considers a variational inequality (VI) problem arising from a game among multiple agents, where each agent aims to minimize its own cost function subject to its constrained set represented as the intersection of a (possibly infinite) number of convex functional level sets. A direct projection-based approach or Lagrangian-based techniques for such a problem can be computationally expensive if not impossible to implement. To deal with the problem, we consider randomized methods that avoid the projection step on the whole constraint set by employing random feasibility updates. In particular, we propose and analyze such random methods for solving VIs based on the projection method, Korpelevich method, and Popov method. We establish the almost sure convergence of the methods and, also, provide their convergence rate guarantees. We illustrate the performance of the methods in simulations for two-agent games. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_05462 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Randomized Feasibility-Update Algorithms for Variational Inequality Problems Chakraborty, Abhishek Nedić, Angelia Optimization and Control This paper considers a variational inequality (VI) problem arising from a game among multiple agents, where each agent aims to minimize its own cost function subject to its constrained set represented as the intersection of a (possibly infinite) number of convex functional level sets. A direct projection-based approach or Lagrangian-based techniques for such a problem can be computationally expensive if not impossible to implement. To deal with the problem, we consider randomized methods that avoid the projection step on the whole constraint set by employing random feasibility updates. In particular, we propose and analyze such random methods for solving VIs based on the projection method, Korpelevich method, and Popov method. We establish the almost sure convergence of the methods and, also, provide their convergence rate guarantees. We illustrate the performance of the methods in simulations for two-agent games. |
| title | Randomized Feasibility-Update Algorithms for Variational Inequality Problems |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2402.05462 |