more_thuente(func, func_prime, args, x, f, g, p, a_init=1.0, a_min=1e-25, a_max=None, a_tol=1e-10, phi_min=-1000.0, mu=0.001, eta=0.1, print_flag=0)

A line search algorithm from More and Thuente.

More, J. J., and Thuente, D. J. 1994, Line search algorithms with guaranteed sufficient decrease. ACM Trans. Math. Softw. 20, 286-307.

Internal variables

a0, the null sequence data structure containing the following keys:

'a' - 0
'phi' - phi(0)
'phi_prime' - phi'(0)

a, the sequence data structure containing the following keys:

'a' - alpha
'phi' - phi(alpha)
'phi_prime' - phi'(alpha)

Ik, the interval data structure containing the following keys:

'a' - The current interval Ik = [al, au]
'phi' - The interval [phi(al), phi(au)]
'phi_prime' - The interval [phi'(al), phi'(au)]

Instead of using the modified function:

   psi(a) = phi(a) - phi(0) - a.phi'(0),

the function:

   psi(a) = phi(a) - a.phi'(0),

was used as the phi(0) component has no effect on the results.

update(a, Ik, at, al, au, ft, fl, fu, gt, gl, gu, bracketed, Ik_lim, d=0.66, print_flag=0)

source code

Trial value selection and interval updating.

Trial value selection

fl, fu, ft, gl, gu, and gt are the function and gradient values at the interval end points al and au, and at the trial point at. ac is the minimiser of the cubic that interpolates fl, ft, gl, and gt. aq is the minimiser of the quadratic that interpolates fl, ft, and gl. as is the minimiser of the quadratic that interpolates fl, gl, and gt.

The trial value selection is divided into four cases.

Case 1: ft > fl. In this case compute ac and aq, and set:

          / ac,            if |ac - al| < |aq - al|,
   at+ = <
          \ 1/2(aq + ac),  otherwise.

Case 2: ft <= fl and gt.gl < 0. In this case compute ac and as, and set:

          / ac,            if |ac - at| >= |as - at|,
   at+ = <
          \ as,            otherwise.

Case 3: ft <= fl and gt.gl >= 0, and |gt| <= |gl|. In this case at+ is chosen by extrapolating the function values at al and at, so the trial value at+ lies outside th interval with at and al as endpoints. Compute ac and as.

If the cubic tends to infinity in the direction of the step and the minimum of the cubic is beyound at, set:
```
          / ac,            if |ac - at| < |as - at|,
   at+ = <
          \ as,            otherwise.
```
Otherwise set at+ = as.

Redefine at+ by setting:

          / min{at + d(au - at), at+},        if at > al.
   at+ = <
          \ max{at + d(au - at), at+},        otherwise,

for some d < 1.

Case 4: ft <= fl and gt.gl >= 0, and |gt| > |gl|. In this case choose at+ as the minimiser of the cubic that interpolates fu, ft, gu, and gt.

Interval updating

Given a trial value at in I, the endpoints al+ and au+ of the updated interval I+ are determined as follows:

Case U1: If f(at) > f(al), then al+ = al and au+ = at.
Case U2: If f(at) <= f(al) and f'(at)(al - at) > 0, then al+ = at and au+ = au.
Case U3: If f(at) <= f(al) and f'(at)(al - at) < 0, then al+ = at and au+ = al.

Module more_thuente

more_thuente(func, func_prime, args, x, f, g, p, a_init=1.0, a_min=1e-25, a_max=None, a_tol=1e-10, phi_min=-1000.0, mu=0.001, eta=0.1, print_flag=0)

Internal variables

update(a, Ik, at, al, au, ft, fl, fu, gt, gl, gu, bracketed, Ik_lim, d=0.66, print_flag=0)

Trial value selection

Interval updating