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.