gradient.descent: Gradient descent

In salad: Simple Automatic Differentiation

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")

salad documentation built on April 4, 2025, 1:06 a.m.