Nhat Thang LE soutiendra publiquement ses travaux de thèse en mathématiques le jeudi 30 octobre 2025 à 15h00. (Auditorium 4 bâtiment TSE)
Titre des travaux: Algorithmic Aspects of Markov Processes and Their Applications
Cette thèse pourra également être suivie en ligne. Pour obtenir le lien Teams, merci de contacter le candidat.
Les membres du jury sont :
- Mr. Jan Maas – Institute of Science and Technology of Austria (Referee)
- Mr. Zhenji Ren – LaMME, Université d’Évry, Paris-Saclay (Referee)
- Mr. Pierre Del Moral – INRIA Bordeaux (Examiner)
- Mrs. Aurélia Deshayes – Université Paris-Est Créteil (Examiner)
- Mr. Laurent Miclo – Institut de Mathématiques de Toulouse, CNRS (Thesis Advisor)
- Mr. Stéphane Villeneuve – Toulouse School of Economics (Thesis Co-Advisor)
Résumé (en anglais) :
This thesis presents two applications of Markov processes.
The first part focuses on finite optimization, where we propose a new swarm dynamic formulated in the framework of nonlinear Markov chains. This dynamic serves as the foundation for a particle approximation algorithm designed to approximate the nonlinear Markov evolution. The underlying idea is that the interacting particles progressively concentrate on the set of optimizers of the target function. A key result we establish is that, by choosing a temperature schedule of the form βt ≈ t^α with α∈(0,1/2), the measure of the set of global optimizers converges to 1. This contrasts with the classical ln(t) temperature schedule used in simulated annealing algorithms.
The second part introduces a novel and efficient algorithm for computing both the value function and the Nash equilibrium in a class of zero-sum optimal stopping games involving two players, commonly known as Dynkin games. In such games, the players observe the evolution of a Markov process on a finite state space and may choose to stop the game at any time. When the game stops, a payoff is made from one player to the other. The proposed algorithm demonstrates strong practical efficiency and opens a promising direction for future applied research, complementing the already well-established theoretical literature on this topic. In particular, the algorithm terminates in strictly fewer than N^2 steps, where N denotes the size of the underlying state space. Moreover, each step requires only the computation of a matrix inverse, making the overall computational complexity entirely dependent on that of matrix inversion algorithms.
