6
$\begingroup$

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:

enter image description here

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?
Improve this question
$\endgroup$
1
  • $\begingroup$ 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 ? $\endgroup$
    – denis
    Commented Aug 8, 2018 at 14:48

2 Answers 2

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • $\begingroup$ Thanks - do you have a link/reference where this is explained in a little more detail? $\endgroup$
    – dr.blochwave
    Commented Jun 5, 2015 at 12:07
  • $\begingroup$ @blochwave: No; Isn't it self-explaining? These sort of tricks are at best in little remarks scattered through papers with applications. $\endgroup$
    – Arnold Neumaier
    Commented Jun 5, 2015 at 12:14
  • $\begingroup$ Sure - I do understand it, just curious how much has been written about it. Thanks! $\endgroup$
    – dr.blochwave
    Commented Jun 5, 2015 at 12:17
  • $\begingroup$ @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? $\endgroup$
    – m4r35n357
    Commented Feb 19 at 13:12
  • 1
    $\begingroup$ 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. $\endgroup$
    – Arnold Neumaier
    Commented Feb 19 at 16:26
4
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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 . . . ? $\endgroup$
    – m4r35n357
    Commented Feb 19 at 14:02
  • $\begingroup$ @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. $\endgroup$
    – Wolfgang Bangerth
    Commented Feb 19 at 16:16
  • $\begingroup$ 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? $\endgroup$
    – m4r35n357
    Commented Feb 19 at 16:18
  • $\begingroup$ @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? $\endgroup$
    – Wolfgang Bangerth
    Commented Feb 19 at 23:33
  • $\begingroup$ 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? $\endgroup$
    – m4r35n357
    Commented Feb 20 at 9:26

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.