gradient.descent {salad} | R Documentation |
Gradient descent
Description
A simple implementation of the gradient descent algorithm
Usage
gradient.descent(
par,
fn,
...,
step = 0.1,
maxit = 100,
reltol = sqrt(.Machine$double.eps),
trace = FALSE
)
Arguments
par |
Initial value |
fn |
A function to be minimized (or maximized if 'step' < 0) |
... |
Further arguments to be passed to 'fn' |
step |
Step size. Use a negative value to perform a gradient ascent. |
maxit |
Maximum number of iterations |
reltol |
Relative convergence tolerance |
trace |
If 'TRUE', keep trace of the visited points |
Details
First note that this is not an efficient optimisation method. It is included in the package as a demonstration only.
The function iterates x_{n+1} = x_{n} - step \times grad f(x_n)
until convergence. The gradient is computed using automatic differentiation.
The convergence criterion is as in optim
\frac{ |f(x_{n+1}) - f(x_n)| }{ |f(x[n])| + reltol } < reltol
.
Value
a list with components: 'par' is the final value of the parameter,
'value' is the value of 'f' at 'par', 'counts' is the number of iterations performed,
'convergence' is '0' is the convergence criterion was met. If 'trace' is 'TRUE', an
extra component 'trace' is included, which is a matrix giving the successive values of
x_n
.
Examples
f <- function(x) (x[1] - x[2])**4 + (x[1] + 2*x[2])**2 + x[1] + x[2]
X <- seq(-1, .5, by = 0.01)
Y <- seq(-0.5, 0.5, by = 0.01)
Z <- matrix(NA_real_, nrow = length(X), ncol = length(Y))
for(i in seq_along(X)) for(j in seq_along(Y)) Z[i,j] <- f(c(X[i],Y[j]))
par(mfrow = c(2,2), mai = c(1,1,1,1)/3)
contour(X,Y,Z, levels = c(-0.2, 0, 0.3, 2**(0:6)), main = "step = 0.01")
gd1 <- gradient.descent(c(0,0), f, step = 0.01, trace = TRUE)
lines(t(gd1$trace), type = "o", col = "red")
contour(X,Y,Z, levels = c(-0.2, 0, 0.3, 2**(0:6)))
gd2 <- gradient.descent(c(0,0), f, step = 0.1, trace = TRUE)
lines(t(gd2$trace), type = "o", col = "red")
contour(X,Y,Z, levels = c(-0.2, 0, 0.3, 2**(0:6)))
gd3 <- gradient.descent(c(0,0), f, step = 0.18, trace = TRUE)
lines(t(gd3$trace), type = "o", col = "red")
contour(X,Y,Z, levels = c(-0.2, 0, 0.3, 2**(0:6)))
gd4 <- gradient.descent(c(0,0), f, step = 0.2, trace = TRUE)
lines(t(gd4$trace), type = "o", col = "red")