1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you. I am having trouble thinking in more dimensions, and how to represent e.g. triangles with inequalities. Can you write out the inequalities explicitly for the case of p=2 (e.g. if n = 5, or whatever you think is best)? I think that can really help me. $\endgroup$ – Xu Wang Jun 6 '18 at 17:06
  • $\begingroup$ For each triple of indices $(j,k,l)$, the points $(x_j, y_j)$, $(x_k, y_k)$ and $(x_l, y_l)$ define a unique affine function. Then, if $x_i$ lies in the triangle $x_j, x_k, x_l$, you have to check that the value of the affine function at $x_i$ is above $y_i$. It is not hard to express this with formulas and I won't do it. $\endgroup$ – gerw Jun 7 '18 at 6:28
  • $\begingroup$ Thank you for adding those specifications. I'm understanding more little by little. So for each triple of indices, I need to check that all of the other $x_i$ that lie within the triangle. So the maximum number of checks would be something like (n choose 3)*(n-3). For the arbitrary case of n=5, this would be 20. Of course that is a maximum and many of the 20 checks would not be necessary because many of the points would not fall in the triangles. Is what I said made sense? $\endgroup$ – Xu Wang Jun 7 '18 at 15:37
  • $\begingroup$ Yes, this is true. It is even sufficient to check those triangles which contain exactly one other point, see Theorem 3 in the paper. This will still be a huge number if you have a moderate amount of points. $\endgroup$ – gerw Jun 8 '18 at 6:29
  • $\begingroup$ Thank you for extra clarifying. That helps a lot and motivates me to study more to understand the technicalities of the theorems. I hope to get there someday. $\endgroup$ – Xu Wang Jun 8 '18 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.