FrankWolfe

Julia implementation for various Frank-Wolfe and Conditional Gradient variants

https://github.com/zib-iol/frankwolfe.jl

Science Score: 67.0%

This score indicates how likely this project is to be science-related based on various indicators:

✓
CITATION.cff file
Found CITATION.cff file
✓
codemeta.json file
Found codemeta.json file
✓
.zenodo.json file
Found .zenodo.json file
✓
DOI references
Found 3 DOI reference(s) in README
✓
Academic publication links
Links to: arxiv.org, zenodo.org
○
Committers with academic emails
○
Institutional organization owner
○
JOSS paper metadata
○
Scientific vocabulary similarity
Low similarity (14.2%) to scientific vocabulary

Keywords

conditional-gradients first-order-methods frank-wolfe hacktoberfest julia optimization optimization-algorithms

Keywords from Contributors

numerics hybrid-differential-equations interpretability programming-language pde julialang pinns polyhedra nonlinear-programming matrix-exponential

Last synced: 4 months ago · JSON representation ·

Repository

Julia implementation for various Frank-Wolfe and Conditional Gradient variants

Basic Info

Host: GitHub
Owner: ZIB-IOL
License: mit
Language: Julia
Default Branch: master
Homepage:
Size: 266 MB

Statistics

Stars: 111
Watchers: 4
Forks: 24
Open Issues: 27
Releases: 93

Topics

conditional-gradients first-order-methods frank-wolfe hacktoberfest julia optimization optimization-algorithms

Created almost 5 years ago · Last pushed 4 months ago

Metadata Files

Readme Contributing License Citation Authors

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 math \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:

FrankWolfe.jl: A high-performance and flexible toolbox for Frank-Wolfe algorithms and Conditional Gradients.

Installation

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

julia using Pkg Pkg.add("FrankWolfe")

or the master branch:

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

Getting started

Let's say we want to solve the following minimization problem math \min_{p \in Δ(n)} p_1^2 + \dots + p_n^2, where $Δ(n)= \{p \in R^n_{\geq 0} | p_1 + \dots + p_n =1\}$ is the probability simplex.

Using FrankWolfe.jl, let's write a minimal code solving this problem in dimension $n=3$. The main function is FrankWolfe.frank_wolfe and it requires:

a function f that computes the values of the objective function $f$;
a function grad! that computes in-place the gradient of the objective function $f$;
a subtype of FrankWolfe.LinearMinimizationOracle for which a method of FrankWolfe.compute_extreme_point has been implemented (see here);
a starting vector p0.

```julia julia> using FrankWolfe

objective function f(p) = p1^2 + ... + pn^2

julia> f(p) = sum(abs2, p)

in-place gradient computation for f thanks to '.='

julia> grad!(storage, p) = storage .= 2p

pre-defined type implementing the linear minimization oracle interface for the simplex

julia> lmo = FrankWolfe.ProbabilitySimplexOracle(1.)

starting vector (of dimension n=3)

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

an optimal solution is returned in p_opt

julia> popt, _ = frankwolfe(f, grad!, lmo, p0; verbose=true);

Vanilla Frank-Wolfe Algorithm. MEMORYMODE: FrankWolfe.InplaceEmphasis() STEPSIZE: Adaptive EPSILON: 1.0e-7 MAXITERATION: 10000 TYPE: Float64 MOMENTUM: nothing GRADIENTTYPE: Nothing

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 ```

Note that active-set based methods like the Away-step Frank-Wolfe and Blended Pairwise Conditional Gradients also include a post-processing step. In post-processing all values are recomputed and in particular the dual gap is computed at the current FW vertex, which might be slightly larger than the best dual gap observed as the gap is not monotonic. This is expected behavior.

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 julia> using TestEnv

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

necessary for plotting

julia> include("examples/plotutils.jl") julia> include("examples/linearregression.jl") ... ```

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

```julia using Plots using FrankWolfe

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

Owner

Name: IOL Lab
Login: ZIB-IOL
Kind: organization
Location: Germany

Website: https://iol.zib.de
Repositories: 27
Profile: https://github.com/ZIB-IOL

Working on optimization and learning at the intersection of mathematics and computer science

Citation (CITATION.bib)

% for modern features of the package and newer versions
@article{besancon2025improvedalgorithmsnovelapplications,
      title={Improved algorithms and novel applications of the {FrankWolfe.jl} library}, 
      author={Mathieu Besan{\c{c}}on and Sébastien Designolle and Jannis Halbey and Deborah Hendrych and Dominik Kuzinowicz and Sebastian Pokutta and Hannah Troppens and Daniel Viladrich Herrmannsdoerfer and Elias Wirth},
      year={2025},
      eprint={2501.14613},
      archivePrefix={arXiv},
      primaryClass={math.OC},
      url={https://arxiv.org/abs/2501.14613}, 
}

% general citation for the package and older versions
@article{besanccon2022frankwolfe,
  title={{FrankWolfe.jl}: A High-Performance and Flexible Toolbox for {Frank-Wolfe} Algorithms and Conditional Gradients},
  author={Besan{\c{c}}on, Mathieu and Carderera, Alejandro and Pokutta, Sebastian},
  journal={INFORMS Journal on Computing},
  year={2022},
  publisher={INFORMS}
}

% to use the monotonic step size strategies
@article{carderera2021simple,
  title={Simple steps are all you need: {Frank-Wolfe} and generalized self-concordant functions},
  author={Carderera, Alejandro and Besan{\c{c}}on, Mathieu and Pokutta, Sebastian},
  journal={Proceedings of Advances in Neural Information Processing Systems},
  volume={34},
  year={2021}
}

@article{carderera2024simple,
  title={Scalable {Frank-Wolfe} on Generalized Self-Concordant Functions via Simple Steps},
  author={Carderera, Alejandro and Besan{\c{c}}on, Mathieu and Pokutta, Sebastian},
  journal={SIAM Journal on Optimization},
  volume = {34},
  number = {3},
  pages = {2231-2258},
  doi = {10.1137/23M1616789},
  year={2024},
  publisher={SIAM},
  eprint={2105.13913},
  archivePrefix={arXiv},
  primaryClass={math.OC}
}

% for blended pairwise
@article{tsuji2022pairwise,
  title={Pairwise Conditional Gradients without Swap Steps and Sparser Kernel Herding},
  author={Tsuji, Kazuma and Tanaka, Ken’ichiro and Pokutta, Sebastian},
  journal={Proceedings of International Conference on Machine Learning},
  pages={21864--21883},
  year={2022},
}

% for the stochastic Frank-Wolfe with momentum
@InProceedings{pmlr-v162-macdonald22a,
  title = 	 {Interpretable Neural Networks with {Frank-Wolfe}: Sparse Relevance Maps and Relevance Orderings},
  author =       {Macdonald, Jan and Besan{\c{c}}on, Mathieu and Pokutta, Sebastian},
  booktitle = 	 {Proceedings of the 39th International Conference on Machine Learning},
  pages = 	 {14699--14716},
  year = 	 {2022},
  editor = 	 {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan},
  volume = 	 {162},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {17--23 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v162/macdonald22a/macdonald22a.pdf},
  url = 	 {https://proceedings.mlr.press/v162/macdonald22a.html},
}

% for active set sparsification
@inproceedings{wirth2024pivotingframeworkfrankwolfealgorithms,
      title={The Pivoting Framework: {Frank-Wolfe} Algorithms with Active Set Size Control}, 
      author={Wirth, Elias and Besançon, Mathieu and Pokutta, Sebastian},
      year={2025},
      eprint={2407.11760},
      archivePrefix={arXiv},
      primaryClass={math.OC},
      booktitle={The 28th International Conference on Artificial Intelligence and Statistics},
      url={https://arxiv.org/abs/2407.11760}
}

% for the secant line search
@inproceedings{hendrych2025secantlinesearchfrankwolfe,
      title={Secant Line Search for {Frank-Wolfe} Algorithms},
      author={Deborah Hendrych and Mathieu Besançon and David Martínez-Rubio and Sebastian Pokutta},
      year={2025},
      eprint={2501.18775},
      archivePrefix={arXiv},
      primaryClass={math.OC},
      url={https://arxiv.org/abs/2501.18775},
      booktitle={Forty-second International Conference on Machine Learning}
}

% for the direct solve active set
@misc{halbey2025efficientquadraticcorrectionsfrankwolfe,
      title={Efficient Quadratic Corrections for {Frank-Wolfe} Algorithms},
      author={Jannis Halbey and Seta Rakotomandimby and Mathieu Besançon and Sébastien Designolle and Sebastian Pokutta},
      year={2025},
      eprint={2506.02635},
      archivePrefix={arXiv},
      primaryClass={math.OC},
      url={https://arxiv.org/abs/2506.02635},
}

GitHub Events

Total

Fork event: 5
Create event: 86
Commit comment event: 43
Release event: 16
Issues event: 18
Watch event: 18
Delete event: 56
Member event: 3
Issue comment event: 89
Push event: 689
Pull request review comment event: 50
Pull request review event: 75
Pull request event: 138

Last Year

Fork event: 5
Create event: 86
Commit comment event: 43
Release event: 16
Issues event: 18
Watch event: 18
Delete event: 56
Member event: 3
Issue comment event: 89
Push event: 689
Pull request review comment event: 50
Pull request review event: 75
Pull request event: 138

Committers

Last synced: 9 months ago

All Time

Total Commits: 1,103
Total Committers: 24
Avg Commits per committer: 45.958
Development Distribution Score (DDS): 0.487

Past Year

Commits: 153
Committers: 11
Avg Commits per committer: 13.909
Development Distribution Score (DDS): 0.68

Top Committers

Name	Email	Commits
Mathieu Besançon	m**n@g**m	566
Sebastian Pokutta	2****a	264
alejandro-carderera	a**a@g**m	64
Sébastien Designolle	s**e@g**m	56
dhendryc	9****c	36
Jonathan Geuter	j**r@g**e	31
Jannis H	4****l	26
setarakotomandimby	8****2	14
hannahtro	4****o	12
github-actions[bot]	4****]	7
Guillaume Dalle	2****e	5
Zev Woodstock	w**k@z**e	4
dviladrich95	3****5	4
Elias Wirth	6****h	2
Zev Woodstock	9****k	2
Hendrych	d**c@m**e	2
Jeremiah	4****s	1
Victor Thouvenot	1****t	1
Wenjie Xiao	1****2	1
Troppens	h**n@m**e	1
Mathieu Besancon	b**n@z**e	1
Hendrych	d**c@o**e	1
CompatHelper Julia	c**y@j**g	1
ZWoodstock	9****k	1

Committer Domains (Top 20 + Academic)

zib.de: 2 julialang.org: 1 opt117.zib.de: 1 mob-009564.zib.de: 1 mob-009366.zib.de: 1 gmx.de: 1

Issues and Pull Requests

Last synced: 4 months ago

All Time

Total issues: 61
Total pull requests: 292
Average time to close issues: 10 months
Average time to close pull requests: 22 days
Total issue authors: 12
Total pull request authors: 20
Average comments per issue: 3.38
Average comments per pull request: 0.93
Merged pull requests: 241
Bot issues: 0
Bot pull requests: 7

Past Year

Issues: 16
Pull requests: 132
Average time to close issues: 18 days
Average time to close pull requests: 13 days
Issue authors: 8
Pull request authors: 11
Average comments per issue: 1.0
Average comments per pull request: 0.75
Merged pull requests: 97
Bot issues: 0
Bot pull requests: 3

View more stats

Top Authors

Issue Authors

matbesancon (22)
pokutta (13)
gdalle (8)
dhendryc (8)
JannisHal (2)
Mettush (1)
WenjieXiao-2022 (1)
lsandig (1)
alejandro-carderera (1)
giommazz (1)
odow (1)
sebastiendesignolle (1)
JuliaTagBot (1)

Pull Request Authors

matbesancon (156)
dhendryc (51)
JannisHal (44)
sebastiendesignolle (31)
pokutta (18)
gdalle (10)
WenjieXiao-2022 (9)
github-actions[bot] (8)
zevwoodstock (5)
dviladrich95 (5)
elwirth (4)
j-geuter (4)
odow (2)
victorthouvenot (2)
SetaR0202 (2)

Top Labels

Issue Labels

enhancement (8) good first issue (3) midterm (3) testing (2) documentation (2) bug (2) Code improvements (1) Low priority (1) blended_cg (1) performance (1)

Pull Request Labels

Packages

Total packages: 1
Total downloads:
- julia 24 total

Total dependent packages: 5
Total dependent repositories: 0
Total versions: 92

juliahub.com: FrankWolfe

Julia implementation for various Frank-Wolfe and Conditional Gradient variants

Documentation: https://docs.juliahub.com/General/FrankWolfe/stable/
License: MIT
Latest release: 0.5.6
published 5 months ago

Versions: 92
Dependent Packages: 5
Dependent Repositories: 0
Downloads: 24 Total

Rankings

Stargazers count: 11.9%

Average: 14.2%

Forks count: 16.4%

Last synced: 4 months ago

Dependencies

.github/workflows/TagBot.yml actions

JuliaRegistries/TagBot v1 composite

.github/workflows/ci.yml actions

actions/cache v1 composite
actions/checkout v2 composite
codecov/codecov-action v1 composite
julia-actions/julia-buildpkg v1 composite
julia-actions/julia-processcoverage v1 composite
julia-actions/julia-runtest v1 composite
julia-actions/setup-julia v1 composite

.github/workflows/documentation.yml actions

actions/checkout v2 composite
julia-actions/setup-julia latest composite

.github/workflows/CompatHelper.yml actions

FrankWolfe

Science Score: 67.0%

Keywords

Keywords from Contributors

Repository

Basic Info

Statistics

Topics

Metadata Files

README.md

FrankWolfe.jl

Overview

Installation

Getting started

objective function f(p) = p1^2 + ... + pn^2

in-place gradient computation for f thanks to '.='

pre-defined type implementing the linear minimization oracle interface for the simplex

starting vector (of dimension n=3)

an optimal solution is returned in p_opt

Type Iteration Primal Dual Dual Gap Time It/sec

Last 24 3.333333e-01 3.333332e-01 9.488992e-08 1.533181e+00 1.565373e+01

Documentation and examples

necessary for plotting

Owner

Citation (CITATION.bib)

GitHub Events

Total

Last Year

Committers

All Time

Past Year

Top Committers

Committer Domains (Top 20 + Academic)

Issues and Pull Requests

All Time

Past Year

Top Authors

Issue Authors

Pull Request Authors

Top Labels

Issue Labels

Pull Request Labels

Packages

juliahub.com: FrankWolfe

Rankings

Dependencies