Initially Bracketing Minimum for Line Search

Question

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?

Answer 1

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.

Answer 2

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.