The Iterates of the Frank–Wolfe Algorithm May Not Converge

The Frank–Wolfe algorithm is a popular method for minimizing a smooth convex function f over a compact convex set $\mathcal{C}$. Whereas many convergence results have been derived in terms of function values, almost nothing is known about the convergence behavior of the sequence of iterates ${(x_t)}_{t\in \mathbb{N}}$. Under the usual assumptions, we design several counterexamples to the convergence of ${(x_t)}_{t\in \mathbb{N}}$, where f is d-time continuously differentiable, $d⩾2$, and $f(x_t)\to {\min }_{\mathcal{C}} f$. Our counterexamples cover the cases of open-loop, closed-loop, and line-search step-size strategies and work for any choice of the linear minimization oracle, thus demonstrating the fundamental pathologies in the convergence behavior of ${(x_t)}_{t\in \mathbb{N}}$.

Funding: The authors acknowledge the support of the AI Interdisciplinary Institute ANITI funding through the French “Investments for the Future – PIA3” program under the Agence Nationale de la Recherche (ANR) agreement [Grant ANR-19-PI3A0004], the Air Force Office of Scientific Research, Air Force Material Command, U.S. Air Force [Grants FA866-22-1-7012 and ANR MaSDOL 19-CE23-0017-0], ANR Chess [Grant ANR-17-EURE-0010], ANR Regulia, and Centre Lagrange.