4
$\begingroup$

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!

Improve this question
$\endgroup$
3
  • $\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
    Commented Sep 22, 2016 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
    Commented Sep 22, 2016 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
    Commented Sep 23, 2016 at 1:41

3 Answers 3

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
6
$\begingroup$

How abou trying to apply the Golden Search algorithm?

Improve this answer
$\endgroup$
1
  • $\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
    Commented Dec 6, 2016 at 21:22
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Oct 9, 2016 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
    Commented Oct 11, 2016 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
    Commented Oct 11, 2016 at 3:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .