Let $f(t)$ be a function from $(0,1)$ to $\mathbb R$. If $f$ is strictly convex, then finding the minimizer is an easy task. For example, newton's method would be able to do the job.

However, if my function is not convex, but more like the followingenter image description here (please forgive my poor drawing skill...)

That is, the function is "almost" convex but with small perturbation. Then, is there an efficient algorithm which can find an "good enough" minimizer?

PS: the existence of minimizer of $f(t)$ is assumed.

any ideas or references would be really welcome.

Thank you!

  • $\begingroup$ If your function is of bounded variation (and if you can quantify that variation) then you can look into so-called interval methods which (as long as the bounds are good) often allow for relatively efficient and robust pruning. $\endgroup$ – Steven Stadnicki Sep 22 '16 at 23:55
  • $\begingroup$ @StevenStadnicki Thank you sir. I googled the interval methods, does this link leads to the method you want to refer to? and why bounded variation is important? thank you! en.wikipedia.org/wiki/Interval_arithmetic $\endgroup$ – JumpJump Sep 22 '16 at 23:58
  • $\begingroup$ That's at the heart of those methods, though it's more about the techniques in general than their use in this particular problem. And without bounded variation, it's effectively impossible to refine the intervals down to make any actual progress on them. $\endgroup$ – Steven Stadnicki Sep 23 '16 at 1:41

You could try stochastic optimization methods. The rough idea is to leverage noise to efficiently explore the landscape of $f(t)$. To quote from the linked article, the injected randomness may enable the method to escape a local optimum and eventually to approach a global optimum.

To illustrate this point, suppose you knew that the only point where $f'(t)=0$ is at the minimizer, then you could use a numerical solution to the SDE: $$ d Y = - f'(Y) dt + f'(Y) dW $$ to find the minimizer. Here $W$ is a standard Brownian motion. Note that this SDE has a fixed point at the minimizer, and away from the minimizer it efficiently explores $f(t)$.

As a concrete test, consider $f(x) = 1/2 (x-1/2)^2 + \epsilon \cos(10 x \pi)$, which has a global minimum at $x=1/2$ as shown in the figure below with $\epsilon=0.01$. Starting from the initial condition $0.92$ the method described above converges like a charm to the minimum at $0.5$ in just $32$ steps despite the fact that $f(t)$ is a bit bumpy. enter image description here The dots in this figure represent the points along a numerical solution of the SDE by the simple Euler-Maruyama scheme.


How abou trying to apply the Golden Search algorithm?

  • $\begingroup$ I used this for a "almost unimodal" function like the one drawn and it seems to do a reasonable job in practice. Since it uses large steps at the beginning it tends to do well in the first iterations, descending towards the true minimum. Once it gets close, however, it only takes a single sample that points the "wrong way" and it will narrow in on the wrong end of the curve. How soon that happens (and if it happens at all) depends a lot on how flat the function is near the true minimum - the flatter, the worse off you are. In my cases, I added a supplementary brute force search to refine... $\endgroup$ – BeeOnRope Dec 6 '16 at 21:22

If you are interested in complexity results, I advice you to look at this paper https://arxiv.org/abs/1501.07242 by Belloni, Liang, Narayanan and Rakhlin. I think their results are nearly optimal when the required accuracy $\epsilon\to 0$; however, their analysis might be overly complicated for your case, as it is suited for higher dimensional settings.

  • $\begingroup$ How does one verify that a given function satisfies their hypotheses, i.e., can be approximated arbitrarily/uniformly well by a Lipschitz, convex function? $\endgroup$ – Nawaf Bou-Rabee Oct 9 '16 at 17:44
  • $\begingroup$ Just to clarify: the method does not require arbitrary approximation to a Lipschitz convex function: $\epsilon$ is a parameter, which may be large or small. To my understanding, even deciding convexity is a hard problem, so there is no way to computationally verify almost-convexity either. The natural application of this setup (and the only one I am aware of) is a convex Lipschitz objective and optimization via evaluations with additive noise (so-called stochastic zero order convex optimization). $\endgroup$ – Cristóbal Guzmán Oct 11 '16 at 0:55
  • $\begingroup$ Thanks for your clarification and for sharing this interesting paper, even though its assumptions may be tricky to verify in practice. $\endgroup$ – Nawaf Bou-Rabee Oct 11 '16 at 3:35

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.