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?
Checking convexity is NP hard in general so in practice it may not be possible to do what you want.
The Mprobe tool
http://www.sce.carleton.ca/faculty/chinneck/mprobe.html
and the information about it may be helpful.
Thank you very much for your answer. do you know any paper that address this issue?
is it still NP hard to find the convexity of a function when it is smooth and differentiable?
In "Computing proximal points of nonconvex functions", my co-author and I discuss an algorithm that, as a side effect, required the computation of the minimum convexification parameter required to make the function locally convex. The method needs function and (sub-)gradient values. The algorithm might give a reasonable heuristic. The algorithm could probably be adapted to the non-gradient case using simplex gradients.
Thank you warren, so with your approach the function doesn't need to be smooth right?
Do you have any estimate of the complexity of your approach ?
Regarding smoothness, no you do not need f to be smooth. However, you do need access to the generalized gradients
Regarding complexity, the approach would be heuristic, so I'm not sure complexity analysis makes sense. I certainly have never done it.
Thank you again.
currently i have started to read two of you papers
1-the optimal value and optimal solution of the proximal average of convex functions
2-computing proximal point of nonconvex functions.
actually the idea of proximal average, point and mapping seems to be useful and very near to what i am looking for. have you ever seen any thing like the following optimization problem :
F(x)= max_{y_1+y_2...+y_n
Examining the monotonicity of a function is insufficient. Log(x) is monotonous and concave, |x| or x^2 are not monotonous and nevertheless convex.
Even if your function is smooth, if you do not have semilocal or global information for the function, proving convexity by function evaluation alone is only possible if your algorithm eventually evaluates the function on a dense subset of R^n.
However, why do you need to prove convexity of the function?
Actually, the problem you cited has a separable objective function with a single linear constraint (actually: did you miss y_i >= 0, or can the y_i become negative?). The function F(x) is monotone and univariate. Do you want to optimize it, or do you want to compute some of its values? What size is N=n? Anyway, you can compute R for as many points as you need/like and test Jensen's inequality for them. This is more or less the best you can do if the function is non-differentiable.
In a 3X3 Hessian matrix, 1st order minors are 0, positive and negative; 2nd order minors are negative, 0 and negative; and 3rd order minor is positive. Then is it convex/ quasi-convex or not?
@Sutanu Gosh
The function has no useful convexity properties whatsoever. I assume that the information on the 3x3 Hessian is over a certain area. If it were convex its Hessian would be positive semidefinite, and then all minors would be nonnegative. For testing quasiconvexity/-concavity you would need to check the bordered Hessians of the function. However, since there are nonquasiconvex/-concave functions that have the proposed Hessian structure (even a quadratic function that is indefinite) that implies that in general no useful convexity properties can be deduced.
- Badges
- Science topic
- Similar topics
- Names