Finiteness Principles for Smooth Convex Functions

Abstract

Let $E\subset {\mathbb{R}}^n$ be a compact set, and $f:E\to \mathbb{R}$. How can we tell if there exists a convex extension $F\in C^{1,1}({\mathbb{R}}^n)$ of $f$, i.e. satisfying $F{|}_E=f{|}_E$? Assuming such an extension exists, how small can one take the Lipschitz constant $\text{Lip}(\nabla F):={\sup }_{x,y\in {\mathbb{R}}^n,x\ne y}\frac{|\nabla F(x)-\nabla F(y)|}{|x-y|}$? We provide an answer to these questions for the class of strongly convex functions by proving that there exist constants $k^{\#}\in \mathbb{N}$ and $C>0$ depending only on the dimension $n$, such that if for every subset $S\subset E$, $\#S\le k^{\#}$, there exists an $\eta$-strongly convex function $F^S\in C^{1,1}({\mathbb{R}}^n)$ satisfying $F^S{|}_S=f{|}_S$ and $\text{Lip}(\nabla F^S)\le M$, then there exists an $\frac{\eta }{C}$-strongly convex function $F\in C_c^{1,1}({\mathbb{R}}^n)$ satisfying $F{|}_E=f{|}_E$, and $\text{Lip}(\nabla F)\le C{M}^2/\eta$. Further, we prove a Finiteness Principle for the space of convex functions in $C^{1,1}(\mathbb{R})$ and that the sharp finiteness constant for this space is $k^{\#}=5$.