# How to examine the convexity of a complex function numerically?

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!

-
this paper is a very narrow example sorry. –  behrad mahboobi Oct 2 '13 at 21:44
Deciding complexity for polynomial functions is known to be NP-hard problem (in number of terms of the polynomial), so for all practical purposes your complicated function is probably so too. If all you have is a black box function, you might want to try branch and bound type of methods. –  Piyush Grover Oct 2 '13 at 22:04
actually i know my function is continuous and almost everywhere differentiable ! does that help to reduce the complexity load? –  behrad mahboobi Oct 2 '13 at 22:09
@behradmahboobi: a convex function defined over an open domain, I believe, is always continuous and a.e. differentiable. Thus, the mentioned properties will not contribute anything new to the problem. –  SashaKolpakov Oct 2 '13 at 23:08

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.

-
you have assumed that the function is strictly convex at the first like of your post!! if it is strictly convex then it is convex too so why do we need third derivative in class $C^3$! –  behrad mahboobi Oct 4 '13 at 12:31
Actually strictly convex is not enough, you need the second derivative bounded away from $0$. –  Robert Israel Oct 4 '13 at 15:28
strongly or strictly convexity always results in convexity. –  behrad mahboobi Oct 5 '13 at 6:37
But you will have a hard time trying to prove its convexity numerically. –  Robert Israel Oct 6 '13 at 6:43