# Derivative-free optimization of function with a flat region

I'm attempting derivative-free minimization of, essentially, a black-box function in one dimension. Up to now I've been using BOBYQA as implemented in NLopt. The shape of the function looks like this:

Clearly, giving a good initial guess will help immensely here, as I can avoid the nasty flat region to the right of the graph. However, sometimes a good initial guess is unavailable, and it can end up in the flat region and hence never find the minima.

• Are there any tips/tricks for getting out/avoiding the flat region at all?
• Would a simple Fibonacci / Golden Section search be any better?
• Or would my time be better spent on working out good initial guesses?
• 1) BOBYQA is sensitive to initstep / stepsizes $\rho_t$: "if you rescale the objective function then you are effectively changing the initial rho. This changes the convergence rate ..." -- S.G.Johnson. 2) try Py-BOBYQA ? Commented Aug 8, 2018 at 14:48

The following works in any dimension:

If you have a poor initial guess $x_0$ only (but outside the completely flat region), minimize $f(x)+c_k||x-x_k||^2$ for $k=0$ with some small $c_0$, call the result $x_1$, and iterate with a strongly decreasing sequence of $c_k$'s. In many cases $c_1=0$ will already work.

• Thanks - do you have a link/reference where this is explained in a little more detail? Commented Jun 5, 2015 at 12:07
• @blochwave: No; Isn't it self-explaining? These sort of tricks are at best in little remarks scattered through papers with applications. Commented Jun 5, 2015 at 12:14
• Sure - I do understand it, just curious how much has been written about it. Thanks! Commented Jun 5, 2015 at 12:17
• @ArnoldNeumaier Must admit, I don't get it at all ;) Firstly, surely a guess outside the completely flat region is a "good initial guess", rendering the method unnecessary? Secondly, I can't see what the method is doing! Can you give any hints? Commented Feb 19 at 13:12
• Yes. The point of the regularization is just to ensure that when you start at a nearly flat point, your root finder (e.g., Newton's method) will not overshoot and attempt to try a very negative value next. As long as there is a numerically perceptible slope, there will be progress. Commented Feb 19 at 16:26

In your particular case, you could consider transforming the $x$ variable by replacing the problem by the following: find $y$ so that $f(e^y)$ is minimal. In essence, you're compressing the long tail to the right and thereby make its gradient steeper.

• That is an interesting approach, I guess whether it works depends on "how flat" the flat part is. I have a feeling that it will fail if the function is "truly flat", as the "expansion" will be flat also . . . ? Commented Feb 19 at 14:02
• @m4r35n357 As is universally the case, if you know something about the function you're dealing with, put that into the formulation. If you know that your problem has a double-exponential tail, use $x \to e^{(e^y)}$ as your substitution. Commented Feb 19 at 16:16
• I am frequently puzzled by the level of a priori knowledge needed to solve many optimization problems ;) Why not just avoid the flat bit altogether if you know it is there? Commented Feb 19 at 16:18
• @m4r35n357 No, not necessary. You can just make algorithms more efficient if you know something about the problem. As for your question: "Why not just avoid the flat bit altogether if you know it is there?" If the function you're trying to minimize is given as a function with a number of parameters, and all you're given is a starting point, how do you tell that you're in the flat region? How do you know that for the given set of parameters, the function even has a flat region? Commented Feb 19 at 23:33
• That does not answer my question. I ask in another way, how do you mitigate (whether exponentially or otherwise) for a "troublesome" region that you don't even know is there? Commented Feb 20 at 9:26