Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
    
    
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
1  
@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
add comment

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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