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$

1 Answer 1

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$
5
  • $\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
    Commented Jun 6, 2018 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
    Commented Jun 7, 2018 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
    Commented Jun 7, 2018 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
    Commented Jun 8, 2018 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
    Commented Jun 8, 2018 at 15:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .