# Single-variable multimodal derivative-free optimization (for a well-behaved function)

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.

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

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.