performance estimation

The exact worst-case convergence rate of the alternating direction method of multipliers

  • Moslem Zamani
  • Hadi Abbaszadehpeivasti
  • Etienne de Klerk
    • Categories Convex Optimization Tags , , ,

    Recently, semidefinite programming performance estimation has been employed as a strong tool for the worst-case performance analysis of first order methods. In this paper, we derive new non-ergodic convergence rates for the alternating direction method of multipliers (ADMM) by using performance estimation. We give some examples which show the exactness of the given bounds. We … Read more

    Exact Worst-case Performance of First-order Methods for Composite Convex Optimization

  • François Glineur
  • Julien M. Hendrickx
  • Adrien B. Taylor
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , , , , , , ,

    We provide a framework for computing the exact worst-case performance of any algorithm belonging to a broad class of oracle-based first-order methods for composite convex optimization, including those performing explicit, projected, proximal, conditional and inexact (sub)gradient steps. We simultaneously obtain tight worst-case guarantees and explicit instances of optimization problems on which the algorithm reaches this … Read more