Graph-structured tensor optimization for nonlinear density control and mean field games
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910378102882304 |
|---|---|
| author | Ringh, Axel Haasler, Isabel Chen, Yongxin Karlsson, Johan |
| author_facet | Ringh, Axel Haasler, Isabel Chen, Yongxin Karlsson, Johan |
| contents | In this work we develop a numerical method for solving a type of convex graph-structured tensor optimization problems. This type of problems, which can be seen as a generalization of multi-marginal optimal transport problems with graph-structured costs, appear in many applications. Examples are unbalanced optimal transport and multi-species potential mean field games, where the latter is a class of nonlinear density control problems. The method we develop is based on coordinate ascent in a Lagrangian dual, and under mild assumptions we prove that the algorithm converges globally. Moreover, under a set of stricter assumptions, the algorithm converges R-linearly. To perform the coordinate ascent steps one has to compute projections of the tensor, and doing so by brute force is in general not computationally feasible. Nevertheless, for certain graph structures it is possible to derive efficient methods for computing these projections, and here we specifically consider the graph structure that occurs in multi-species potential mean field games. We also illustrate the methodology on a numerical example from this problem class. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2112_05645 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Graph-structured tensor optimization for nonlinear density control and mean field games Ringh, Axel Haasler, Isabel Chen, Yongxin Karlsson, Johan Optimization and Control Systems and Control In this work we develop a numerical method for solving a type of convex graph-structured tensor optimization problems. This type of problems, which can be seen as a generalization of multi-marginal optimal transport problems with graph-structured costs, appear in many applications. Examples are unbalanced optimal transport and multi-species potential mean field games, where the latter is a class of nonlinear density control problems. The method we develop is based on coordinate ascent in a Lagrangian dual, and under mild assumptions we prove that the algorithm converges globally. Moreover, under a set of stricter assumptions, the algorithm converges R-linearly. To perform the coordinate ascent steps one has to compute projections of the tensor, and doing so by brute force is in general not computationally feasible. Nevertheless, for certain graph structures it is possible to derive efficient methods for computing these projections, and here we specifically consider the graph structure that occurs in multi-species potential mean field games. We also illustrate the methodology on a numerical example from this problem class. |
| title | Graph-structured tensor optimization for nonlinear density control and mean field games |
| topic | Optimization and Control Systems and Control |
| url | https://arxiv.org/abs/2112.05645 |