Friday, February 9, 2024

Conservative polynomial approximations and applications to Fokker-Planck equations

 

Tino Laidin, Lorenzo Pareschi (preprint arXiv:2402.06473)

We address the problem of constructing approximations based on orthogonal polynomials that preserve an arbitrary set of moments of a given function without loosing the spectral convergence property. To this aim, we compute the constrained polynomial of best approximation for a generic basis of orthogonal polynomials. The construction is entirely general and allows us to derive structure preserving numerical methods for partial differential equations that require the conservation of some moments of the solution, typically representing relevant physical quantities of the problem.

Wednesday, January 10, 2024

Optimization by linear kinetic equations and mean-field Langevin dynamics

Lorenzo Pareschi (preprint arXiv:2401.05553)

Probably one of the most striking examples of the close connections between global optimization processes and statistical physics is the simulated annealing method, inspired by the famous Monte Carlo algorithm devised by Metropolis et al. in the middle of the last century. In this paper we show how the tools of linear kinetic theory allow to describe this gradient-free algorithm from the perspective of statistical physics and how convergence to the global minimum can be related to classical entropy inequalities. This analysis highlight the strong link between linear Boltzmann equations and stochastic optimization methods governed by Markov processes.

Sunday, December 31, 2023

Reduced variance random batch methods for nonlocal PDEs

Lorenzo Pareschi, Mattia Zanella (preprint arXiv:2401.00493)

Random Batch Methods (RBM) for mean-field interacting particle systems enable the reduction of the quadratic computational cost associated with particle interactions to a near-linear cost. The essence of these algorithms lies in the random partitioning of the particle ensemble into smaller batches at each time step. The interaction of each particle within these batches is then evolved until the subsequent time step. This approach effectively decreases the computational cost by an order of magnitude while increasing the amount of fluctuations due to the random partitioning. In this work, we propose a variance reduction technique for RBM applied to nonlocal PDEs of Fokker-Planck type based on a control variate strategy.

Modelling contagious viral dynamics: a kinetic approach based on mutual utility

 Giulia Bertaglia, Lorenzo Pareschi, Giuseppe Toscani (Math. Biosci. Eng. to appear. Preprint arXiv:2401.00480)

The time evolution of a contagious viral disease is modeled as the dynamic progression of different classes of populations that interact pairwise, aiming to improve their condition with respect to a given target. This evolutionary mechanism is based on binary interactions between agents, designed to enhance their utility mutually. To achieve this goal, we introduce kinetic equations of Boltzmann type to describe the time evolution of the probability distributions of the agent system undergoing binary interactions. The fundamental idea is to describe these interactions using principles from price theory, particularly by employing Cobb-Douglas utility functions for the binary exchange and the Edgeworth box to depict the common exchange area where utility increases for both agents.

Thursday, October 12, 2023

Kinetic description and convergence analysis of genetic algorithms for global optimization

Giacomo Borghi, Lorenzo Pareschi (preprint arXiv:2310.08562)

Genetic Algorithms (GA) are a class of metaheuristic global optimization methods inspired by the process of natural selection among individuals in a population. Despite their widespread use, a comprehensive theoretical analysis of these methods remains challenging due to the complexity of the heuristic mechanisms involved. In this work, relying on the tools of statistical physics, we take a first step towards a mathematical understanding of GA by showing how their behavior for a large number of individuals can be approximated through a time-discrete kinetic model. This allows us to prove the convergence of the algorithm towards a global minimum under mild assumptions on the objective function for a popular choice of selection mechanism. Furthermore, we derive a time-continuous model of GA, represented by a Boltzmann-like partial differential equation, and establish relations with other kinetic and mean-field dynamics in optimization.