Unconstrained Minimization Techniques - Line Search Options

SEPATH offers several line search options:

  1. A simple stephalving approach (but with user adjustable parameters). In this approach, lk is set at 1 at the beginning of each iteration. If an acceptable function value is not found, lk is multiplied by a "stephalving fraction" between zero and 1, and the discrepancy function is recalculated. The process continues until an acceptable discrepancy function is found, or a maximum number of "stephalves" has occurred. In SEPATH both the stephalving fraction and the maximum number of stephalving operations is user selectable. For further details see the SEPATH command reference.
  2. A cubic interpolation procedure (the default). This procedure uses the previous function evaluation information during a particular iteration to attempt to pinpoint, quickly, a reasonably close approximation to the "best" lk. SEPATH uses the algorithm A6.3.1 in the Appendix of Dennis & Schnabel (1983), modified in several ways to make it more robust than the version used in EzPATH 1.0.
  3. An "exact" line search procedure, with user selectable parameters, which allows the user to pinpoint the "best" lk to a very high degree of accuracy on a particular iteration. The algorithm used in SEPATH is the Golden Search algorithm described in Kennedy and Gentle (1980, page 432).

Each of the line search options in SEPATH has its merits and drawbacks. The stephalving approach is inexpensive and usually works, but occasionally fails with difficult problems. The cubic interpolation approach is quite reliable and not too expensive. Consequently, it is used as the default in SEPATH. The Golden Section approach can be useful when a discrepancy function is an extremely nonlinear function of lk on a particular iteration. Remember that, with the ability to break out of the iterative process, change the line search parameters, and restart iteration, the highly sophisticated user can manipulate the iterative process to help achieve a difficult solution with difficult problems.