1
$\begingroup$

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.

$\endgroup$
2
  • 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
    Commented Oct 17, 2014 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
    Commented Oct 18, 2014 at 6:49

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Uhh ohh, you are right. I misremember convex and concave. $\endgroup$
    – InformedA
    Commented Oct 18, 2014 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
    Commented Oct 18, 2014 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$ Commented Oct 19, 2014 at 1:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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