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   3.410097e-01   2.932468e+03
  5.000047e-02
    FW          2000   5.000000e-02   4.999558e-02   4.423306e-06   3.532049e-01   5.662435e+03
  5.000000e-02
  Last          2445   5.000000e-02   4.999898e-02   1.022986e-06   4.360244e-01   5.607484e+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   1.573009e-02   6.357241e+04
  5.000047e-02
    FW          2000   5.000000e-02   4.999569e-02   4.308009e-06   3.460002e-02   5.780343e+04
  5.000000e-02
  Last          2446   5.000000e-02   4.999898e-02   1.018029e-06   4.342430e-02   5.632791e+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   5.732358e-01  -4.342676e+01   4.400000e+01   0.000000e+00            Inf
----------------
        Infeas
----------------

  5.732358e-01
    FW          1000   5.000037e-02   4.989919e-02   1.011781e-04   7.533197e-02   1.327458e+04
  5.000037e-02
    FW          2000   5.000000e-02   4.999626e-02   3.736708e-06   8.979164e-02   2.227379e+04
  5.000000e-02
  Last          2379   5.000000e-02   4.999897e-02   1.033050e-06   9.568041e-02   2.486402e+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   4.609343e-01   3.427820e+02             86
----------------------------------------------------------------------------------------------------------------
  5.000000e-02
----------------
    PP           158   5.000000e-02   4.999922e-02   7.835690e-07   5.664925e-01   2.789093e+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.087861e-01   2.043931e-01   0.000000e+00            Inf
    FW           100   1.045308e-04   5.000040e-02   9.125671e-01   1.095810e+02
    FW           200   2.524997e-05   5.000002e-02   2.027377e+00   9.864965e+01
    FW           300   1.122811e-05   5.000000e-02   3.463822e+00   8.660953e+01
    FW           400   6.334101e-06   5.000000e-02   5.169802e+00   7.737240e+01
    FW           500   4.028960e-06   5.000000e-02   6.914017e+00   7.231686e+01
    FW           600   2.823896e-06   5.000000e-02   8.780768e+00   6.833115e+01
    FW           700   2.088682e-06   5.000000e-02   1.077300e+01   6.497723e+01
    FW           800   1.569986e-06   5.000000e-02   1.283828e+01   6.231365e+01
    FW           900   1.258972e-06   5.000000e-02   1.494502e+01   6.022073e+01
    FW          1000   9.944106e-07   5.000000e-02   1.713209e+01   5.837001e+01
  Last          1000   9.944106e-07   5.000000e-02   1.715454e+01   5.829361e+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.