Edit on GitHub
Main.check_gradients

Alternating methods

In this example we will compare FrankWolfe.alternating_linear_minimization and FrankWolfe.alternating_projections for a very simple feasibility problem.

We consider the probability simplex

\[P = \{ x \in \mathbb{R}^n \colon \sum_{i=1}^n x_i = 1, x_i \geq 0 ~~ i=1,\dots,n\} ~.\]

and a scaled, shifted $\ell^{\infty}$ norm ball

\[Q = [-1,0]^n ~.\]

The goal is to find either a point in the intersection, $x \in P \cap Q$, or a pair of points, $(x_P, x_Q) \in P \times Q$, which attains minimal distance between $P$ and $Q$,

\[\|x_P - x_Q\|_2 = \min_{(x,y) \in P \times Q} \|x - y \|_2 ~.\]

using FrankWolfe
include("../examples/plot_utils.jl")
Main.check_gradients

Setting up objective, gradient and linear minimization oracles

Since we only consider the feasibility problem the objective function as well as the gradient are zero.

n = 20

f(x) = 0

function grad!(storage, x)
    @. storage = zero(x)
end


lmo1 = FrankWolfe.ProbabilitySimplexOracle(1.0)
lmo2 = FrankWolfe.ScaledBoundLInfNormBall(-ones(n), zeros(n))
lmos = (lmo1, lmo2)

x0 = rand(n)

target_tolerance = 1e-6

trajectories = [];

Running Alternating Linear Minimization

We run Alternating Linear Minimization (ALM) with FrankWolfe.block_coordinate_frank_wolfe. This method allows three different update orders, FullUpdate, CyclicUpdate and Stochasticupdate. Accordingly both blocks are updated either simulatenously, sequentially or in random order.

for order in [FrankWolfe.FullUpdate(), FrankWolfe.CyclicUpdate(), FrankWolfe.StochasticUpdate()]

    _, _, _, _, _, alm_trajectory = FrankWolfe.alternating_linear_minimization(
        FrankWolfe.block_coordinate_frank_wolfe,
        f,
        grad!,
        lmos,
        x0,
        update_order=order,
        verbose=true,
        trajectory=true,
        epsilon=target_tolerance,
    )
    push!(trajectories, alm_trajectory)
end

Alternating Linear Minimization (ALM).
LAMBDA: 1.0
Block coordinate Frank-Wolfe (BCFW).
MEMORY_MODE: FrankWolfe.InplaceEmphasis() STEPSIZE: DataType[FrankWolfe.Adaptive{Float64, Int64}, FrankWolfe.Adaptive{Float64, Int64}] EPSILON: 1.0e-6 MAXITERATION: 10000 TYPE: Float64
MOMENTUM: nothing GRADIENTTYPE: FrankWolfe.BlockVector{Float64, Vector{Float64}, Tuple{Int64}} UPDATE_ORDER: FrankWolfe.FullUpdate() UPDATE_STEP: DataType[FrankWolfe.FrankWolfeStep, FrankWolfe.FrankWolfeStep]
[ Info: In memory_mode memory iterates are written back into x0!

-------------------------------------------------------------------------------------------------
  Type     Iteration         Primal           Dual       Dual Gap           Time         It/sec
-------------------------------------------------------------------------------------------------
     I             1   3.778464e+00  -4.022154e+01   4.400000e+01   0.000000e+00            Inf
----------------
        Infeas
----------------

  3.778464e+00
    FW          1000   5.000047e-02   4.988536e-02   1.151053e-04   7.296192e-01   1.370578e+03
  5.000047e-02
    FW          2000   5.000000e-02   4.999558e-02   4.423306e-06   7.401146e-01   2.702284e+03
  5.000000e-02
  Last          2445   5.000000e-02   4.999898e-02   1.022986e-06   9.094512e-01   2.688434e+03
-------------------------------------------------------------------------------------------------
  5.000000e-02
----------------

Alternating Linear Minimization (ALM).
LAMBDA: 1.0
Block coordinate Frank-Wolfe (BCFW).
MEMORY_MODE: FrankWolfe.InplaceEmphasis() STEPSIZE: DataType[FrankWolfe.Adaptive{Float64, Int64}, FrankWolfe.Adaptive{Float64, Int64}] EPSILON: 1.0e-6 MAXITERATION: 10000 TYPE: Float64
MOMENTUM: nothing GRADIENTTYPE: FrankWolfe.BlockVector{Float64, Vector{Float64}, Tuple{Int64}} UPDATE_ORDER: FrankWolfe.CyclicUpdate() UPDATE_STEP: DataType[FrankWolfe.FrankWolfeStep, FrankWolfe.FrankWolfeStep]
[ Info: In memory_mode memory iterates are written back into x0!

-------------------------------------------------------------------------------------------------
  Type     Iteration         Primal           Dual       Dual Gap           Time         It/sec
-------------------------------------------------------------------------------------------------
     I             1   3.778464e+00  -4.022154e+01   4.400000e+01   0.000000e+00            Inf
----------------
        Infeas
----------------

  3.778464e+00
    FW          1000   5.000047e-02   4.988833e-02   1.121389e-04   8.742596e-03   1.143825e+05
  5.000047e-02
    FW          2000   5.000000e-02   4.999569e-02   4.308009e-06   1.690986e-02   1.182742e+05
  5.000000e-02
  Last          2446   5.000000e-02   4.999898e-02   1.018029e-06   2.069594e-02   1.181874e+05
-------------------------------------------------------------------------------------------------
  5.000000e-02
----------------

Alternating Linear Minimization (ALM).
LAMBDA: 1.0
Block coordinate Frank-Wolfe (BCFW).
MEMORY_MODE: FrankWolfe.InplaceEmphasis() STEPSIZE: DataType[FrankWolfe.Adaptive{Float64, Int64}, FrankWolfe.Adaptive{Float64, Int64}] EPSILON: 1.0e-6 MAXITERATION: 10000 TYPE: Float64
MOMENTUM: nothing GRADIENTTYPE: FrankWolfe.BlockVector{Float64, Vector{Float64}, Tuple{Int64}} UPDATE_ORDER: FrankWolfe.StochasticUpdate() UPDATE_STEP: DataType[FrankWolfe.FrankWolfeStep, FrankWolfe.FrankWolfeStep]
[ Info: In memory_mode memory iterates are written back into x0!

-------------------------------------------------------------------------------------------------
  Type     Iteration         Primal           Dual       Dual Gap           Time         It/sec
-------------------------------------------------------------------------------------------------
     I             1   5.732358e-01  -4.342676e+01   4.400000e+01   0.000000e+00            Inf
----------------
        Infeas
----------------

  5.732358e-01
    FW          1000   5.000033e-02   4.990436e-02   9.597183e-05   8.862453e-02   1.128356e+04
  5.000033e-02
    FW          2000   5.000000e-02   4.999676e-02   3.243229e-06   9.640295e-02   2.074625e+04
  5.000000e-02
  Last          2354   5.000000e-02   4.999899e-02   1.010147e-06   9.927530e-02   2.371184e+04
-------------------------------------------------------------------------------------------------
  5.000000e-02
----------------

As an alternative to Block-Coordiante Frank-Wolfe (BCFW), one can also run alternating linear minimization with standard Frank-Wolfe algorithm. These methods perform then the full (simulatenous) update at each iteration. In this example we also use FrankWolfe.away_frank_wolfe.

_, _, _, _, _, afw_trajectory = FrankWolfe.alternating_linear_minimization(
    FrankWolfe.away_frank_wolfe,
    f,
    grad!,
    lmos,
    x0,
    verbose=true,
    trajectory=true,
    epsilon=target_tolerance,
)
push!(trajectories, afw_trajectory);

Alternating Linear Minimization (ALM).
LAMBDA: 1.0
Away-step Frank-Wolfe Algorithm.
MEMORY_MODE: FrankWolfe.InplaceEmphasis() STEPSIZE: Adaptive{Float64, Int64} EPSILON: 1.0e-6 MAXITERATION: 10000 TYPE: Float64
GRADIENTTYPE: FrankWolfe.BlockVector{Float64, Vector{Float64}, Tuple{Int64}} LAZY: false lazy_tolerance: 2.0 MOMENTUM: nothing AWAYSTEPS: true
LMO: FrankWolfe.ProductLMO{2, Tuple{FrankWolfe.ProbabilitySimplexOracle{Float64}, FrankWolfe.ScaledBoundLInfNormBall{Float64, 1, Vector{Float64}, Vector{Float64}}}}

----------------------------------------------------------------------------------------------------------------
  Type     Iteration         Primal           Dual       Dual Gap           Time         It/sec     #ActiveSet
----------------------------------------------------------------------------------------------------------------
     I             1   2.300000e+01           -Inf            Inf   0.000000e+00            Inf              2
----------------
        Infeas
----------------

  2.010582e+00
  Last           171   5.000000e-02   4.999908e-02   9.177388e-07   9.474569e-01   1.804832e+02             84
----------------------------------------------------------------------------------------------------------------
  5.000000e-02
----------------
    PP           171   5.000000e-02   4.999908e-02   9.177388e-07   1.028380e+00   1.662809e+02             84
----------------------------------------------------------------------------------------------------------------
  5.000000e-02
----------------

Running Alternating Projections

Unlike ALM, Alternating Projections (AP) is only suitable for feasibility problems. One omits the objective and gradient as parameters.

_, _, _, _, ap_trajectory = FrankWolfe.alternating_projections(
    lmos,
    x0,
    trajectory=true,
    verbose=true,
    print_iter=100,
    epsilon=target_tolerance,
)
push!(trajectories, ap_trajectory);

Alternating Projections.
MEMORY_MODE: FrankWolfe.InplaceEmphasis() EPSILON: 1.0e-6 MAXITERATION: 10000 TYPE: Float64
GRADIENTTYPE: Vector{Vector{Float64}}
[ Info: In memory_mode memory iterates are written back into x0!

----------------------------------------------------------------------------------
  Type     Iteration       Dual Gap         Infeas           Time         It/sec
----------------------------------------------------------------------------------
     I             1   4.095012e-01   2.047506e-01   0.000000e+00            Inf
    FW           100   1.045308e-04   5.000040e-02   1.220630e+00   8.192490e+01
    FW           200   2.524997e-05   5.000002e-02   2.011634e+00   9.942165e+01
    FW           300   1.122811e-05   5.000000e-02   2.561057e+00   1.171391e+02
    FW           400   6.334101e-06   5.000000e-02   3.191104e+00   1.253485e+02
    FW           500   4.028960e-06   5.000000e-02   3.886511e+00   1.286501e+02
    FW           600   2.823896e-06   5.000000e-02   4.605336e+00   1.302837e+02
    FW           700   2.088682e-06   5.000000e-02   5.375874e+00   1.302114e+02
    FW           800   1.569986e-06   5.000000e-02   6.168279e+00   1.296958e+02
    FW           900   1.258972e-06   5.000000e-02   6.978978e+00   1.289587e+02
    FW          1000   9.944106e-07   5.000000e-02   7.812455e+00   1.280007e+02
  Last          1000   9.944106e-07   5.000000e-02   7.823049e+00   1.278274e+02
----------------------------------------------------------------------------------

Plotting the resulting trajectories

labels = ["BCFW - Full", "BCFW - Cyclic", "BCFW - Stochastic", "AFW", "AP"]

plot_trajectories(trajectories, labels, xscalelog=true)

This page was generated using Literate.jl.