Fully corrective Frank-Wolfe

Holloway replaces the fixed step-size rule with a full re-optimisation over the convex hull of every vertex found so far. The inner minimisation is a cycle of golden-section line searches between the current point and each active vertex, repeated a fixed number of rounds so both language arms take identical steps.

Usage

Fwlfwd(f, grad_f, domain, x0, steps = 10, rounds = 3)

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 vertex additions.

rounds

Line-search sweeps over the active set per step.

Value

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

Details

Formula: S <- S + argmin_v <grad f(x), v>; x <- argmin{ f(x) : x in conv(S) }.

References

Holloway (1974), An extension of the Frank and Wolfe method of feasible directions, Mathematical Programming 6(1):14-27. doi:10.1007/BF01580219

Examples

V <- rbind(c(0, 0), c(1, 0), c(0, 1))
Fwlfwd(function(x) sum((x - 0.3)^2), function(x) 2 * (x - 0.3),
       domain = V, x0 = c(0.3, 0.3))
#> $estimate
#> [1] 5.782095e-27
#> 
#> $x
#> [1] 0.3 0.3
#> 
#> $f_path
#>  [1] 0.000000e+00 3.383257e-26 1.541070e-25 3.304073e-27 6.607480e-28
#>  [6] 5.458958e-27 3.624215e-27 1.407301e-26 1.087835e-26 8.114707e-27
#> [11] 5.782095e-27
#> 
#> $gap
#> [1] 7.364109e-14
#> 
#> $n_active
#> [1] 3
#> 
#> $n
#> [1] 2
#> 
#> $method
#> [1] "vertex addition plus re-optimisation over conv(S), Holloway (1974)"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"