armijo | R Documentation |
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.
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, ...)
fun |
a function whose first argument is a numeric vector |
x |
a starting value to be passed to |
dx |
numeric vector containing feasible direction for search; defaults
to |
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 |
maximise |
logical: if set to |
searchup |
logical: if set to |
adj.start |
an initial adjustment factor for the step size. |
... |
other arguments to be passed to |
coarseLine
performs a stepwise search and tries to find the integer
k minimising f(x_k) where
x_k = x + β^k dx.
Note k may be negative. This is genearlly quicker and dirtier than the Armijo rule.
armijo
implements an Armijo rule for moving, which is to say that
f(x_k) - f(x) < - σ β^k dx . grad.
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).
A list comprising
best |
the value of the function at the final point of evaluation |
adj |
the constant in the step, i.e. β^n |
move |
the final move; i.e. β^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 |
coarseLine
: Coarse line search
Robin Evans
Bertsekas, D.P. Nonlinear programming, 2nd Edition. Athena, 1999.
# minimisation of simple function of three variables x = c(0,-1,4) f = function(x) ((x[1]-3)^2 + sin(x[2])^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) (or c(3,k*pi,0) for any integer k) x
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.