Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2402.05462 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _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 |