Is there a test for convexity?

Question

This is a very heterodox question. But here is the context. I'm programming a computational package, and the user may write/define a cost function freely, e.g. $$ cost(x,y) = e^{|x-y|} (x-y)^2. $$ Now, the algorithm programmed only works if the cost function is convex. Here is where my question comes in. Would there be some kind of test to verify if the function is indeed convex? Mathematically, we can try to manipulate the function in order to verify whether it satisfies the convexity definition, but this scenario does not allow for such approaches. I was thinking for something like "sample some points, calculate the function and verify if the mid point is above the linear interpolation". How many points would be necessary to correctly guess that the function is convex with a certain probability? Any references on this kind of odd question (the probability that a function is convex)?

Answer 1

Heuristic argument to prove that such a probability can’t be defined in a meaningful way.

Let $\Omega$ be the set of maps that can be defined with a program. $\Omega$ is countable infinite. Therefore if $K \subseteq \mathbb R$ is a compact, the subset $\Omega_K \subseteq \Omega$ of continuous maps defined on $K$ is also countable.

Now, to get a probability space $(\Omega_K, \mathcal A, P)$ on $\Omega_K$, we have to define a probability function $P$ on $\Omega_K$. $P$ can’t be constant and different of zero as otherwise the probability of the whole space $\Omega_K$ would be infinite. $P$ can’t either be equal to zero.

Therefore $P$ has to be non constant. You could attach a probability that would depend on the length of the program that defines the function or something similar (and the probability decreases to zero as the length of the program increases)… but then the probability for convexity will depend on your programming language!

Not saying that it is impossible. But rather that it would be rather meaningless.

Then assuming that such a (meaningless) probability has been defined, you raised a second point, about the number of sampling points required to test convexity. You’ll enter here other difficulties. I.e. that the answer depends on the chosen points, and nice topics like that.