# Find the max of a convex function in fewest samples

Suppose there is a convex function, and a certain domain interval. I want to find the max of this function within the interval. The goal is to minimize the number of times the function is evaluated, because evaluating it is expensive.

I can think of a naive solution involving evaluating the function at two points of the interval (thereby partitioning the interval into three sub-intervals) and discarding the edge sub-interval of the point with the lower function value. But, I am not sure whether it's optimal.

• It depends on the function, if the curvature of the function is complicated, for any solution you find, one can come up with a function with curvature complicated enough yet still convex and you will not be able to make a guarantee on the number of samples needed to attain the maxima. – InformedA Oct 17 '14 at 20:07
• Wrong, the above comment is for finding a minima in convex function OR finding maxima in concave function. As stated above, this question can be trivially answered as some one has below. – InformedA Oct 18 '14 at 6:49

## 1 Answer

As the function $f$ is convex, its maximum value in interval $[a,b]$ is either $f(a)$ or $f(b)$. Otherwise, it will violate Jensen's inequality.

• Uhh ohh, you are right. I misremember convex and concave. – InformedA Oct 18 '14 at 6:47
• Dammit, thanks, but I actually meant I have a concave function. I will close this question and ask another one. Thanks. – Philip Oct 18 '14 at 23:51
• Sure. I could be helpful in the concave version, hopefully. BTW, I think it's better to present the question as find the minimum of a convex function. And there should be some pre-existing tools. – Tianren Liu Oct 19 '14 at 1:15