Frank-Wolfe conditional gradient

Each step solves a linear problem over the feasible polytope and moves toward its solution, so the iterate stays feasible by construction and no projection is ever needed. The duality gap <grad, x - s> upper bounds the optimality gap and is reported.

Usage

Frwol2(f, grad_f, domain, x0, steps = 50)

Arguments

f: Objective function of a numeric vector.
grad_f: Gradient function.
domain: Matrix whose rows are the polytope vertices.
x0: Feasible starting point.
steps: Number of iterations.

Value

List with estimate, x, f_path, gap, steps, n, method.

Details

Formula: s = argmin_v <grad f(x), v>; x <- (1 - gamma) x + gamma s with gamma = 2/(t + 2).

References

Frank and Wolfe (1956), An algorithm for quadratic programming, Naval Research Logistics Quarterly 3(1-2):95-110. doi:10.1002/nav.3800030109

Examples

V <- rbind(c(0, 0), c(1, 0), c(0, 1))
Frwol2(function(x) sum((x - 0.3)^2), function(x) 2 * (x - 0.3),
       domain = V, x0 = c(0.3, 0.3))
#> $estimate
#> [1] 0.0004998078
#> 
#> $x
#> [1] 0.3215686 0.2941176
#> 
#> $f_path
#>  [1] 0.000000e+00 1.800000e-01 2.244444e-01 4.111111e-02 1.000000e-02
#>  [6] 3.777778e-02 1.764172e-02 2.959184e-03 1.611111e-02 1.111111e-02
#> [11] 1.487603e-03 9.568411e-03 8.270874e-03 1.084410e-03 6.757370e-03
#> [16] 6.736111e-03 9.883218e-04 5.297962e-03 5.792552e-03 9.972299e-04
#> [21] 8.163265e-04 2.162253e-03 1.362621e-03 3.659945e-04 1.877778e-03
#> [26] 1.671006e-03 2.676926e-04 1.784105e-03 1.906622e-03 3.091558e-04
#> [31] 1.768991e-03 2.081491e-03 4.043274e-04 2.763718e-04 8.488101e-04
#> [36] 6.072058e-04 1.440179e-04 8.345052e-04 8.147796e-04 1.314924e-04
#> [41] 8.804283e-04 1.007634e-03 1.805474e-04 9.534750e-04 1.179471e-03
#> [46] 2.599827e-04 1.155096e-04 4.688207e-04 3.938463e-04 7.496876e-05
#> [51] 4.998078e-04
#> 
#> $gap
#> [1] 0.01239484
#> 
#> $steps
#> [1] 50
#> 
#> $n
#> [1] 2
#> 
#> $method
#> [1] "s = argmin_v <grad, v>, gamma_t = 2/(t+2), Frank & Wolfe (1956)"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"