Publications

2014

• An Eco-Evolutionary approach of Adaptation and Recombination in a large population of varying size
  
  • Smadi Charline
  , 2014. We identify the genetic signature of a selective sweep in a population described by a birth-and-death process with density dependent competition. We study the limit behaviour for large K, where K scales the population size. We focus on two loci: one under selection and one neutral. We distinguish a soft sweep occurring after an environmental change, from a hard sweep occurring after a mutation, and express the neutral proportion variation as a function of the ecological parameters, recombination probability r_K, and K. We show that for a hard sweep, two recombination regimes appear according to the order of r_K log K.
• Bilaplacian problems with a sign-changing coefficient
  
  • Chesnel Lucas
  Mathematical Methods in the Applied Sciences, Wiley, 2014, pp.10.1002/mma.3366. We investigate the properties of the operator ∆(σ∆·) : H^2_0 (Ω) → H^{−2}(Ω), where σ is a given parameter whose sign can change on the bounded domain Ω. Here, H^2_0 (Ω) denotes the subspace of H^2(Ω) made of the functions v such that v = ν · ∇v = 0 on ∂Ω. The study of this problem arises when one is interested in some configurations of the Interior Transmission Eigenvalue Problem. We prove that ∆(σ∆·) : H^2_0 (Ω) → H^{−2}(Ω) is a Fredholm operator of index zero as soon as σ ∈ L^∞(Ω), with σ^{−1}∈ L^∞(Ω), is such that σ remains uniformly positive (or uniformly negative) in a neighbourhood of ∂Ω. We also study configurations where σ changes sign on ∂Ω and we prove that Fredholm property can be lost for such situations. In the process, we examine in details the features of a simpler problem where the boundary condition ν · ∇v = 0 is replaced by σ∆v = 0 on ∂Ω. (10.1002/mma.3366)
  DOI : 10.1002/mma.3366
• A Necklace Model for Vesicles Simulations in 2D
  
  • Ismail Mourad
  • Lefebvre-Lepot Aline
  International Journal for Numerical Methods in Fluids, Wiley, 2014, 76 (11), pp.835–854. The aim of this paper is to propose a new numerical model to simulate 2D vesicles interacting with a newtonian fluid. The inextensible membrane is modeled by a chain of circular rigid particles which are maintained in cohesion by using two different type of forces. First, a spring force is imposed between neighboring particles in the chain. Second, in order to model the bending of the membrane, each triplet of successive particles is submitted to an angular force. Numerical simulations of vesicles in shear flow have been run using Finite Element Method and the FreeFem++[1] software. Exploring different ratios of inner and outer viscosities, we recover the well known "Tank-Treading" and "Tumbling" motions predicted by theory and experiments. Moreover, for the first time, 2D simulations of the "Vacillating-Breathing" regime predicted by theory in [2] and observed experimentally in [3] are done without special ingredient like for example thermal fluctuations used in [4]. (10.1002/fld)
  DOI : 10.1002/fld
• Combinatorial simplex algorithms can solve mean payoff games
  
  • Allamigeon Xavier
  • Benchimol Pascal
  • Gaubert Stéphane
  • Joswig Michael
  SIAM Journal on Optimization, Society for Industrial and Applied Mathematics, 2014, 24 (4), pp.22. A combinatorial simplex algorithm is an instance of the simplex method in which the pivoting depends on combinatorial data only. We show that any algorithm of this kind admits a tropical analogue which can be used to solve mean payoff games. Moreover, any combinatorial simplex algorithm with a strongly polynomial complexity (the existence of such an algorithm is open) would provide in this way a strongly polynomial algorithm solving mean payoff games (all the arithmetic operations being performed on data polynomially bounded in the size of the input, in particular). Mean payoff games are known to be in NP and co-NP; whether they can be solved in polynomial time is an open problem. Our algorithm relies on a tropical implementation of the simplex method over a real closed field of Hahn series. One of the key ingredients is a new scheme for symbolic perturbation which allows us to lift an arbitrary mean payoff game instance into a non-degenerate linear program over Hahn series. (10.1137/140953800)
  DOI : 10.1137/140953800
• A max-plus based randomized algorithm for solving a class of HJB PDEs
  
  • Qu Zheng
  , 2014, pp.1575--1580. McEneaney introduced the curse of dimensionality free method for the special class of infinite horizon optimal control problems where the Hamiltonian is represented as a maximum of quadratic affine functions. This method is featured by its cubic complexity with respect to the state space dimension, but the number of basis functions is multiplied by the number of switches at each iteration, referred to as the ’curse of complexity’. In previous works, an SDP-based pruning technique was incorporated into the method in order to reduce the curse of complexity. Its efficiency was proved on many examples. In this paper we develop a new max-plus based randomized algorithm to solve the same class of infinite horizon optimal control problems. The major difference between the new algorithm and the previous SDP-based curse of dimensionality free method is that, instead of adding a large number of functions and then pruning the less useful ones, the new algorithm finds in cheap computation time (linear in the current number of basis functions), by a randomized procedure, useful quadratic functions and adds only those functions to the set of basis functions. Experimental results show that the max- plus randomized algorithm can reach the same precision order obtained by the SDP-based method with a speedup varying from 10 up to 100 and that the maximal precision order attainable by the new algorithm is much better than what can be done by the SDP-based algorithm in reasonable computation time. Besides, with the randomized algorithm we are now able to tackle switched problems with more number of switches, which will allow us to extend the algorithm to more general classes of optimal control problems.
• Generic uniqueness of the bias vector of mean payoff zero-sum games
  
  • Akian Marianne
  • Gaubert Stephane
  • Hochart Antoine
  , 2014. Zero-sum mean payoff games can be studied by means of a nonlinear spectral problem. When the state space is finite, the latter consists in finding an eigenpair (u,λ) solution of T(u)=λ1+u where T is the Shapley (dynamic programming) operator, λ is a scalar, 1 is the unit vector, and u is a n dimensional vector. The scalar λ yields the mean payoff per time unit, and the vector u, called the bias, allows one to determine optimal stationary strategies. The existence of the eigenpair (u,λ) is generally related to ergodicity conditions. A basic issue is to understand for which classes of games the bias vector is unique (up to an additive constant). In this paper, we consider perfect information zero-sum stochastic games with finite state and action spaces, thinking of the transition payments as variable parameters, transition probabilities being fixed. We identify structural conditions on the support of the transition probabilities which guarantee that the spectral problem is solvable for all values of the transition payments. Then, we show that the bias vector, thought of as a function of the transition payments, is generically unique (up to an additive constant). The proof uses techniques of max-plus (tropical) algebra and nonlinear Perron-Frobenius theory.
• Non-linear eigenvalue problems arising from growth maximization of positive linear dynamical systems
  
  • Calvez Vincent
  • Gabriel Pierre
  • Gaubert Stéphane
  , 2014, pp.1600--1607. We study a growth maximization problem for a continuous time positive linear system with switches. This is motivated by a problem of mathematical biology (modeling growth-fragmentation processes and the PMCA protocol). We show that the growth rate is determined by the non-linear eigenvalue of a max-plus analogue of the Ruelle-Perron-Frobenius operator, or equivalently, by the ergodic constant of a Hamilton-Jacobi (HJ) partial differential equation, the solutions or subsolutions of which yield Barabanov and extremal norms, respectively. We exploit contraction properties of order preserving flows, with respect to Hilbert's projective metric, to show that the non-linear eigenvector of the operator, or the ''weak KAM'' solution of the HJ equation, does exist. Low dimensional examples are presented, showing that the optimal control can lead to a limit cycle. (10.1109/CDC.2014.7039628)
  DOI : 10.1109/CDC.2014.7039628
• Minimal Complexity Sinusoidal Controls for Path Planning
  
  • Gauthier Jean-Paul
  • Kawski Matthias
  , 2014.
• On the steady flow of reactive gaseous mixture
  
  • Giovangigli Vincent
  • Pokorny Milan
  • Zatorska Ewelina
  , 2014. We present the study of systems of equations governing a steady flow of poly-atomic, heat-conducting reactive gas mixture. It is shown that the corresponding system of PDEs admits a weak solution and renormalized solution to the continuity equation, provided the adiabatic exponent for the mixture γ is greater than 5 3 .
• On the controllability of quantum transport in an electronic nanostructure
  
  • Méhats Florian
  • Privat Yannick
  • Sigalotti Mario
  SIAM Journal on Applied Mathematics, Society for Industrial and Applied Mathematics, 2014, 74 (6), pp.1870--1894. We investigate the controllability of quantum electrons trapped in a two-dimensional device, typically a MOS field-effect transistor. The problem is modeled by the Schrödinger equation in a bounded domain coupled to the Poisson equation for the electrical potential. The controller acts on the system through the boundary condition on the potential, on a part of the boundary modeling the gate. We prove that, generically with respect to the shape of the domain and boundary conditions on the gate, the device is controllable. We also consider control properties of a more realistic nonlinear version of the device, taking into account the self-consistent electrostatic Poisson potential. (10.1137/130939328)
  DOI : 10.1137/130939328
• Korn-Poincaré inequalities for functions with a small jump set
  
  • Chambolle Antonin
  • Conti Sergio
  • Francfort Gilles
  , 2014. Special functions with bounded deformation" and p-integrable strain arise naturally in the study of geometrically linear fracture models. They have a jump set of finite (n − 1)-dimensional measure and, away from the jump set, a symmetrized gradient e(u) in Lp , p ≥ 1. We show that if the measure of the jump set is sufficiently small with respect to the size of the domain, then the function u can be approximated by an affine function away from a small exceptional set, with an error which depends solely on e(u). We also derive a corresponding trace statement.
• Tropical aspects of linear programming
  
  • Benchimol Pascal
  , 2014. In this thesis, we present new results on the complexity of classical linear programming on the one hand, and of tropical linear programming and mean payoff games on the other hand. Our contributions lie in the study of the interplay between these two problems provided by the dequantization process. This process tranforms classical linear programs into linear programs over tropical semirings, such as the $\R \cup\{ -\infty\}$ endowed with $\max$ as addition and $+$ as muliplication. Concerning classical linear programming, our first contribution is a tropicalization of the simplex method. More precisely, we describe an implementation of the simplex method that, under genericity conditions, solves a linear program over an ordered field. Our implementation uses only the restricted information provided by the valuation map, which corresponds to the ``orders of magnitude'' of the input. Using this approach, we exhibit a class of classical linear programs over the real numbers on which the simplex method, with any pivoting rule, performs a number of iterations which is polynomial in the input size of the problem. In particular, this implies that the corresponding polyhedra have a diameter which is polynomial in the input size. Our second contribution concerns interior point methods for classical linear programming. We disprove the continuous analog of the Hirsch conjecture proposed by Deza, Terlaky and Zinchenko, by constructing a family of linear programs with $3r + 4$ inequalities in dimension $2r + 2$ where the central path has a total curvature which is exponential in $r$. We also point out suprising features of the tropicalization of the central path. For example it has a purely geometric description, while the classical central path depends on the algebraic representation of a linear program. Moreover, the tropical central path may lie on the boundary of the tropicalization of the feasible set, and may even coincide with a path of the tropical simplex method. Concerning tropical linear programming and mean payoff games, our main result is a new procedure to solve these problems based on the tropicalization of the simplex method. The latter readily applies to tropical linear programs satisfying genericity conditions. In order to solve arbitrary problems, we devise a new perturbation scheme. Our key tool is to use tropical semirings based on additive groups of vectors ordered lexicographically. Then, we transfer complexity results from classical to tropical linear programming. We show that the existence of a polynomial-time pivoting rule for the classical simplex method, satisfying additional assumptions, would provide a polynomial algorithm for tropical linear programming and thus for mean payoff games. By transferring the analysis of the shadow-vertex rule of Adler, Karp and Shamir, we also obtain the first algorithm that solves mean payoff games in polynomial time on average, assuming the distribution of the games satisfies a symmetry property. We establish tropical counterparts of the notions of basic points and edges of a polyhedron. This yields a geometric interpretation of the tropicalization of the simplex method. As in the classical case, the tropical algorithm pivots on the graph of an arrangement of hyperplanes associated to a tropical polyhedron. This interpretation is based on a geometric connection between the cells of an arrangement of classical hyperplanes and their tropicalization. Building up on this geometric interpretation, we present algorithmic refinements of the tropical pivoting operation. We show that pivoting along an edge of a tropical polyhedron defined by $m$ inequalities in dimension $n$ can be done in time $O(n(m+n))$, a complexity similar to the classical pivoting operation. We also show that the computation of reduced costs can be done tropically in time $O(n(m+n))$.
• Parareal in time 3D numerical solver for the LWR Benchmark neutron diffusion transient model
  
  • Baudron Anne-Marie
  • Lautard Jean-Jacques
  • Maday Yvon
  • Riahi Mohamed Kamel
  • Salomon Julien
  Journal of Computational Physics, Elsevier, 2014, 279, pp.67 - 79. Abstract In this paper we present a time-parallel algorithm for the 3D neutrons calculation of a transient model in a nuclear reactor core. The neutrons calculation consists in numerically solving the time dependent diffusion approximation equation, which is a simplified transport equation. The numerical resolution is done with finite elements method based on a tetrahedral meshing of the computational domain, representing the reactor core, and time discretization is achieved using a θ-scheme. The transient model presents moving control rods during the time of the reaction. Therefore, cross-sections (piecewise constants) are taken into account by interpolations with respect to the velocity of the control rods. The parallelism across the time is achieved by an adequate use of the parareal in time algorithm to the handled problem. This parallel method is a predictor corrector scheme that iteratively combines the use of two kinds of numerical propagators, one coarse and one fine. Our method is made efficient by means of a coarse solver defined with large time step and fixed position control rods model, while the fine propagator is assumed to be a high order numerical approximation of the full model. The parallel implementation of our method provides a good scalability of the algorithm. Numerical results show the efficiency of the parareal method on large light water reactor transient model corresponding to the Langenbuch–Maurer–Werner benchmark. (10.1016/j.jcp.2014.08.037)
  DOI : 10.1016/j.jcp.2014.08.037
• Shape optimization with a level set based mesh evolution method
  
  • Allaire Grégoire
  • Dapogny Charles
  • Frey Pascal
  Computer Methods in Applied Mechanics and Engineering, Elsevier, 2014, pp.doi:10.1016/j.cma.2014.08.028. In this article, we discuss an approach for geometry and topology optimization of structures which benefits from an accurate description of shapes at each stage of the iterative process - by means of a mesh amenable for mechanical analyses - while retaining the whole versatility of the level set method when it comes to accounting for their evolution. The key ingredients of this method are two operators for switching from a meshed representation of a domain to an implicit one, and conversely; this notably brings into play an algorithm for generating the signed distance function to an arbitrary discrete domain, and a mesh generation algorithm for implicitly-defined geometries.
• Energy management method for an electric vehicle
  
  • Granato Giovanni
  • Bonnans J. Frederic
  • Aouchiche K.
  • Grégory Rousseau
  • Zidani Hasnaa
  , 2014. The invention relates to a method for managing energy consumption for an automobile having an electric battery and a heat engine, said method making it possible to select the use phases of said engine along a given route so as to minimize the fuel consumption of said vehicle. The main characteristic of the method according to the invention is that it includes the following steps: a step of cutting the road network, which is taken into consideration for a given route, into a plurality of segments, each segment being defined by an input node and by an output node; a step of calculating, from a speed associated with said segment, the probability of a speed transition between a speed at an input node and a speed at an output node of a segment, while taking a plurality of speeds at the input node and a plurality speeds at the output node into consideration, said step being carried out gradually over all of the segments of the route; a step of applying a stochastic optimization algorithm taking all the possible transition scenarios between each input node and each output node, and the probability associated therewith, into account, and taking a fuel consumption model between two successive nodes into account, said step being carried out over all of the segments of the route; and a step of selecting use phases of the heat engine along the route.
• Contribution aux risques d’information asymétrique,de longévité et d’externalisation
  
  • Hillairet Caroline
  , 2014. Ce mémoire est une synthèse de mes travaux de recherche depuis ma thèse doctorale. Ces travaux s’articulent selon trois thèmes: Risque de défaut et information asymétrique, Risque de longévité et règle de Ramsey avec utilité progressive, Contrat Partenariat-Public-Privé et Externalisation de la dette. Ces sujets sont issus de motivations rattachéesaux domaines de la finance, de l’assurance ou de l’ ́économie. L’étude de cesproblèmes fait intervenir des outils mathématiques et probabilistes variés,comme par exemple des outils de grossissements de filtrations, des techniquesd’optimisation reposant sur des méthodes de dualité , du contrôle stochastique,des méthodes de programmation dynamique et de la théorie des jeux.
• Spectral properties for Hamiltonians of weak interactions
  
  • Barbaroux Jean-Marie
  • Faupin Jérémy
  • Guillot Jean-Claude
  , 2016, 254, pp.11-36. We present recent results on the spectral theory for Hamiltonians of the weak decay. We discuss rigorous results on self-adjointness, location of the essential spectrum, existence of a ground state, purely absolutely continuous spectrum and limiting absorption principles. The last two properties heavily rely on the so-called Mourre Theory, which is used, depending on the Hamiltonian we study, either in its standard form, or in a more general framework using non self-adjoint conjugate operators.
• Volume Viscosity and Internal Energy Relaxation : Error Estimates
  
  • Giovangigli Vincent
  • Yong Wen-An
  , 2014. We investigate the fast relaxation of internal energy in nonequilibrium gas models derived from the kinetic theory of gases. We establish a priori estimates and existence theorems for symmetric hyperbolic-parabolic systems of partial differential equations with small second order terms and stiff sources. We also establish the stability of the corresponding equilibrium systems. We then prove local in time error estimates between the out of equilibrium solution and the one-temperature equilibrium fluid solution for well prepared data and justify the apparition of volume viscosity terms. The situation of ill prepared data with initial layers is also addressed.
• Certification of real inequalities: templates and sums of squares
  
  • Magron Victor
  • Allamigeon Xavier
  • Gaubert Stéphane
  • Werner Benjamin
  Mathematical Programming, Springer Verlag, 2014, 151 (2), pp.30. We consider the problem of certifying lower bounds for real-valued multivariate transcendental functions. The functions we are dealing with are nonlinear and involve semialgebraic operations as well as some transcendental functions like cos, arctan, exp, etc. Our general framework is to use different approximation methods to relax the original problem into polynomial optimization problems, which we solve by sparse sums of squares relaxations. In particular, we combine the ideas of the maxplus approximations (originally introduced in optimal control) and of the linear templates (originally introduced in static analysis by abstract interpretation). The nonlinear templates control the complexity of the semialgebraic relaxations at the price of coarsening the maxplus approximations. In that way, we arrive at a new—template based—certified global optimization method, which exploits both the precision of sums of squares relaxations and the scalability of abstraction methods. We analyze the performance of the method on problems from the global optimization literature, as well as medium-size inequalities issued from the Flyspeck project. (10.1007/s10107-014-0834-5)
  DOI : 10.1007/s10107-014-0834-5
• Structure fractale tridimensionnelle avec une transformation conforme 1/O dans l'ensemble des Octonions -section tridimensionnelle
  
  • Colonna Jean-François
  , 2014. Tridimensional fractal structure with a 1/O conformal transformation in the Octonionic space -tridimensional cross-section- (Structure fractale tridimensionnelle avec une transformation conforme 1/O dans l'ensemble des Octonions -section tridimensionnelle-)
• Generic uniqueness of the bias vector of mean-payoff zero-sum games
  
  • Akian Marianne
  • Gaubert Stephane
  • Hochart Antoine
  , 2014. Zero-sum mean payoff games can be studied by means of a nonlinear spectral problem. When the state space is finite, the latter consists in finding an eigenpair (u,λ) solution of T(u)=λ1+u where T:Rn→Rn is the Shapley (dynamic programming) operator, λ is a scalar, 1 is the unit vector, and u∈Rn. The scalar λ yields the mean payoff per time unit, and the vector u, called the bias, allows one to determine optimal stationary strategies. The existence of the eigenpair (u,λ) is generally related to ergodicity conditions. A basic issue is to understand for which classes of games the bias vector is unique (up to an additive constant). In this paper, we consider perfect information zero-sum stochastic games with finite state and action spaces, thinking of the transition payments as variable parameters, transition probabilities being fixed. We identify structural conditions on the support of the transition probabilities which guarantee that the spectral problem is solvable for all values of the transition payments. Then, we show that the bias vector, thought of as a function of the transition payments, is generically unique (up to an additive constant). The proof uses techniques of max-plus (tropical) algebra and nonlinear Perron-Frobenius theory.
• Complexity of policy iteration for stochastic zero-sum games
  
  • Akian Marianne
  • Gaubert Stéphane
  , 2014.
• Comparison of Viscosity Solutions of Semi-linear Path-Dependent PDEs
  
  • Ren Zhenjie
  • Touzi Nizar
  • Zhang Jianfeng
  , 2014. This paper provides a probabilistic proof of the comparison result for viscosity solutions of path-dependent semilinear PDEs. We consider the notion of viscosity solutions introduced in [8] which considers as test functions all those smooth processes which are tangent in mean. When restricted to the Markovian case, this definition induces a larger set of test functions, and reduces to the notion of stochastic viscosity solutions analyzed in [1, 2]. Our main result takes advantage of this enlargement of the test functions, and provides an easier proof of comparison. This is most remarkable in the context of the linear path-dependent heat equation. As a key ingredient for our methodology, we introduce a notion of punctual differentiation, similar to the corresponding concept in the standard viscosity solutions [3], and we prove that semimartingales are almost everywhere punctually differentiable. This smoothness result can be viewed as the counterpart of the Aleksandroff smoothness result for convex functions. A similar comparison result was established earlier in [8]. The result of this paper is more general and, more importantly, the arguments that we develop do not rely on any representation of the solution.
• Ancestral lineages and limit theorems for branching Markov chains
  
  • Bansaye Vincent
  , 2014. We consider a branching model in discrete time for structured population in varying environment. Each individual has a trait, which belongs to some general state space and both the reproduction law and the trait inherited by the offsprings may depend on the trait of the mother and the environment. We study the long time behavior of the population and the ancestral lineage of typical individuals under general assumptions. We focus on the growth rate and the trait distribution among the population for large time and provide some estimations of the local densities. A key role is played by well chosen (possibly non-homogeneous) Markov chains. It relies in particular on an extension of many-to-one formula and the analysis of the genealogy, in the vein of the spine decomposition. The applications use the spectral gap of the mean operator, the Harris ergodicity or the large deviations of this auxiliary Markov chain.
• Viscosity Solutions of Fully Nonlinear Elliptic Path Dependent PDEs
  
  • Ren Zhenjie
  , 2014. This paper introduces a convenient solution space for the uniformly elliptic fully nonlinear path dependent PDEs. It provides a wellposedness result under standard Lipschitz-type assumptions on the nonlinearity and an additional assumption formulated on some partial differential equation defined locally by freezing the path.