9
$\begingroup$

Leafing through a few textbooks, I've noticed that the problem of initially bracketing a minimum during a line search tends be an afterthought (at least in my undergraduate texts). Are there well-established techniques or best practices for this type of problem, or are solutions typically application dependent? Can anyone recommend some references on the topic?

$\endgroup$
9
$\begingroup$

Usually one doubles the initial step until the Goldstein condition is violated or (in a feasible point method) the boundary is reached. Then one has a bracket. (If no such step exists, the objective function is unbounded below.) One can also use less conservative extrapolation procedures, but these require good tuning to be robust enough in a general purpose solver.

$\endgroup$
5
$\begingroup$

In my experience establishing the bracket is very often application-dependent. If you had real constraints or an algebraic derivation for your bracket, you'd use it of course! Usually there's an appeal to either

  • nature this physically makes no sense outside this bracket
  • computability this would be too hard to compute outside of the bracket
  • objective solutions outside of this region are otherwise undesirable.

I'm hoping someone else can come in with a more algorithmic approach, which is what I think you're looking for here.

$\endgroup$
  • $\begingroup$ I think your answer is spot on. For real problems, you almost always have a reasonable first guess for upper and lower bounds of variables. The engine speed in a car can only vary between 0 and 20,000 rpms; the fuel injection rate can only vary between 0 and 10 liters per hour; etc -- in other words, for real problems, you know what values can be. $\endgroup$ – Wolfgang Bangerth Aug 15 '12 at 19:28

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.