{
  "id": "2202.08711",
  "version": "v1",
  "published": "2022-02-17T15:33:04.000Z",
  "updated": "2022-02-17T15:33:04.000Z",
  "title": "The Iterates of the Frank-Wolfe Algorithm May Not Converge",
  "authors": [
    "Jérôme Bolte",
    "Cyrille W. Combettes",
    "Édouard Pauwels"
  ],
  "comment": "15 pages, 7 figures",
  "categories": [
    "math.OC"
  ],
  "abstract": "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}}$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-02-17T15:33:04.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "frank-wolfe algorithm",
      "convergence behavior",
      "smooth convex function",
      "compact convex set",
      "linear minimization oracle"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 15,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}