Approximately Gaussian Replicator Flows: Nonconvex Optimization as a Nash-Convergent Evolutionary Game
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929493803794432 |
|---|---|
| author | Anderson, Brendon G. Pfrommer, Samuel Sojoudi, Somayeh |
| author_facet | Anderson, Brendon G. Pfrommer, Samuel Sojoudi, Somayeh |
| contents | This work leverages tools from evolutionary game theory to solve unconstrained nonconvex optimization problems. Specifically, we lift such a problem to an optimization over probability measures, whose minimizers exactly correspond to the Nash equilibria of a particular population game. To algorithmically solve for such Nash equilibria, we introduce approximately Gaussian replicator flows (AGRFs) as a tractable alternative to simulating the corresponding infinite-dimensional replicator dynamics. Our proposed AGRF dynamics can be integrated using off-the-shelf ODE solvers when considering objectives with closed-form integrals against a Gaussian measure. We theoretically analyze AGRF dynamics by explicitly characterizing their trajectories and stability on quadratic objective functions, in addition to analyzing their descent properties. Our methods are supported by illustrative experiments on a range of canonical nonconvex optimization benchmark functions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_19529 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Approximately Gaussian Replicator Flows: Nonconvex Optimization as a Nash-Convergent Evolutionary Game Anderson, Brendon G. Pfrommer, Samuel Sojoudi, Somayeh Optimization and Control This work leverages tools from evolutionary game theory to solve unconstrained nonconvex optimization problems. Specifically, we lift such a problem to an optimization over probability measures, whose minimizers exactly correspond to the Nash equilibria of a particular population game. To algorithmically solve for such Nash equilibria, we introduce approximately Gaussian replicator flows (AGRFs) as a tractable alternative to simulating the corresponding infinite-dimensional replicator dynamics. Our proposed AGRF dynamics can be integrated using off-the-shelf ODE solvers when considering objectives with closed-form integrals against a Gaussian measure. We theoretically analyze AGRF dynamics by explicitly characterizing their trajectories and stability on quadratic objective functions, in addition to analyzing their descent properties. Our methods are supported by illustrative experiments on a range of canonical nonconvex optimization benchmark functions. |
| title | Approximately Gaussian Replicator Flows: Nonconvex Optimization as a Nash-Convergent Evolutionary Game |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2406.19529 |