rje (version 1.9)

armijo: Generic functions to aid finding local minima given search direction

Description

Allows use of an Armijo rule or coarse line search as part of minimisation (or maximisation) of a differentiable function of multiple arguments (via gradient descent or similar). Repeated application of one of these rules should (hopefully) lead to a local minimum.

Usage

armijo(fun, x, dx, beta = 3, sigma = 0.5, grad, 
                 maximise = FALSE, searchup = TRUE, adj.start = 1, ...)
coarseLine(fun, x, dx, beta = 3, maximise = FALSE, ...)

Arguments

fun

a function whose first argument is a numeric vector

x

a starting value to be passed to fun

dx

numeric vector containing feasible direction for search; defaults to -grad for ordinary gradient descent

beta

numeric value (greater than 1) giving factor by which to adjust step size

sigma

numeric value (less than 1) giving steepness criterion for move

grad

numeric gradient of f at x (will be estimated if not provided)

maximise

logical: if set to TRUE search is for a maximum rather than a minimum.

searchup

logical: if set to TRUE method will try to find largest move satisfying Armijo criterion, rather than just accepting the first it sees

adj.start

an initial adjustment factor for the step size.

…

other arguments to be passed to fun

Value

A list comprising

best

the value of the function at the final point of evaluation

adj

the constant in the step, i.e. \(\beta^n\)

move

the final move; i.e. \(\beta^n dx\)

code

an integer indicating the result of the function; 0 = returned OK, 1 = very small move suggested, may be at minimum already, 2 = failed to find minimum: function evaluated to NA or was always larger than \(f(x)\) (direction might be infeasible), 3 = failed to find minimum: stepsize became too small or large without satisfying rule.

Details

coarseLine performs a stepwise search and tries to find the integer \(k\) minimising \(f(x_k)\) where $$x_k = x + \beta^k dx.$$ Note \(k\) may be negative.

armijo implements an Armijo rule for moving, which is to say that $$f(x_k) - f(x) < - \sigma \beta^k dx \cdot \nabla_x f.$$ This has better convergence guarantees than a simple line search, but may be slower in practice. See Bertsekas (1999) for theory underlying the Armijo rule.

Each of these rules should be applied repeatedly to achieve convergence (see example below).

References

Bertsekas, D.P. Nonlinear programming, 2nd Edition. Athena, 1999.

Examples

# NOT RUN {
# minimisation of simple function of three variables
x = c(0,-2,4)
f = function(x) ((x[1]-3)^2 + x[2]*sin(x[2]) + exp(x[3]) - x[3])

tol = .Machine$double.eps
mv = 1

while (mv > tol) {
  # or replace with coarseLine()
  out = armijo(f, x, sigma=0.1)
  x = out$x
  mv = sum(out$move^2)
}

# correct solution is c(3,0,0)
x

# }