# Frank-Wolfe Algorithms: Sparsity Guarantees and an Application to Robust Optimization

Mathieu Besançon

► To cite this version:

Mathieu Besançon. Frank-Wolfe Algorithms: Sparsity Guarantees and an Application to Robust Optimization. ROADEF 2025 - 26ème Congrès annuel de la Société française de recherche opérationnelle et d'aide à la décision, Société française de recherche opérationnelle et d'aide à la décision, Feb 2025, Champs-Sur-Marne, France. pp.1-1. hal-04979715

HAL Id: hal-04979715

https://hal.science/hal-04979715v1

Submitted on 6 Mar 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Frank-Wolfe Algorithms: Sparsity Guarantees and an Application to Robust Optimization

Mathieu Besançon¹

Université Grenoble Alpes, Inria, CNRS, LIG
mathieu.besancon@inria.fr

**Keywords** : nonlinear optimization, first-order methods

**Introduction.** Frank-Wolfe (FW) methods are a class of nonlinear optimization algorithms over a compact constraint set leveraging first-order information of the objective and linear optimization on the constraints. They have risen in popularity in the last decade for their applications in operations research and learning, see, e.g., [3] for a recent overview of the method and some applications.

In this talk, we will first present a recently proposed enhancement of all Frank-Wolfe algorithms that ensure that the iterates remain sparse, in the sense that they are formed as a convex combination of a low number of vertices. We will then view an application of FW to robust optimization.

**Sparsity Guarantees for Frank-Wolfe.** In a first part, we will present recent progress on the pivoting framework that modifies Frank-Wolfe variants, ensuring the sparsity of the iterate. We will then introduce the so-called active set identification property of some FW variants [2] and how they can be leveraged to ensure sparser iterates in a so-called *pivoting* framework [4].

**Frank-Wolfe for robust optimization under an oracle model.** In the second part of the talk, we will focus on recent applications of FW or FW-inspired methods to tackle robust optimization under an oracle setting [1]. We will highlight how different approaches from the literature are connected through the lens of these algorithms or are dual of each other, including a recent simplicial decomposition, a cutting plane, and a FW approach with Nesterov smoothing.

**Funding** This research benefited from the support of the FMJH Program PGMO.

## References

[1] Mathieu Besançon and Jannis Kurtz. A Frank-Wolfe algorithm for oracle-based robust optimization, 2024.

[2] Immanuel M Bomze, Francesco Rinaldi, and Damiano Zeffiro. Active set complexity of the away-step Frank-Wolfe algorithm. *SIAM Journal on Optimization*, 30(3):2470–2500, 2020.

[3] Gábor Braun, Alejandro Carderera, Cyrille W Combettes, Hamed Hassani, Amin Karbasi, Aryan Mokhtari, and Sebastian Pokutta. Conditional gradient methods. *arXiv preprint arXiv:2211.14103*, 2022.

[4] Elias Wirth, Mathieu Besançon, and Sebastian Pokutta. The pivoting framework: Frank-Wolfe algorithms with active set size control, 2024.