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.

  • 1
    $\begingroup$ 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. $\endgroup$ – InformedA Oct 17 '14 at 20:07
  • $\begingroup$ 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. $\endgroup$ – InformedA Oct 18 '14 at 6:49

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.

  • $\begingroup$ Uhh ohh, you are right. I misremember convex and concave. $\endgroup$ – InformedA Oct 18 '14 at 6:47
  • $\begingroup$ Dammit, thanks, but I actually meant I have a concave function. I will close this question and ask another one. Thanks. $\endgroup$ – Philip Oct 18 '14 at 23:51
  • $\begingroup$ 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. $\endgroup$ – Tianren Liu Oct 19 '14 at 1:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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