Conditions under which a discretely defined function can be extended convexly

Question

Suppose we have a set of points $u_1,\ldots, u_m \in \mathbb{R}^d$. Suppose $F$ is a function into the reals defined at each of the points $u_i$. My question is how do we know when $F$ is really convex, in the sense that I can find a convex function on $\mathbb{R}^d$ which extends $F$. In 1-dimensional case it's pretty clear that you can check this just by applying a linear interpolation and see that the result is convex but I'm confused about how to do this for higher-dimensional cases. Is there an easy way to check if a function defined on a finite number of points can be described convexly?

Answer 1

A necessary condition is that if $u_i$ is a convex combination $\sum_{j \ne i} c_j u_j$, $c_j \ge 0$, $\sum_{j\ne i} c_j = 1$, then $F(u_i) \le \sum_{j \ne i} c_j F(u_j)$. That is, $(u_i, F(u_i))$ must be on the lower boundary of the convex hull of the points $(u_j, F(u_j))$.

And this is sufficient as well: for $x$ in the convex hull $C$ of the $u_i$, take $F(x) = y$ where $(x,y)$ is on the lower boundary of the convex hull of the $(u_j, F(u_j))$. Take a ball $B$ with $C$ in its interior, and you can define $F$ on $B$ using the convex hull of the $(u_j, F(u_j))$ and $(s,y)$ for $s$ on the boundary of $B$, where $y$ is a sufficiently large constant. And then for $x$ outside $B$, you can take $F(x) = y + r \|x\|$ for sufficiently large $r$.