optimal gradient method

FAST FIRST-ORDER METHODS FOR COMPOSITE CONVEX OPTIMIZATION WITH BACKTRACKING

  • Xi Bai
  • Donald Goldfarb
  • Katya Scheinberg
    • Categories Nonsmooth Optimization Tags , , , , ,

    We propose new versions of accelerated first order methods for convex composite optimization, where the prox parameter is allowed to increase from one iteration to the next. In particular we show that a full backtracking strategy can be used within the FISTA \cite{Beck-Teboulle-2009} and FALM algorithms \cite{Goldfarb-Ma-Scheinberg-2010} while preserving their worst-case iteration complexities of $O(\sqrt{L(f)/\epsilon})$. … Read more

    Fast Multiple Splitting Algorithms for Convex Optimization

  • Donald Goldfarb
  • Shiqian Ma
    • Categories Convex and Nonsmooth Optimization Tags , , , , , , , , ,

    We present in this paper two different classes of general $K$-splitting algorithms for solving finite-dimensional convex optimization problems. Under the assumption that the function being minimized has a Lipschitz continuous gradient, we prove that the number of iterations needed by the first class of algorithms to obtain an $\epsilon$-optimal solution is $O(1/\epsilon)$. The algorithms in … Read more

    Fast Alternating Linearization Methods for Minimizing the Sum of Two Convex Functions

  • Donald Goldfarb
  • Shiqian Ma
  • Katya Scheinberg
    • Categories Convex and Nonsmooth Optimization Tags , , , , , , , , ,

    We present in this paper first-order alternating linearization algorithms based on an alternating direction augmented Lagrangian approach for minimizing the sum of two convex functions. Our basic methods require at most $O(1/\epsilon)$ iterations to obtain an $\epsilon$-optimal solution, while our accelerated (i.e., fast) versions of them require at most $O(1/\sqrt{\epsilon})$ iterations, with little change in … Read more