Distributed Gradient Tracking Methods with Guarantees for Computing a Solution to Stochastic MPECs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917611800887296 |
|---|---|
| author | Ebrahimi, Mohammadjavad Shanbhag, Uday V. Yousefian, Farzad |
| author_facet | Ebrahimi, Mohammadjavad Shanbhag, Uday V. Yousefian, Farzad |
| contents | We consider a class of hierarchical multi-agent optimization problems over networks where agents seek to compute an approximate solution to a single-stage stochastic mathematical program with equilibrium constraints (MPEC). MPECs subsume several important problem classes including Stackelberg games, bilevel programs, and traffic equilibrium problems, to name a few. Our goal in this work is to provably resolve stochastic MPECs in distributed regimes where the agents only have access to their local objectives and an inexact best-response to the lower-level equilibrium problem. To this end, we devise a new method called randomized smoothed distributed zeroth-order gradient tracking (rs-DZGT). This is a novel gradient tracking scheme where agents employ a zeroth-order implicit scheme to approximate their (unavailable) local gradients. Leveraging the properties of a randomized smoothing technique, we establish the convergence of the method and derive complexity guarantees for computing a stationary point of an optimization problem with a smoothed implicit global objective. We also provide preliminary numerical experiments where we compare the performance of rs-DZGT on networks under different settings with that of its centralized counterpart. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_09356 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Distributed Gradient Tracking Methods with Guarantees for Computing a Solution to Stochastic MPECs Ebrahimi, Mohammadjavad Shanbhag, Uday V. Yousefian, Farzad Optimization and Control We consider a class of hierarchical multi-agent optimization problems over networks where agents seek to compute an approximate solution to a single-stage stochastic mathematical program with equilibrium constraints (MPEC). MPECs subsume several important problem classes including Stackelberg games, bilevel programs, and traffic equilibrium problems, to name a few. Our goal in this work is to provably resolve stochastic MPECs in distributed regimes where the agents only have access to their local objectives and an inexact best-response to the lower-level equilibrium problem. To this end, we devise a new method called randomized smoothed distributed zeroth-order gradient tracking (rs-DZGT). This is a novel gradient tracking scheme where agents employ a zeroth-order implicit scheme to approximate their (unavailable) local gradients. Leveraging the properties of a randomized smoothing technique, we establish the convergence of the method and derive complexity guarantees for computing a stationary point of an optimization problem with a smoothed implicit global objective. We also provide preliminary numerical experiments where we compare the performance of rs-DZGT on networks under different settings with that of its centralized counterpart. |
| title | Distributed Gradient Tracking Methods with Guarantees for Computing a Solution to Stochastic MPECs |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2310.09356 |