Computing minimal interpolants in $C^{1,1}({\mathbb{R}}^d)$

Abstract

We consider the following interpolation problem. Suppose one is given a finite set $E\subset {\mathbb{R}}^d$, a function $f:E\to \mathbb{R}$, and possibly the gradients of $f$ at the points of $E$. We want to interpolate the given information with a function $F\in C^{1,1}({\mathbb{R}}^d)$ with the minimum possible value of $\mathrm{Lip}(\nabla F)$. We present practical, efficient algorithms for constructing an $F$ such that $\mathrm{Lip}(\nabla F)$ is minimal, or for less computational effort, within a small dimensionless constant of being minimal.

41 pages, 6 figures. Replaces arXiv:1307.3292. v2: Minor edits, formatting changed. v3: Revised version, which includes numerous updates, corrections and edits for clarification. v4: Minor edits. Software available at: https://github.com/matthew-hirn/C-1-1-Interpolation