Using inequalities to determine if grid points (x,y) can be from a convex function

Question

Suppose we have n data points $(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)$. Assume that $y_i\in\mathbb{R},x_i\in\mathbb{R}^p$. What is the set of inequalities that must hold between all of the points if the points are from a convex function (i.e., if $y_i=f(x_i)$ is convex)?

According to the definition of a convex function, it must be true that

$\forall x_j,x_k$ and $\forall t\in[0,1]$,

$f(tx_j + (1-t)x_k)\le tf(x_j)+(1-t)f(x_k)$

but I don't know the true function $f$, except the evaluations on the data points. Further, I don't want to check for all $t$ in an infinite set (I am trying to think practically, if I have data). Is there a way to specify the set of inequalities that must hold in terms of only the $(x_i,y_i)$? I can do this in the case when $p=1$, as follows:

First, I order the $(x_i,y_i)$ such that $x_1\le x_2\le\cdots\le x_n$. Then I need to check the following inequalities, because we need the derivative to be non-decreasing:

$\frac{y_2-y_1}{x_2-x_1}\le \frac{y_3-y_2}{x_3-x_2}$

$\frac{y_3-y_2}{x_3-x_2}\le \frac{y_4-y_3}{x_4-x_3}$

$\vdots$

$\frac{y_{n-1}-y_{n-2}}{x_{n-1}-x_{n-2}}\le \frac{y_n-y_{n-1}}{x_n-x_{n-1}}$

But I am lost for a more general way that I can use for $p>1$. First, I know that I cannot order the $(x_i,y_i)$ as I did above, and second I think I need to compare each point to all the others (as opposed to above, where I just compare to the previous one), but I'm not even sure what the comparison should be.

Answer 1

The case $p = 2$ is covered in https://doi.org/10.1007/PL00005446, Theorems 2 and 3.

According to Theorem 2, you have to check that the point $(x_i, y_i)$ lies below the plane spanned by $(x_j, y_j)$, $(x_k,y_k)$, $(x_l, y_l)$ for all quadruples of indices such that the point $x_i$ lies in the triangle $x_j, x_k, x_l$.

This representation can be reduced (Theorem 3). In fact, it is sufficient to consider all quadruples for which $x_i$ is the only point (among all $x_m$, $m \in \{1,\ldots,n\}\setminus\{j,k,l\}$) in the triangle $x_j, x_k, x_l$.

However, the number of inequalities you have to check grows very fast w.r.t. $n$. In this context you should be aware that Corollary 4 in the above paper is wrong, see Theorem 2.5 in https://doi.org/10.1007/s00211-015-0732-7.

I would guess that the higher-dimensional case is very similar (by using simplices instead of triangles). Also note that your one dimensional observation is an analogy to the case $p = 2$ by using intervals instead of triangles.