using FrankWolfe
using LinearAlgebra
using LaTeXStrings
using PlotsFrankWolfe for scaled, shifted $\ell^1$ and $\ell^{\infty}$ norm balls
In this example, we run the vanilla FrankWolfe algorithm on a scaled and shifted $\ell^1$ and $\ell^{\infty}$ norm ball, using the ScaledBoundL1NormBall and ScaledBoundLInfNormBall LMOs. We shift both onto the point $(1,0)$ and then scale them by a factor of $2$ along the x-axis. We project the point $(2,1)$ onto the polytopes.
n = 2
k = 1000
xp = [2.0, 1.0]
f(x) = norm(x - xp)^2
function grad!(storage, x)
@. storage = 2 * (x - xp)
return nothing
end
lower = [-1.0, -1.0]
upper = [3.0, 1.0]
l1 = FrankWolfe.ScaledBoundL1NormBall(lower, upper)
linf = FrankWolfe.ScaledBoundLInfNormBall(lower, upper)
x1 = FrankWolfe.compute_extreme_point(l1, zeros(n))
gradient = collect(x1)
x_l1, v_1, primal_1, dual_gap_1, trajectory_1 = FrankWolfe.frank_wolfe(
f,
grad!,
l1,
collect(copy(x1)),
max_iteration=k,
line_search=FrankWolfe.Shortstep(2.0),
print_iter=50,
memory_mode=FrankWolfe.InplaceEmphasis(),
verbose=true,
trajectory=true,
);
println("\nFinal solution: ", x_l1)
x2 = FrankWolfe.compute_extreme_point(linf, zeros(n))
gradient = collect(x2)
x_linf, v_2, primal_2, dual_gap_2, trajectory_2 = FrankWolfe.frank_wolfe(
f,
grad!,
linf,
collect(copy(x2)),
max_iteration=k,
line_search=FrankWolfe.Shortstep(2.0),
print_iter=50,
memory_mode=FrankWolfe.InplaceEmphasis(),
verbose=true,
trajectory=true,
);
println("\nFinal solution: ", x_linf)
Vanilla Frank-Wolfe Algorithm.
MEMORY_MODE: FrankWolfe.InplaceEmphasis() STEPSIZE: Shortstep EPSILON: 1.0e-7 MAXITERATION: 1000 TYPE: Float64
MOMENTUM: nothing GRADIENTTYPE: Nothing
LMO: FrankWolfe.ScaledBoundL1NormBall{Float64, 1, Vector{Float64}, Vector{Float64}}
[ Info: In memory_mode memory iterates are written back into x0!
-------------------------------------------------------------------------------------------------
Type Iteration Primal Dual Dual Gap Time It/sec
-------------------------------------------------------------------------------------------------
I 1 2.000000e+00 -6.000000e+00 8.000000e+00 0.000000e+00 Inf
FW 50 2.198243e-01 1.859119e-01 3.391239e-02 1.035963e-01 4.826427e+02
FW 100 2.104540e-01 1.927834e-01 1.767061e-02 1.038810e-01 9.626400e+02
FW 150 2.071345e-01 1.951277e-01 1.200679e-02 1.041402e-01 1.440366e+03
FW 200 2.054240e-01 1.963167e-01 9.107240e-03 1.043936e-01 1.915826e+03
FW 250 2.043783e-01 1.970372e-01 7.341168e-03 1.046578e-01 2.388736e+03
FW 300 2.036722e-01 1.975209e-01 6.151268e-03 1.049165e-01 2.859417e+03
FW 350 2.031630e-01 1.978684e-01 5.294582e-03 1.051680e-01 3.328008e+03
FW 400 2.027782e-01 1.981301e-01 4.648079e-03 1.054169e-01 3.794456e+03
FW 450 2.024772e-01 1.983344e-01 4.142727e-03 1.056798e-01 4.258146e+03
FW 500 2.022352e-01 1.984984e-01 3.736776e-03 1.059339e-01 4.719925e+03
FW 550 2.020364e-01 1.986329e-01 3.403479e-03 1.061867e-01 5.179555e+03
FW 600 2.018701e-01 1.987452e-01 3.124906e-03 1.064349e-01 5.637249e+03
FW 650 2.017290e-01 1.988404e-01 2.888583e-03 1.066974e-01 6.091997e+03
FW 700 2.016078e-01 1.989222e-01 2.685564e-03 1.069517e-01 6.545011e+03
FW 750 2.015024e-01 1.989932e-01 2.509264e-03 1.072007e-01 6.996225e+03
FW 800 2.014101e-01 1.990554e-01 2.354727e-03 1.074483e-01 7.445444e+03
FW 850 2.013284e-01 1.991103e-01 2.218154e-03 1.077095e-01 7.891594e+03
FW 900 2.012558e-01 1.991592e-01 2.096580e-03 1.079636e-01 8.336139e+03
FW 950 2.011906e-01 1.992030e-01 1.987662e-03 1.082150e-01 8.778822e+03
FW 1000 2.011319e-01 1.992424e-01 1.889519e-03 1.084626e-01 9.219766e+03
Last 1001 2.011297e-01 1.992439e-01 1.885794e-03 1.086137e-01 9.216147e+03
-------------------------------------------------------------------------------------------------
Final solution: [1.799813188674937, 0.5986834801090863]
Vanilla Frank-Wolfe Algorithm.
MEMORY_MODE: FrankWolfe.InplaceEmphasis() STEPSIZE: Shortstep EPSILON: 1.0e-7 MAXITERATION: 1000 TYPE: Float64
MOMENTUM: nothing GRADIENTTYPE: Nothing
LMO: FrankWolfe.ScaledBoundLInfNormBall{Float64, 1, Vector{Float64}, Vector{Float64}}
[ Info: In memory_mode memory iterates are written back into x0!
-------------------------------------------------------------------------------------------------
Type Iteration Primal Dual Dual Gap Time It/sec
-------------------------------------------------------------------------------------------------
I 1 1.300000e+01 -1.900000e+01 3.200000e+01 0.000000e+00 Inf
FW 50 1.084340e-02 -7.590380e-02 8.674720e-02 5.513974e-02 9.067870e+02
FW 100 5.509857e-03 -3.856900e-02 4.407886e-02 5.541036e-02 1.804717e+03
FW 150 3.695414e-03 -2.586790e-02 2.956331e-02 5.567144e-02 2.694380e+03
FW 200 2.780453e-03 -1.946317e-02 2.224362e-02 5.592580e-02 3.576167e+03
FW 250 2.228830e-03 -1.560181e-02 1.783064e-02 5.620253e-02 4.448198e+03
FW 300 1.859926e-03 -1.301948e-02 1.487941e-02 5.645862e-02 5.313627e+03
FW 350 1.595838e-03 -1.117087e-02 1.276670e-02 5.671039e-02 6.171709e+03
FW 400 1.397443e-03 -9.782098e-03 1.117954e-02 5.697383e-02 7.020767e+03
FW 450 1.242935e-03 -8.700548e-03 9.943483e-03 5.722746e-02 7.863358e+03
FW 500 1.119201e-03 -7.834409e-03 8.953610e-03 5.747484e-02 8.699458e+03
FW 550 1.017878e-03 -7.125146e-03 8.143024e-03 5.772938e-02 9.527211e+03
FW 600 9.333816e-04 -6.533671e-03 7.467053e-03 5.801418e-02 1.034230e+04
FW 650 8.618413e-04 -6.032889e-03 6.894730e-03 5.826857e-02 1.115524e+04
FW 700 8.004890e-04 -5.603423e-03 6.403912e-03 5.851864e-02 1.196200e+04
FW 750 7.472928e-04 -5.231050e-03 5.978342e-03 5.876637e-02 1.276240e+04
FW 800 7.007275e-04 -4.905093e-03 5.605820e-03 5.903066e-02 1.355228e+04
FW 850 6.596259e-04 -4.617381e-03 5.277007e-03 5.928763e-02 1.433689e+04
FW 900 6.230796e-04 -4.361557e-03 4.984637e-03 5.953589e-02 1.511693e+04
FW 950 5.903710e-04 -4.132597e-03 4.722968e-03 5.980878e-02 1.588396e+04
FW 1000 5.609256e-04 -3.926479e-03 4.487405e-03 6.009374e-02 1.664067e+04
Last 1001 5.598088e-04 -3.918661e-03 4.478470e-03 6.024747e-02 1.661480e+04
-------------------------------------------------------------------------------------------------
Final solution: [2.0005598087769556, 0.9763463450796975]We plot the polytopes alongside the solutions from above:
xcoord1 = [1, 3, 1, -1, 1]
ycoord1 = [-1, 0, 1, 0, -1]
xcoord2 = [3, 3, -1, -1, 3]
ycoord2 = [-1, 1, 1, -1, -1]
plot(
xcoord1,
ycoord1,
title="Visualization of scaled shifted norm balls",
lw=2,
label=L"\ell^1 \textrm{ norm}",
)
plot!(xcoord2, ycoord2, lw=2, label=L"\ell^{\infty} \textrm{ norm}")
plot!(
[x_l1[1]],
[x_l1[2]],
seriestype=:scatter,
lw=5,
color="blue",
label=L"\ell^1 \textrm{ solution}",
)
plot!(
[x_linf[1]],
[x_linf[2]],
seriestype=:scatter,
lw=5,
color="orange",
label=L"\ell^{\infty} \textrm{ solution}",
legend=:bottomleft,
)
This page was generated using Literate.jl.