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, vol. 49, n° 4, novembre 2024, p. 2049–2802.
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