4
$\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?
$\endgroup$
  • $\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 Aug 8 '18 at 14:48
5
$\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.

$\endgroup$
  • $\begingroup$ Thanks - do you have a link/reference where this is explained in a little more detail? $\endgroup$ – dr.blochwave Jun 5 '15 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 Jun 5 '15 at 12:14
  • $\begingroup$ Sure - I do understand it, just curious how much has been written about it. Thanks! $\endgroup$ – dr.blochwave Jun 5 '15 at 12:17
3
$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.