One-Dimensional Numerical Algorithms for Gradient Flows in the p-Wasserstein Spaces

We numerically approximate, on the real line, solutions to a large class of parabolic partial differential equations which are “gradient flows” of some energy functionals with respect to the L ^p -Wasserstein metrics for all p>1. Our method relies on variational principles involving the optimal transport problem with general strictly convex cost functions.     

Contraction mappings underlying undiscounted Markov decision problems

This paper is concerned with the properties of the value-iteration operator0 which arises in undiscounted Markov decision problems. We give both necessary and sufficient conditions for this operator to reduce to a contraction operator, in which case it is easy to show that the value-iteration method exhibits a uniform geometric convergence rate. As necessary conditions we obtain a number of important characterizations of the chain and periodicity structures of the problem, and as sufficient conditions, we give a general “scrambling-type” recurrency condition, which encompasses a number of important special cases. Next, we show that a data transformation turns every unichained undiscounted Markov Renewal Program into an equivalent undiscounted Markov decision problem, in which the value-iteration operator is contracting, because it satisfies this “scrambling-type” condition. We exploit this contraction property in order to obtain lower and upper bounds as well as variational characterizations for the fixed point of the optimality equation and a test for eliminating suboptimal actions.     

Domain perturbations and estimates for the solutions of second order elliptic equations

We study the dependence of the variational solution of the inhomogeneous Dirichlet problem for a second order elliptic equation with respect to perturbations of the domain. We prove optimal L² and energy estimates for the difference of two solutions in two open sets in terms of the “distance” between them and suitable geometrical parameters which are related to the regularity of their boundaries. We derive such estimates when at least one of the involved sets is uniformly Lipschitz: due to the connection of this problem with the regularity properties of the solutions in the L² family of Sobolev–Besov spaces, the Lipschitz class is the reasonably weakest one compatible with the optimal estimates.     

A Note on the Variational Formalism for Sloshing with Rotational Flows in a Rigid Tank with Unprescribed Motion

Ukrainian Mathematical Journal - The Bateman–Luke-type variational formulation of the free-boundary “sloshing” problem is generalized to the case of irrotational flows and...     

A preconditioner for a kind of coupled FEM-BEM variational inequality

In this paper we are concerned with a kind of nonlinear transmission problem with Signorini contact conditions. This problem can be described by a coupled FEM-BEM variational inequality. We first develop a preconditioning gradient projection method for solving the variational inequality. Then we construct an effective domain decomposition preconditioner for the discrete system. The preconditioner makes the coupled inequality problem be decomposed into an equation problem and a “small” inequality problem, which can be solved in parallel. We give a complete analysis to the convergence speed of this iterative method.     

Genericity and Hölder Stability in Semi-Algebraic Variational Inequalities

The aim of this paper is twofold. We first present generic properties of semi-algebraic variational inequalities: “typical” semi-algebraic variational inequalities have finitely many solutions, around each of which they admit a unique “active manifold” and such solutions are nondegenerate. Second, based on these results, we offer Hölder stability, upper semi-continuity, and lower semi-continuity properties of the solution map of parameterized variational inequalities.     

Well Posed Variational Problems and Friedrichs Extensions

In this paper the concept of well posed variational problem is studied for the pair (P, F_f where P is a multivoque operator from B(P) c X into 2 X and 3,. is a convex functiont, Convenient hypotheses show that if the variational problem for the pair (P, 3 p) is well will then P can be extended up to a maximal monotone and surjective operator. Several applitint A (“temperature control” included) are also considered.     

Min–max formulæ for the speeds of pulsating travelling fronts in periodic excitable media

This paper is concerned with some nonlinear propagation phenomena for reaction–advection–diffusion equations in a periodic framework. It deals with travelling wave solutions of the equation $u_t =\nabla\cdot(A(z)\nabla u)\;+q(z)\cdot\nabla u+\,f(z,u),\qquad t\in\mathbb{R},\quad z\in\Omega,$ propagating with a speed c. In the case of a “combustion” nonlinearity, the speed c exists and it is unique, while the front u is unique up to a translation in t. We give a min–max and a max–min formula for this speed c. On the other hand, in the case of a “ZFK” or a “KPP” nonlinearity, there exists a minimal speed of propagation c*. In this situation, we give a min–max formula for c*. Finally, we apply this min–max formula to prove a variational formula involving eigenvalue problems for the minimal speed c* in the “KPP” case.     

A reduced theory for thin‐film micromagnetics

Micromagnetics is a nonlocal, nonconvex variational problem. Its minimizer represents the ground‐state magnetization pattern of a ferromagnetic body under a specified external field. This paper identifies a physically relevant thin‐film limit and shows that the limiting behavior is described by a certain “reduced” variational problem. Our main result is the Γ‐convergence of suitably scaled three‐dimensional micromagnetic problems to a two‐dimensional reduced problem; this implies, in particular, convergence of minimizers for any value of the external field. The reduced problem is degenerate but convex; as a result, it determines some (but not all) features of the ground‐state magnetization pattern in the associated thin‐film limit. © 2002 Wiley Periodicals, Inc.     

Numerical analysis of generalised max-plus eigenvalue problems

This paper is concerned with the deterministic discrete-time infinite horizon optimisation problem on a compact metric space with an average cost criterion involving two functions K (the “cost”) and T (the “time”). Firstly, we collect the different characterisations of the value λ in terms of generalised max-plus eigenvalue problem and in terms of linear programming. Secondly, we prove an error bound on λ when the space is discretised.     

Gray codes in graphs of subsets

Let G(n,k) be a graph whose vertices are the k-element subsets of an n-set represented as n-tuples of “O's” and “1's” with k “1's”. Two such subsets are adjacent if one can be obtained from the other by switching a “O” and a “1” which are in adjacent positions, where the first and nth positions are also considered adjacent. The problem of finding hamiltonian cycles in G(n,k) is discussed. This may be considered a problem of finding “Gray codes” of the k-element subsets of an n-set. It is shown that no such cycle exists if n and k are both even or if k=2 and n?7 and that such a cycle does exist in all other cases where k?5.     

Bifurcation problems for equations of elliptic type with discontinuous nonlinearities

We consider the problem of the existence of semiregular solutions to the main boundary-value problems for second-order equations of elliptic type with a spectral parameter and discontinuous nonlinearities. A variational method is used to obtain the theorem on the existence of solutions and properties of the “separating” set for the problems under consideration. The results obtained are applied to the Goldshtik problem.     

Values and cores of fuzzy games with infinitely many players

The problem of the existence ofvalues (FA-valued, linear, positive, symmetric and efficient operators) on symmetric spaces of “fuzzy games” (that is, ideal set functions of bounded variation) arises naturally from [8], [18], [23] and [2], [3], [4] where it is implicitely approached for technical purposes. In our present work, this problem is approached in itself for the main reason that it is essentially related with the problem of the existence of significant countable additive measures lying in the cores of the “market games”. In fact, it is shown here that there exists a continuous value on the closed subspacebv′ICA ofIBV spanned by thebv′ functions of “fuzzy probability measures” ([9]), this values is “diagonal” onpICA, the closed subspace ofbv′ICA spanned by the natural powers of the fuzzy measures and this is used to prove the main result stating that the cooperative markets contained inpICA have unique fuzzy measures in their cores which are exactly the corresponding diagonal values. This result is of interest because it is providing a tool of determiningCA measures lying in the cores of large classes of games which are not necessarily “non-atomic” and, specially, because it is opening a way toward a new approach of the “Value Equivalence Principle” for differentiable markets with a continuum of traders which are not “perfectly competitive”.     

Problem solving in the United States, 1970–2008: research and theory, practice and politics

Problem solving was a major focus of mathematics education research in the US from the mid-1970s though the late 1980s. By the mid-1990s research under the banner of “problem solving” was seen less frequently as the field’s attention turned to other areas. However, research in those areas did incorporate some ideas from the problem solving research, and that work continues to evolve in important ways. In curricular terms, the problem solving research of the 1970s and 1980s (see, e.g., Lester in J Res Math Educ, 25(6), 660–675, 1994, and Schoenfeld in Handbook for research on mathematics teaching and learning, MacMillan, New York, pp 334–370, 1992, for reviews) gave birth to the “reform” or “standards-based” curriculum movement. New curricula embodying ideas from the research were created in the 1990s and began to enter the marketplace. These curricula were controversial. Despite evidence that they tend to produce positive results, they may well fall victim to the “math wars” as the “back to basics” movement in the US is revitalized.     

Stochastic variational inequalities: single-stage to multistage

Variational inequality modeling, analysis and computations are important for many applications, but much of the subject has been developed in a deterministic setting with no uncertainty in a problem’s data. In recent years research has proceeded on a track to incorporate stochasticity in one way or another. However, the main focus has been on rather limited ideas of what a stochastic variational inequality might be. Because variational inequalities are especially tuned to capturing conditions for optimality and equilibrium, stochastic variational inequalities ought to provide such service for problems of optimization and equilibrium in a stochastic setting. Therefore they ought to be able to deal with multistage decision processes involving actions that respond to increasing levels of information. Critical for that, as discovered in stochastic programming, is introducing nonanticipativity as an explicit constraint on responses along with an associated “multiplier” element which captures the “price of information” and provides a means of decomposition as a tool in algorithmic developments. That idea is extended here to a framework which supports multistage optimization and equilibrium models while also clarifying the single-stage picture.     

Solution dependence on initial conditions in differential variational inequalities

In the first part of this paper, we establish several sensitivity results of the solution x(t, ξ) to the ordinary differential equation (ODE) initial-value problem (IVP) dx/dt = f(x), x(0) =  ξ as a function of the initial value ξ for a nondifferentiable f(x). Specifically, we show that for $\Xi_T \equiv \{\,x(t,\xi^0): 0 \leq t \leq T\,\}$ , (a) if f is “B-differentiable” on $\Xi_T$ , then so is the solution operator x(t;·) at ξ⁰; (b) if f is “semismooth” on $\Xi_T$ , then so is x(t;·) at ξ⁰; (c) if f has a “linear Newton approximation” on $\Xi_T$ , then so does x(t;·) at ξ⁰; moreover, the linear Newton approximation of the solution operator can be obtained from the solution of a “linear” differential inclusion. In the second part of the paper, we apply these ODE sensitivity results to a differential variational inequality (DVI) and discuss (a) the existence, uniqueness, and Lipschitz dependence of solutions to subclasses of the DVI subject to boundary conditions, via an implicit function theorem for semismooth equations, and (b) the convergence of a “nonsmooth shooting method” for numerically computing such boundary-value solutions.     

Estimation and detection of high-variable functions from Sloan—Woźniakowski space

The major difficulty arising in statistics of multi-variable functions is “the curse of dimensionality”: the rates of accuracy in estimation and separation rates in detection problems behave poorly when the number of variables increases. This difficulty arises for most popular functional classes such as Sobolev or Hölder balls.In this paper we consider functional classes of a new type, first introduced by Sloan and Wo?niakowski in 1998. We consider balls F _σ,s in a “Sloan—Wo?niakowski” or “weighted Sobolev” space characterized by two parameters: σ > 0 is a “smoothness” parameter, and s > 0 determines the weight sequence which describes “importance” of the variables. Previously Kuo and Sloan [18] used the spaces of similar structure to address the problem of numerical integration.For the classes F _σ,s we show that in the white Gaussian noise model, the separation rates in detection are similar to those for one-variable functions of smoothness σ* = min(s,σ) regardless of the original problem dimension; thus the curse of dimensionality is “lifted”. Similar results hold for the estimation problem.The studies are based on known results for estimation and detection problems for ellipsoids. Using these results, the asymptotics in the problems are determined by asymptotics of “distribution of coefficients” of ellipsoids. The key point of the paper is the study of these asymptotics for the balls F _σ,s .     

On approximation of approximately linear mappings by linear mappings

Assume A is a normed linear space, B is a Banach space, and f: A → B is a mapping “approximately linear.” We solve the following Ulam problem: “Give conditions in order for a linear mapping near an approximately linear mapping to exist.”     

Asymptotic solution of a singularly perturbed optimal control problem related to the reconstruction of a defective curve

The introduction of “cheap” controls for minimizing the simplest energy functional in an optimal control problem related to the reconstruction of a defective curve necessitates solving a singularly perturbed variational problem with fixed time and fixed ends. The construction of a uniform zero asymptotic approximation to the optimal control in the latter problem permits one to conclude that the optimal trajectories in the original optimal control problem combine a uniform motion in the interior of the time interval with rapid transition layers at the boundaries of the control interval.     

Rectilinear line segment intersection,layered segment trees,and dynamization

The aim of the present paper is to provide an efficient solution to the following problem: “Given a family of n rectilinear line segments in two-space report all intersections in the family with a query consisting of an arbitrary rectilinear line segment.” We provide an algorithm which takes O(nlog₂n) preprocessing time, o(nlog₂n) space and O(log₂n + k) query time, where k is the number of reported intersections. This solution serves to introduce a powerful new data structure, the layered segment tree, which is of independent interest. Second it yields, by way of recent dynamization techniques, a solution to the on-line version of the above problem, that is the operations INSERT and DELETE and QUERY with a line segment are allowed. Third it also yields a new nonscanning solution to the batched version of the above problem. Finally we apply these techniques to the problem obtained by replacing “line segment” by “rectangle” in the above problem, giving an efficient solution in this case also.