Daniel Rodriguez

Polytope conditioning and linear convergence of the Frank-Wolfe algorithm

  • Javier F. Peña
  • Daniel Rodriguez
    • Categories Convex Optimization Tags , ,

    It is known that the gradient descent algorithm converges linearly when applied to a strongly convex function with Lipschitz gradient. In this case the algorithm’s rate of convergence is determined by condition number of the function. In a similar vein, it has been shown that a variant of the Frank-Wolfe algorithm with away steps converges … Read more

    On the von Neumann and Frank-Wolfe Algorithms with Away Steps

  • Javier F. Peña
  • Daniel Rodriguez
  • Negar Soheili
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , ,

    The von Neumann algorithm is a simple coordinate-descent algorithm to determine whether the origin belongs to a polytope generated by a finite set of points. When the origin is in the interior of the polytope, the algorithm generates a sequence of points in the polytope that converges linearly to zero. The algorithm’s rate of convergence … Read more