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")

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   3.055602e-01   3.272678e+03
  5.000047e-02
    FW          2000   5.000000e-02   4.999558e-02   4.423306e-06   3.191504e-01   6.266638e+03
  5.000000e-02
  Last          2445   5.000000e-02   4.999898e-02   1.022986e-06   3.955470e-01   6.181313e+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   5.350406e-02   1.869017e+04
  5.000047e-02
    FW          2000   5.000000e-02   4.999569e-02   4.308009e-06   6.615722e-02   3.023101e+04
  5.000000e-02
  Last          2446   5.000000e-02   4.999898e-02   1.018029e-06   7.205435e-02   3.394660e+04
-------------------------------------------------------------------------------------------------
  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   1.000000e+00           -Inf            Inf   0.000000e+00            Inf
----------------
        Infeas
----------------

  1.000000e+00
    FW          1000   5.000030e-02   4.990779e-02   9.251220e-05   8.495725e-02   1.177063e+04
  5.000030e-02
    FW          2000   5.000000e-02   4.999607e-02   3.926060e-06   1.299524e-01   1.539026e+04
  5.000000e-02
  Last          2410   5.000000e-02   4.999901e-02   9.945886e-07   1.355272e-01   1.778241e+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           158   5.000000e-02   4.999922e-02   7.835690e-07   3.430922e-01   4.605175e+02             86
----------------------------------------------------------------------------------------------------------------
  5.000000e-02
----------------
    PP           158   5.000000e-02   4.999922e-02   7.835690e-07   4.120018e-01   3.834935e+02             86
----------------------------------------------------------------------------------------------------------------
  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.012252e-01   2.006126e-01   0.000000e+00            Inf
    FW           100   1.045308e-04   5.000040e-02   8.288678e-01   1.206465e+02
    FW           200   2.524997e-05   5.000002e-02   1.968423e+00   1.016042e+02
    FW           300   1.122811e-05   5.000000e-02   3.490186e+00   8.595531e+01
    FW           400   6.334101e-06   5.000000e-02   5.177774e+00   7.725327e+01
    FW           500   4.028960e-06   5.000000e-02   7.295883e+00   6.853180e+01
    FW           600   2.823896e-06   5.000000e-02   9.277288e+00   6.467407e+01
    FW           700   2.088682e-06   5.000000e-02   1.134125e+01   6.172157e+01
    FW           800   1.569986e-06   5.000000e-02   1.388669e+01   5.760913e+01
    FW           900   1.258972e-06   5.000000e-02   1.626778e+01   5.532409e+01
    FW          1000   9.944106e-07   5.000000e-02   1.875783e+01   5.331108e+01
  Last          1000   9.944106e-07   5.000000e-02   1.878335e+01   5.323863e+01
----------------------------------------------------------------------------------

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.