Gradient descent

On the quadratic f(x) = x^2 the iteration has the exact closed form x_t = x_0 (1 - 2 lr)^t, so it converges for lr < 1, oscillates at lr = 1 and diverges beyond – the behaviour the tests pin down.

Usage

Gradds(f, grad_f, x0, lr = 0.1, steps = 100, tol = 1e-12)

Arguments

f

Objective function of a numeric vector.

grad_f

Gradient function returning a vector of the same length.

x0

Starting point.

lr

Positive step size.

steps

Number of iterations.

tol

Stop when the gradient norm falls below this.

Value

List with estimate (final objective), x, f_path, grad_norm, steps_used, converged, n, method.

Details

Formula: x <- x - lr * grad f(x).

References

Cauchy (1847), Methode generale pour la resolution des systemes d'equations simultanees, C. R. Acad. Sci. Paris 25:536-538.

Examples

Gradds(function(x) sum(x^2), function(x) 2 * x, x0 = c(1, 1))
#> $estimate
#> [1] 8.299031e-20
#> 
#> $x
#> [1] 2.037036e-10 2.037036e-10
#> 
#> $f_path
#>   [1] 2.000000e+00 1.280000e+00 8.192000e-01 5.242880e-01 3.355443e-01
#>   [6] 2.147484e-01 1.374390e-01 8.796093e-02 5.629500e-02 3.602880e-02
#>  [11] 2.305843e-02 1.475740e-02 9.444733e-03 6.044629e-03 3.868563e-03
#>  [16] 2.475880e-03 1.584563e-03 1.014120e-03 6.490371e-04 4.153837e-04
#>  [21] 2.658456e-04 1.701412e-04 1.088904e-04 6.968983e-05 4.460149e-05
#>  [26] 2.854495e-05 1.826877e-05 1.169201e-05 7.482888e-06 4.789049e-06
#>  [31] 3.064991e-06 1.961594e-06 1.255420e-06 8.034690e-07 5.142202e-07
#>  [36] 3.291009e-07 2.106246e-07 1.347997e-07 8.627183e-08 5.521397e-08
#>  [41] 3.533694e-08 2.261564e-08 1.447401e-08 9.263367e-09 5.928555e-09
#>  [46] 3.794275e-09 2.428336e-09 1.554135e-09 9.946465e-10 6.365737e-10
#>  [51] 4.074072e-10 2.607406e-10 1.668740e-10 1.067994e-10 6.835159e-11
#>  [56] 4.374501e-11 2.799681e-11 1.791796e-11 1.146749e-11 7.339196e-12
#>  [61] 4.697085e-12 3.006135e-12 1.923926e-12 1.231313e-12 7.880401e-13
#>  [66] 5.043457e-13 3.227812e-13 2.065800e-13 1.322112e-13 8.461516e-14
#>  [71] 5.415370e-14 3.465837e-14 2.218136e-14 1.419607e-14 9.085484e-15
#>  [76] 5.814710e-15 3.721414e-15 2.381705e-15 1.524291e-15 9.755464e-16
#>  [81] 6.243497e-16 3.995838e-16 2.557336e-16 1.636695e-16 1.047485e-16
#>  [86] 6.703904e-17 4.290499e-17 2.745919e-17 1.757388e-17 1.124728e-17
#>  [91] 7.198262e-18 4.606888e-18 2.948408e-18 1.886981e-18 1.207668e-18
#>  [96] 7.729075e-19 4.946608e-19 3.165829e-19 2.026131e-19 1.296724e-19
#> [101] 8.299031e-20
#> 
#> $grad_norm
#> [1] 7.20201e-10
#> 
#> $steps_used
#> [1] 100
#> 
#> $converged
#> [1] FALSE
#> 
#> $n
#> [1] 2
#> 
#> $method
#> [1] "x <- x - lr grad f(x), Cauchy (1847)"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"