Document de travail

The Iterates of the Frank-Wolfe Algorithm May Not Converge

Jérôme Bolte, Cyrille Combettes et Edouard Pauwels

Résumé

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 (xt)t2N. Under the usual assumptions, we design several counterexamples to the convergence of (xt)t2N, where f is d-time continuously differentiable, d > 2, and f(xt) ---> minC f. 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 (xt)t2N.

Remplacé par

Jérôme Bolte, Cyrille Combettes et Edouard Pauwels, « The Iterates of the Frank–Wolfe Algorithm May Not Converge », Mathematics of Operations Research, 2024, à paraître.

Référence

Jérôme Bolte, Cyrille Combettes et Edouard Pauwels, « The Iterates of the Frank-Wolfe Algorithm May Not Converge », TSE Working Paper, n° 22-1311, février 2022.

Voir aussi

Publié dans

TSE Working Paper, n° 22-1311, février 2022