论文标题
Frank-Wolfe算法的迭代可能不会融合
The Iterates of the Frank-Wolfe Algorithm May Not Converge
论文作者
论文摘要
Frank-Wolfe算法是一种流行的方法，可在紧凑型凸套装$ \ MATHCAL {C} $上最小化光滑的凸功能$ f $。尽管许多收敛结果是根据函数值得出的，但是关于迭代$（x_t）_ {t \ in \ Mathbb {n}} $的迭代序列的收敛行为几乎一无所知。在通常的假设下，我们设计了几个反例，以$（x_t）_ {t \ in \ mathbb {n}} $的收敛性，其中$ f $是$ f $ as $ d $ - time连续区分，$ d \ geq2 $，$ d \ geq2 $和$ f（x_t）我们的反例涵盖了开环，闭环和线路搜索的步进策略。我们不假设线性最小化甲骨文的\ emph {mildspectife}，因此我们的结果不管其返回的点如何，都证明了$（x_t）_ {t \ in \ mathbb {n}} $的收敛行为中的基本病理。
The Frank-Wolfe algorithm is a popular method for minimizing a smooth convex function $f$ over a compact convex set $\mathcal{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 $(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\geq2$, 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. 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)_{t\in\mathbb{N}}$.
