The Iterates of the Frank-Wolfe Algorithm May Not Converge

• 成果类型: Article
• 署名作者: Bolte, Jerome; Combettes, Cyrille W.; Pauwelsb, Edouard
• 署名单位: Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics; Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics; Institut Universitaire de France
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.0057
• 发表日期: 2024
• 页码: 2565-2578
• 关键词: descent methods; minimization; nonconvex

摘要

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 (xt)t is an element of N. Under the usual assumptions, we design several counterexamples to the convergence of (xt)t is an element of N, where f is d-time continuously differentiable, dP 2, and f(xt) -> minC 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 (xt)t is an element of N.