How to examine the convexity of a complex function numerically?

Question

I have a function which does not have a closed form . Large numerical effort should be done to evaluate the function for even a single point. How can I examine the convexity of my function over the whole domain of function with minimum computational load? some extra assumption is that the function is continuous and almost every where differentiable!

Answer 1

If your function was strictly convex and $C^3$ (let's say on a compact interval $I$) and you had bounds on the third derivative there, it might be possible to prove its convexity on $I$ by evaluating it at sufficiently many points of $I$. If not, it's impossible to distinguish any convex function from one whose second derivative has a narrow "blip" taking it below zero between some of the points where you evaluated it.

EDIT: Here's what I had in mind. Suppose you know that $|f'''| \le B$ on interval $I$. Evaluate $f$ at points $x_j = x_0 + j \delta$, $j = 0 \ldots n$ so that $I = [x_0, x_n]$, and compute $L_j = f(x_{j-1}) - 2 f(x_{j}) + f(x_{j+1})$, $j = 1 \ldots n-1$.
Note that $L_j = \int_{x_{j-1}}^{x_{j+1}} (\delta - |t - x_j|) f''(t)\; dt$. If $x_{j-1} \le s \le x_{j+1}$, since $f''(s) \ge f''(t) - B |t - s|$ we have $$ \delta^2 f''(s) \ge L(j) - B \int_{x_{j-1}}^{x_{j+1}} (\delta - |t - x_j|)|t - s|\; dt \ge L(j) - B \delta^3$$ since $$ \max_{s \in [-1,1]} \int_{-1}^1 (1 - |t|)|t-s|\; dt = 1$$ Thus if $L_j \ge B \delta^3$ for all $j = 1 \ldots n-1$ you can conclude that $f'' \ge 0$ and $f$ is convex. On the other hand, if some $L_j < 0$, $f$ is not convex.

If $f''$ is bounded away from $0$, this method is guaranteed to succeed as long as $\delta$ is sufficiently small.
In fact if $f'' \ge c > 0$ on $I$, we will have $L_j \ge c \delta^2$, so we just need $0 < \delta < c/B$. Note that you don't need to know $c$ beforehand, you just keep taking smaller and smaller $\delta$ until you succeed.