Backtracking line search

Shrinks the step until the Armijo sufficient-decrease condition holds. A non-descent direction is rejected rather than searched.

Usage

morie_boyd_backtracking(
  f,
  grad,
  x,
  dx,
  alpha = 0.25,
  beta = 0.5,
  max_iter = 100L
)

Arguments

f

Objective, f(x) returning a scalar.

grad

Gradient at x.

x

Current point.

dx

Search direction; must be a descent direction.

alpha

Sufficient-decrease fraction in (0, 0.5).

beta

Shrink factor in (0, 1).

max_iter

Cap on backtracking steps.

Value

List with t, x_new, f_new, n_backtracks, converged.

References

Boyd, S., & Vandenberghe, L. (2004). Convex Optimization, Algorithm 9.2.

Examples

f <- function(z) sum(z^2)
morie_boyd_backtracking(f, 2, 1, -2)$t
#> [1] 0.5