Publications

2006

• Geometric Variance Reduction in Markov Chains: Application to Value Function and Gradient Estimation
  
  • Munos Rémi
  Journal of Machine Learning Research, Microtome Publishing, 2006, 7, pp.413-427. We study a variance reduction technique for Monte Carlo estimation of functionals in Markov chains. The method is based on designing sequential control variates using successive approximations of the function of interest V. Regular Monte Carlo estimates have a variance of O(1/N), where N is the number of sample trajectories of the Markov chain. Here, we obtain a geometric variance reduction O(ρ^N) (with ρ<1) up to a threshold that depends on the approximation error V-AV, where A is an approximation operator linear in the values. Thus, if V belongs to the right approximation space (i.e. AV=V), the variance decreases geometrically to zero. An immediate application is value function estimation in Markov chains, which may be used for policy evaluation in a policy iteration algorithm for solving Markov Decision Processes. Another important domain, for which variance reduction is highly needed, is gradient estimation, that is computing the sensitivity ∂αV of the performance measure V with respect to some parameter α of the transition probabilities. For example, in policy parametric optimization, computing an estimate of the policy gradient is required to perform a gradient optimization method. We show that, using two approximations for the value function and the gradient, a geometric variance reduction is also achieved, up to a threshold that depends on the approximation errors of both of those representations.
• Unifying evolutionary dynamics: from individual stochastic processes to macroscopic models
  
  • Champagnat Nicolas
  • Ferrière Régis
  • Méléard Sylvie
  Theoretical Population Biology, Elsevier, 2006, 69 (3), pp.297-321. A distinctive signature of living systems is Darwinian evolution, that is, a propensity to generate as well as self-select individual diversity. To capture this essential feature of life while describing the dynamics of populations, mathematical models must be rooted in the microscopic, stochastic description of discrete individuals characterized by one or several adaptive traits and interacting with each other. The simplest models assume asexual reproduction and haploid genetics: an offspring usually inherits the trait values of her progenitor, except when a mutation causes the offspring to take a mutation step to new trait values; selection follows from ecological interactions among individuals. Here we present a rigorous construction of the microscopic population process that captures the probabilistic dynamics over continuous time of birth, mutation, and death, as influenced by the trait values of each individual, and interactions between individuals. A by-product of this formal construction is a general algorithm for effcient numerical simulation of the individual-level model. Once the microscopic process is in place, we derive different macroscopic models of adaptive evolution. These models differ in the renormalization they assume, i.e. in the limits taken, in specific orders, on population size, mutation rate, mutation step, while rescaling time accordingly. The macroscopic models also differ in their mathematical nature: deterministic, in the form of ordinary, integro-, or partial differential equations, or probabilistic, like stochastic partial differential equations or superprocesses. These models include extensions of Kimura's equation (and of its approximation for small mutation effects) to frequency- and density-dependent selection. A novel class of macroscopic models obtains when assuming that individual birth and death occur on a short timescale compared with the timescale of typical population growth. On a timescale of very rare mutations, we establish rigorously the models of "trait substitution sequences" and their approximation known as the "canonical equation of adaptive dynamics". We extend these models to account for mutation bias and random drift between multiple evolutionary attractors. The renormalization approach used in this study also opens promising avenues to study and predict patterns of life-history allometries, thereby bridging individual physiology, genetic variation, and ecological interactions in a common evolutionary framework. (10.1016/j.tpb.2005.10.004)
  DOI : 10.1016/j.tpb.2005.10.004
• An anti-diffusive scheme for viability problems
  
  • Bokanowski Olivier
  • Martin Sophie
  • Munos Rémi
  • Zidani Hasnaa
  Applied Numerical Mathematics: an IMACS journal, Elsevier, 2006, 56 (9), pp.1147-1162. This paper is concerned with the numerical approximation of viability kernels. The method described here provides an alternative approach to the usual viability algorithm. We first consider a characterization of the viability kernel as the value function of a related optimal control problem, and then use a specially relevant numerical scheme for its approximation. Since this value function is discontinuous, usual discretization schemes (such as finite differences) would provide a poor approximation quality because of numerical diffusion. Hence, we investigate the Ultra-Bee scheme, particularly interesting here for its anti-diffusive property in the transport of discontinuous functions. Although currently there is no available convergence proof for this scheme, we observed that numerically, the experiments done on several benchmark problems for computing viability kernels and capture basins are very encouraging compared to the viability algorithm, which fully illustrates the relevance of this scheme for numerical approximation of viability problems.
• Attainability by simply connected domains of optimal bounds for the polarization tensor
  
  • Ammari Habib
  • Capdeboscq Yves
  • Kang Hyeonbae
  • Kim Eunjoo
  • Lim Mikyoung
  European Journal of Applied Mathematics, Cambridge University Press (CUP), 2006, 17 (2), pp.201--219. The notion of polarization tensor is employed for the derivation of the leading-order boundary perturbations in the steady-state voltage potentials that are due to the presence of conductivity inclusions of small diameter. Recently, Capdeboscq and Vogelius obtained optimal bounds of Hashin-Shtrikman type for the trace of the polarization tensor, showing that every pair satisfying these optimal bounds arises as the eigenvalues of a polarization tensor associated with a coated ellipse. In this paper, we give numerical evidence of the fact that the set of possible polarization tensor eigenvalue pairs can also be obtained using simply connected domains. Our numerical computations are based on a boundary integral method. (10.1017/S0956792506006541)
  DOI : 10.1017/S0956792506006541
• 3D Charge Distributions Along Edges and Corners of Electrodes in SAW Transducers
  
  • Jerez-Hanckes Carlos F.
  • Laude Vincent
  • Lardat Raphael
  • Nédélec Jean-Claude
  , 2006, pp.92-95.
• A bilinear optimal control problem applied to a time dependent Hartree-Fock equation coupled with classical nuclear dynamics
  
  • Baudouin Lucie
  Portugaliae Mathematica, European Mathematical Society Publishing House, 2006, 63 (3), pp.293-325. We study a problem of bilinear optimal control for the electronic wave function of an Helium atom by an external time dependent electric field. The behavior of the atom is modeled by the Hartree-Fock equation, whose solution is the wave function of the electrons, coupled with the classical Newtonian dynamics, corresponding to the motion of the nucleus. We prove the existence of a bilinear optimal control in the case when the position of the nucleus is known and also prove the corresponding optimality condition. Then, we detail the proof of the existence of an optimal control for the coupled system and complete the study giving a formal optimality condition to define the electric control.
• Structural Optimization with FreeFem++
  
  • Allaire Grégoire
  • Pantz Olivier
  Structural and Multidisciplinary Optimization, Springer Verlag, 2006, 32, pp.173-181. The aim of this paper is to show that relatively small, simple and efficient shape optimization routines can be written using the free finite element software \texttt{FreeFem++}.This is illustrated by the implementation of two classical methods: the boundary variation method and the homogenization one.Even though these routines are simple enough so that their implementation can be assigned (partially or totally) as homework to graduate students, they yield results accurate enough to be useful tools for engineers orresearchers.
• Model uncertainty and its impact on the pricing of derivative instruments
  
  • Cont Rama
  Mathematical Finance, Wiley, 2006, 16 (3), pp.519 - 547. Model uncertainty, in the context of derivative pricing, can be defined as the uncertainty on the value of a contingent claim resulting from the lack of precise knowledge of the pricing model to be used for its valuation. We introduce here a quantitative framework for defining model uncertainty in option pricing models. After discussing some properties which a quantitative measure of model uncertainty should verify in order to be useful and relevant in the context of risk measurement and management, we propose a method for measuring model uncertainty which verifies these properties and yields numbers which are comparable to other risk measures and compatible with observations of market prices of a set of benchmark derivatives. We illustrate the difference between model uncertainty and the more common notion of "market risk" through examples. Finally, we illustrate the connection between our proposed measure of model uncertainty and the recent literature on coherent and convex risk measures. (10.1111/j.1467-9965.2006.00281.x)
  DOI : 10.1111/j.1467-9965.2006.00281.x
• Deviation bounds for additive functionals of Markov processes
  
  • Cattiaux Patrick
  • Guillin Arnaud
  , 2006. In this paper we derive non asymptotic deviation bounds for $$\P_\nu (|\frac 1t \int_0^t V(X_s) ds - \int V d\mu | \geq R)$$ where $X$ is a $\mu$ stationary and ergodic Markov process and $V$ is some $\mu$ integrable function. These bounds are obtained under various moments assumptions for $V$, and various regularity assumptions for $\mu$. Regularity means here that $\mu$ may satisfy various functional inequalities (F-Sobolev, generalized Poincaré etc...).
• Subgeometric ergodicity of Markov chains
  
  • Douc Randal
  • Moulines Eric
  • Soulier Philippe
  , 2006, pp.55--64. The goal of this paper is to give a short and self contained proof of general bounds for subgeometric rates of convergence, under practical conditions. The main result whose proof, based on coupling, provides an intuitive understanding of the results of Nummelin and Tuominen (1983) and Tuominen and Tweedie (1994). To obtain practical rates, a very general drift condition, recently introduced in Douc et al (2004) is used.
• High Order Generalized Impedance Boundary Conditions in Electromagnetic Scattering Problems
  
  • Duruflé Marc
  • Haddar Houssem
  • Joly Patrick
  Comptes Rendus. Physique, Académie des sciences (Paris), 2006, 7, pp.533-542. We briefly review the use and the derivation of Generalized Impedance Boundary Conditions (GIBC) in the case of thin dielectric coating and in the case of strongly absorbing medium, within the context of electromagnetic scattering problem at a fixed frequency. We then numerically test the validity and accuracy of these boundary conditions in the case of high absorption. A numerical treatment of the corner singularity is proposed to recover the accuracy of the GIBC for singular geometries.
• A New Domain Decomposition Method for the Compressible Euler Equations
  
  • Dolean Victorita
  • Nataf Frédéric
  ESAIM: Mathematical Modelling and Numerical Analysis, Société de Mathématiques Appliquées et Industrielles (SMAI) / EDP, 2006, 40 (4), pp.689-703. In this work we design a new domain decomposition method for the Euler equations in 2 dimensions. The basis is the equivalence via the Smith factorization with a third order scalar equation to whom we can apply an algorithm inspired from the Robin-Robin preconditioner for the convection-diffusion equation. Afterwards we translate it into an algorithm for the initial system and prove that at the continuous level and for a decomposition into 2 sub-domains, it converges in 2 iterations. This property cannot be preserved strictly at discrete level and for arbitrary domain decompositions but we still have numerical results which confirm a very good stability with respect to the various parameters of the problem (mesh size, Mach number, ....).
• A new linear sampling method for the electromagnetic imagining of buried objects
  
  • Cakoni Fioralba
  • Haddar Houssem
  , 2006, pp.19--30. We present a new linear sampling method for determining the shape of scattering objects imbedded in a known inhomogeneous medium from a knowledge of the scattered electromagnetic field due to a point source incident field at fixed frequency. The method does not require any a prior information on the physical properties of the scattering object and, under some restrictions, avoids the need to compute the Green's tensor for the background medium. (10.1142/9789812773197_0003)
  DOI : 10.1142/9789812773197_0003
• Policy Gradient in Continuous Time
  
  • Munos Rémi
  Journal of Machine Learning Research, Microtome Publishing, 2006, 7, pp.771-791. Policy search is a method for approximately solving an optimal control problem by performing a parametric optimization search in a given class of parameterized policies. In order to process a local optimization technique, such as a gradient method, we wish to evaluate the sensitivity of the performance measure with respect to the policy parameters, the so-called policy gradient. This paper is concerned with the estimation of the policy gradient for continuous-time, deterministic state dynamics, in a reinforcement learning framework, that is, when the decision maker does not have a model of the state dynamics. We show that usual likelihood ratio methods used in discrete-time, fail to proceed the gradient because they are subject to variance explosion when the discretization time-step decreases to 0. We describe an alternative approach based on the approximation of the pathwise derivative, which leads to a policy gradient estimate that converges almost surely to the true gradient when the time-step tends to 0. The underlying idea starts with the derivation of an explicit representation of the policy gradient using pathwise derivation. This derivation makes use of the knowledge of the state dynamics. Then, in order to estimate the gradient from the observable data only, we use a stochastic policy to discretize the continuous deterministic system into a stochastic discrete process, which enables to replace the unknown coefficients by quantities that solely depend on known data. We prove the almost sure convergence of this estimate to the true policy gradient when the discretization time-step goes to zero. The method is illustrated on two target problems, in discrete and continuous control spaces.
• The dressed mobile atoms and ions
  
  • Amour Laurent
  • Grébert Benoît
  • Guillot Jean-Claude
  Journal de Mathématiques Pures et Appliquées, Elsevier, 2006, 86, pp.177-200. We consider free atoms and ions in $\R^3$ interacting with the quantized electromagnetic field. Because of the translation invariance we consider the reduced hamiltonian associated with the total momentum. After introducing an ultraviolet cutoff we prove that the reduced hamiltonian for atoms has a ground state if the coupling constant and the total momentum are sufficiently small. In the case of ions an extra infrared regularization is needed. We also consider the case of the hydrogen atom in a constant magnetic field. Finally we determine the absolutely continuous spectrum of the reduced hamiltonian.
• Weak and Strong Order of Convergence of a Semidiscrete Scheme for the Stochastic Nonlinear Schrodinger Equation
  
  • de Bouard Anne
  • Debussche Arnaud
  Applied Mathematics and Optimization, Springer Verlag (Germany), 2006, 54 (3), pp.369-399. In this article we analyze the error of a semidiscrete scheme for the stochastic nonlinear Schrodinger equation with power nonlinearity. We consider supercritical or subcritical nonlinearity and the equation can be either focusing or defocusing. Allowing sufficient spatial regularity we prove that the numerical scheme has strong order in general and order 1 if the noise is additive. Furthermore, we also prove that the weak order is always 1 (10.1007/s00245-006-0875-0)
  DOI : 10.1007/s00245-006-0875-0