Package minfx :: Package line_search :: Module more_thuente
[hide private]
[frames] | no frames]

Module more_thuente

source code

A line search algorithm from More and Thuente.

This file is part of the minfx optimisation library.

Functions [hide private]
 
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.
source code
 
print_data(text, k, a, Ik, Ik_lim)
Temp func for debugging.
source code
 
update(a, Ik, at, al, au, ft, fl, fu, gt, gl, gu, bracketed, Ik_lim, d=0.66, print_flag=0)
Trial value selection and interval updating.
source code
Variables [hide private]
  __package__ = 'minfx.line_search'

Imports: deepcopy, sqrt, dot, sys, cubic_int, cubic_ext, quadratic_fafbga, quadratic_gagb, cubic, quadratic, secant


Function Details [hide private]

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)

source code 

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.