The Iterates of the Frank-Wolfe Algorithm May Not Converge

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.