The Iterates of the Frank–Wolfe Algorithm May Not Converge

Jérôme Bolte, Cyrille W. Combettes () and Edouard Pauwels ()
Additional contact information
Cyrille W. Combettes: Toulouse School of Economics, Université Toulouse Capitole, 31080 Toulouse, France
Edouard Pauwels: Toulouse School of Economics, Institut Universitaire de France, 31080 Toulouse, France

Mathematics of Operations Research, 2024, vol. 49, issue 4, 2565-2578

Abstract: The Frank–Wolfe algorithm is a popular method for minimizing a smooth convex function f over a compact convex set 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 ∈ N . Under the usual assumptions, we design several counterexamples to the convergence of ( x t ) t ∈ N , where f is d -time continuously differentiable, d ⩾ 2 , and f ( x t ) → min 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 ∈ N .

Keywords: Primary: 52A41; 90C25; constrained optimization; Frank–Wolfe algorithm; iterate convergence (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.0057 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:49:y:2024:i:4:p:2565-2578

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().