The Iterates of the Frank-Wolfe Algorithm May Not Converge

MaRDI QIDQ6391406zbMATH OpenFDO

Authors Jérôme Bolte, Cyrille W. Combettes, Edouard Pauwels

Publication date 17 February 2022

Abstract: The Frank-Wolfe algorithm is a popular method for minimizing a smooth convex function $f$ over a compact convex set $mathcalC$. 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{)}_{tinmathbbN}$. Under the usual assumptions, we design several counterexamples to the convergence of $(x_t{)}_{tinmathbbN}$, where $f$ is $d$-time continuously differentiable, $dgeq2$, and $f(x_t)omi{n}_{m}athcalCf$. Our counterexamples cover the cases of open-loop, closed-loop, and line-search step-size strategies. We do not assume emph{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{)}_{tinmathbbN}$.

This page was built for publication: The Iterates of the Frank-Wolfe Algorithm May Not Converge

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6391406)