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?
Asked
Active
Viewed 1,171 times
2 Answers
9
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.
Arnold Neumaier
- 11,318
- 20
- 47
5
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.
Aron Ahmadia
- 6,951
- 4
- 34
- 54
-
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. – Wolfgang Bangerth Aug 15 '12 at 19:28