4
$\begingroup$

Are there well-established approaches to single-variable multimodal optimization?

Given $f:\mathbb{R}\rightarrow\mathbb{R}$ that:

  • has several local minima within a given range of interest $[a,b]$
  • is quadratic in the neighborhood of local minima

and furthermore given that:

  • $f$ is expensive to evaluate
  • $f'$ is not available

can you recommend an algorithm for finding local minima efficiently?

Vaguely I imagine starting with uniformly spaced samples in $[a,b]$, then sub-dividing the promising intervals, and eventually morphing (suddenly or gradually) into a procedure that fits a parabola to small neighborhoods to converge on the local minima.

Improve this question
$\endgroup$
2
  • $\begingroup$ I suggest taking a look at this question that is not focused on single-variable functions, but certainly gives some general advice and references. $\endgroup$
    – Anton Menshov ♦
    Commented May 18, 2019 at 20:28
  • 1
    $\begingroup$ I feel like you’ll want to do some surrogate based optimization method, whether it’s Bayesian optimization or a Kriging based surrogate optimization. $\endgroup$
    – spektr
    Commented May 19, 2019 at 2:24

1 Answer 1

Reset to default
1
$\begingroup$

To find the minima in an interval, you can use the golden-section search. Basically, it is an iterative process where you divide each interval into 3 parts and discard the left or right part according to the values of the function at the boundaries.

However, since you have multiple minima you can either split the interval $[a; b]$ into $n$ several smaller intervals $[c_j; c_{j+1}]$, with $ a = c_0 < c_1 < \ldots < c_{n-1} < c_n = b $ such that you will only have at most one minimum in each interval (though you may have zero minima in an interval).

Another approach is to find a minimum $m_1$ in the interval $[a; b]$. Then, we split the initial interval into two intervals $[a; m_1)$ and $(m1; b]$, and search for a minima in both (one at a time). Each minimum you find will split the respective interval into two smaller intervals to search for minima. And if you don't find the minimum in the interval $(m_j; m_k)$ you could split it in half and repeat the search. You could stop the iterative process and, thus, splitting each interval if one of the following happens: (1) all the minima are found (in case you know how many exist); (2) the interval amplitude is smaller than a pre-determined value.

Edit: You may also alternate the search for local minima and local maxima, since between two maxima there is at least one minima (and vice-versa).

Improve this answer
$\endgroup$
2
  • $\begingroup$ I had implemented a search that combs the domain and then uses golden-section search for the small intervals, but my concerns are (1) that the initial comb's interval is uniform (It would be rational to sample valleys densely and high terrain more sparsely, as an evolutionary algorithm would.) and (2) that golden-section search doesn't exploit the quadratic nature of local minima neighborhoods to converge more quickly. $\endgroup$
    – Museful
    Commented May 18, 2019 at 22:14
  • $\begingroup$ @Museful Perhaps this page may be helpful. I've also edited my post to recall that it may be interesting to also look for maxima. $\endgroup$
    – Ertxiem - reinstate Monica
    Commented May 18, 2019 at 23:48

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.