Swarm dynamics for global optimisation on finite sets
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916205813563392 |
|---|---|
| author | Miclo, Laurent Le, Nhat-Thang |
| author_facet | Miclo, Laurent Le, Nhat-Thang |
| contents | Consider the global optimisation of a function $U$ defined on a finite set $V$ endowed with an irreducible and reversible Markov generator.By integration, we extend $U$ to the set $\mathcal{P}(V)$ of probability distributions on $V$ and we penalise it with a time-dependent generalised entropy functional.Endowing $\mathcal{P}(V)$ with a Maas' Wasserstein-type Riemannian structure, enables us to consider an associated time-inhomogeneous gradient descent algorithm.There are several ways to interpret this $\cP(V)$-valued dynamical system as the time-marginal laws of a time-inhomogeneous non-linear Markov process taking values in $V$, each of them allowing for interacting particle approximations.This procedure extends to the discrete framework the continuous state space swarm algorithm approach of Bolte, Miclo and Villeneuve \cite{Bolte}, but here we go further by considering more general generalised entropy functionals for which functional inequalities can be proven.Thus in the full generality of the above finite framework, we give conditions on the underlying time dependence ensuring the convergence of the algorithm toward laws supported by the set of global minima of $U$.Numerical simulations illustrate that one has to be careful about the choice of the time-inhomogeneous non-linear Markov process interpretation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_09572 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Swarm dynamics for global optimisation on finite sets Miclo, Laurent Le, Nhat-Thang Functional Analysis Probability Consider the global optimisation of a function $U$ defined on a finite set $V$ endowed with an irreducible and reversible Markov generator.By integration, we extend $U$ to the set $\mathcal{P}(V)$ of probability distributions on $V$ and we penalise it with a time-dependent generalised entropy functional.Endowing $\mathcal{P}(V)$ with a Maas' Wasserstein-type Riemannian structure, enables us to consider an associated time-inhomogeneous gradient descent algorithm.There are several ways to interpret this $\cP(V)$-valued dynamical system as the time-marginal laws of a time-inhomogeneous non-linear Markov process taking values in $V$, each of them allowing for interacting particle approximations.This procedure extends to the discrete framework the continuous state space swarm algorithm approach of Bolte, Miclo and Villeneuve \cite{Bolte}, but here we go further by considering more general generalised entropy functionals for which functional inequalities can be proven.Thus in the full generality of the above finite framework, we give conditions on the underlying time dependence ensuring the convergence of the algorithm toward laws supported by the set of global minima of $U$.Numerical simulations illustrate that one has to be careful about the choice of the time-inhomogeneous non-linear Markov process interpretation. |
| title | Swarm dynamics for global optimisation on finite sets |
| topic | Functional Analysis Probability |
| url | https://arxiv.org/abs/2404.09572 |