The Iterates of the Frank-Wolfe Algorithm May Not Converge

2022/02/17 by Jérôme Bolte, Bolte, Jérôme, Cyrille W. Combettes +2 · 1 citation
Computer Science · Mathematics · #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Optimization and Control (math.OC) #Optimization and Variational Analysis #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2202.08711

openalex publication_date 2022/02/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

The Frank-Wolfe algorithm is a popular method for minimizing a smooth convex function f over a compact convex set C. While many convergence results have been derived in terms of function values, hardly nothing is known about the convergence behavior of the sequence of iterates (x_t)_t∈ℕ. Under the usual assumptions, we design several counterexamples to the convergence of (x_t)_t∈ℕ, where f is d-time continuously differentiable, d≥2, and f(x_t)→min_Cf. Our counterexamples cover the cases of open-loop, closed-loop, and line-search step-size strategies. We do not assume misspecification of the linear minimization oracle and our results thus hold regardless of the points it returns, demonstrating the fundamental pathologies in the convergence behavior of (x_t)_t∈ℕ.

Cited by

• Muon Optimizes Under Spectral Norm Constraints

Related

• The Frank-Wolfe algorithm: a short introduction
• The Frank-Wolfe Algorithm: A Short Introduction
• Convergence Analysis of the Frank-Wolfe Algorithm and Its Generalization in Banach Spaces
• Convergence Rate of Frank-Wolfe for Non-Convex Objectives
• Improved convergence rates for the multiobjective Frank-Wolfe method