## FrankWolfe.jl

Julia implementation for various Frank-Wolfe and Conditional Gradient variants
Popularity
73 Stars
Updated Last
1 Year Ago
Started In
January 2021

# FrankWolfe.jl

This package is a toolbox for Frank-Wolfe and conditional gradients algorithms.

## Overview

Frank-Wolfe algorithms were designed to solve optimization problems of the form `min_{x ∈ C} f(x)`, where `f` is a differentiable convex function and `C` is a convex and compact set. They are especially useful when we know how to optimize a linear function over `C` in an efficient way.

A paper presenting the package with mathematical explanations and numerous examples can be found here:

## Installation

The most recent release is available via the julia package manager, e.g., with

```using Pkg

or the master branch:

`Pkg.add(url="https://github.com/ZIB-IOL/FrankWolfe.jl", rev="master")`

## Getting started

Let's say we want to minimize the Euclidian norm over the probability simplex `Δ`. Using `FrankWolfe.jl`, this is what the code looks like (in dimension 3):

```julia> using FrankWolfe

julia> f(p) = sum(abs2, p)  # objective function

# # function d ⟻ argmin ⟨p,d⟩ st. p ∈ Δ
julia> lmo = FrankWolfe.ProbabilitySimplexOracle(1.)

julia> p0 = [1., 0., 0.]

julia> p_opt, _ = frank_wolfe(f, grad!, lmo, p0; verbose=true);

Vanilla Frank-Wolfe Algorithm.
MEMORY_MODE: FrankWolfe.InplaceEmphasis() STEPSIZE: Adaptive EPSILON: 1.0e-7 MAXITERATION: 10000 TYPE: Float64
[ 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  -1.000000e+00   2.000000e+00   0.000000e+00            Inf
Last            24   3.333333e-01   3.333332e-01   9.488992e-08   1.533181e+00   1.565373e+01
-------------------------------------------------------------------------------------------------

julia> p_opt
3-element Vector{Float64}:
0.33333334349923327
0.33333332783841896
0.3333333286623478```

## Documentation and examples

To explore the content of the package, go to the documentation.

Beyond those presented in the documentation, many more use cases are implemented in the `examples` folder. To run them, you will need to activate the test environment, which can be done simply with TestEnv.jl (we recommend you install it in your base Julia).

```julia> using TestEnv

julia> TestEnv.activate()
"/tmp/jl_Ux8wKE/Project.toml"

# necessary for plotting
julia> include("examples/plot_utils.jl")
julia> include("examples/linear_regression.jl")
...```

If you need the plotting utilities in your own code, make sure Plots.jl is included in your current project and run:

```using Plots
using FrankWolfe

include(joinpath(dirname(pathof(FrankWolfe)), "../examples/plot_utils.jl"))```

### Required Packages

View all packages