Adam M. Oberman

We build convergent discretizations and semi-implicit solvers for the Infinity Laplacian and the game theoretical $p$-Laplacian. The discretizations simplify and generalize earlier ones. We prove convergence of the solution of the Wide Stencil finite difference schemes to the unique viscosity solution of the underlying equation. We build a semi-implicit solver, which solves the Laplace equation as each step. It is fast in the sense that the number of iterations is independent of the problem size. This is an improvement over previous explicit solvers, which are slow due to the CFL-condition.

We consider the problem of approximating the solution of variational problems subject to the constraint that the admissible functions must be convex. This problem is at the interface between convex analysis, convex optimization, variational problems, and partial differential equation techniques. The approach is to approximate the (non-polyhedral) cone of convex functions by a polyhedral cone which can be represented by linear inequalities. This approach leads to an optimization problem with linear constraints which can be computed efficiently, hundreds of times faster than existing methods.

The elliptic Monge-Ampere equation is a fully nonlinear Partial Differential Equation which originated in geometric surface theory, and has been applied in dynamic meteorology, elasticity, geometric optics, image processing and image registration. Solutions can be singular, in which case standard numerical approaches fail. In this article we build a finite difference solver for the Monge-Ampere equation, which converges even for singular solutions. Regularity results are used to select a priori between a stable, provably convergent monotone discretization and an accurate finite difference discretization in different regions of the computational domain. This allows singular solutions to be computed using a stable method, and regular solutions to be computed more accurately. The resulting nonlinear equations are then solved by Newton's method. Computational results in two and three dimensions validate the claims of accuracy and solution speed. A computational example is presented which demonstrates the necessity of the use of the monotone scheme near singularities.

The Convex Envelope of a given function was recently characterized as the solution of a fully nonlinear Partial Differential Equation (PDE). In this article we study a modified problem: the Dirichlet problem for the underlying PDE. The main result is an optimal regularity result. Differentiability ($C^{1,\alpha}$ regularity) of the boundary data implies the corresponding result for the solution in the interior, despite the fact that the solution need not be continuous up to the boundary. Secondary results are the characterization of the convex envelope as: (i) the value function of a stochastic control problem, and (ii) the optimal underestimator for a class of nonlinear elliptic PDEs.

The numerical solution of the elliptic Monge-Ampère Partial Differential Equation has been a subject of increasing interest recently [Glowinski, in 6th International Congress on Industrial and Applied Mathematics, ICIAM 07, Invited Lectures (2009) 155–192; Oliker and Prussner, Numer. Math. 54 (1988) 271–293; Oberman, Discrete Contin. Dyn. Syst. Ser. B 10 (2008) 221–238; Dean and Glowinski, in Partial differential equations, Comput. Methods Appl. Sci. 16 (2008) 43–63; Glowinski et al., Japan J. Indust. Appl. Math. 25 (2008) 1–63; Dean and Glowinski, Electron. Trans. Numer. Anal. 22 (2006) 71–96; Dean and Glowinski, Comput. Methods Appl. Mech. Engrg. 195 (2006) 1344–1386; Dean et al., in Control and boundary analysis, Lect. Notes Pure Appl. Math. 240 (2005) 1–27; Feng and Neilan, SIAM J. Numer. Anal. 47 (2009) 1226–1250; Feng and Neilan, J. Sci. Comput. 38 (2009) 74–98; Feng and Neilan, http://arxiv.org/abs/0712.1240v1; G. Loeper and F. Rapetti, C. R. Math. Acad. Sci. Paris 340 (2005) 319–324]. There are already two methods available [Oliker and Prussner, Numer. Math. 54 (1988) 271–293; Oberman, Discrete Contin. Dyn. Syst. Ser. B 10 (2008) 221–238] which converge even for singular solutions. However, many of the newly proposed methods lack numerical evidence of convergence on singular solutions, or are known to break down in this case. In this article we present and study the performance of two methods. The first method, which is simply the natural finite difference discretization of the equation, is demonstrated to be the best performing method (in terms of convergence and solution time) currently available for generic (possibly singular) problems, in particular when the right hand side touches zero. The second method, which involves the iterative solution of a Poisson equation involving the Hessian of the solution, is demonstrated to be the best performing (in terms of solution time) when the solution is regular, which occurs when the right hand side is strictly positive.

Building Lipschitz extensions of functions is a problem of classical analysis. Extensions are not unique: the classical results of Whitney and McShane provide two explicit examples. In certain cases there exists an optimal extension, which is the solution of an elliptic partial differential equation, the infinity Laplace equation. In this work, we find an explicit formula for a sub-optimal extension, which is an improvement over the Whitney and McShane extensions: it can improve the local Lipschitz constant. The formula is found by solving a convex optimization problem for the minimizing extensions at each point. This work extends a previous solution for domains consisting of a finite number of points, which has been used to build convergent numerical schemes for the infinity Laplace equation, and in Image Inpainting applications.

Certain fully nonlinear elliptic Partial Differential Equations can be written as functions of the eigenvalues of the Hessian. These include: the Monge-Ampère equation, Pucci’s Maximal and Minimal equations, and the equation for the convex envelope. In this article we build convergent monotone finite difference schemes for the aforementioned equations. Numerical results are presented.

We derive a nonlinear partial differential equation for the convex envelope of a given function. The solution is interpreted as the value function of an optimal stochastic control problem. The equation is solved numerically using a convergent finite difference scheme.