adagio (version 0.5.9)

linesearch: Wolfe Line Search

Description

Weak and strong Wolfe line search, based on the book by Nocedal and Wright.

Usage

linesearch_ww(x0, d0, fn, gr = NULL, ...,
              dir = c("central", "forward", "backward"),
              c1 = 0, c2 = 0.5, fvalquit = -Inf, trace = 0 )
linesearch_sw(x0, d0, fn, gr = NULL, ...,
              dir = c("central", "forward", "backward"),
              c1 = 0, c2 = 0.5, fvalquit = -Inf, trace = 0)

Arguments

x0

initial point.

d0

search direction.

fn

function to be minimized.

gr

gradient function of fn; will be computed numerically if is NULL; should be passed as column vector.

...

additional parameters to be passed to the function.

dir

direction for computing derivatives; will not be used if gr is not NULL.

c1

first Wolfe parameter for the sufficient decrease condition: f(x0 + u d) < f0 + c1*u*t(grad0)%*%d; default 0.

c2

second Wolfe parameter for the weak condition on directional derivative: (grad f) t(x0 + u d)%*%d > c2*t(grad0)%*%d; default 0.5.

fvalquit

quit immediately if f drops below this value.

trace

printing level, default 0 for no printing at all.

Value

• Returns a list with the following components:
• alpha
  step length satisfying weak Wolfe conditions if one was found, otherwise left end point of interval bracketing such a point (possibly 0)
• xalpha
  x0 + alpha*d.
• falpha
  f(x0 + alpha d).
• galpha
  (grad f)(x0 + alpha d).
• fail
  0 if both Wolfe conditions satisfied, or falpha < fvalquit 1 if one or both Wolfe conditions not satisfied but an interval was found bracketing a point where both satisfied -1 if no such interval was found, function may be unbounded below.
• beta
  same as alpha if it satisfies weak Wolfe conditions, otherwise right end point of interval bracketing such a point (inf if no such finite interval found).
• gbeta
  (grad f)(x0 + beta d) (this is important for bundle methods), vector of nans if beta is Inf.
• fvalrec
  record of function evaluations.
• nsteps
  number of steps, strong Wolfe only.

Details

Line search enforcing weak or strong Wolfe conditions, suitable for minimizing both smooth and nonsmooth functions. Strong Wolfe line search with cubic interpolation. For the Wolfe conditions, see the parameter descriptions for c1 and c2 above.

For functions that are known to be nonsmooth, setting the second Wolfe parameter to zero makes sense, especially for a bundle method, and for the Shor R-algorithm, for which it is essential. However, it's not a good idea for BFGS, as for smooth functions this may prevent superlinear convergence, and it can even make trouble for BFGS on, e.g., f(x) = x_1^2 + eps |x_2|, when eps is small.

References

Nocedal, Jorge, and Stephen Wright (2006). Numerical Optimization. Second edition, Springer Science+Business Media, LLC.

Examples

fnSphere <- function(x) sum(x * x)
  grSphere <- function(x) 2*x
  x0 <- c(1, 1)
  d0 <- -grSphere(x0)
  linesearch_ww(x0, d0, fnSphere, grSphere)
  # $alpha      0.5
  # $xalpha     0   0
  # $falpha     0
  # $galpha     0   0
  # $fail       0
  # $beta       0.5
  # $gbeta      0   0
  # $fevalrec   2   0

  fnExtSphere <- function(x) sum((1:length(x)) * x * x)
  grExtSphere <- function(x) 2 * (1:length(x)) * x
  x0 <- c(1, 1)
  d0 <- -grExtSphere(x0)
  linesearch_sw(x0, d0, fnExtSphere, grExtSphere)
  # $alpha      0.2777778
  # $xalpha     0.4444444   -0.1111111
  # $falpha     0.2222222
  # $galpha     0.8888889   -0.4444444
  # $fail       0
  # $steps      1