New analysis of linear convergence of gradient-type methods via unifying error bound conditions (Q2297652)

Unconstrained optimization problems in $\mathbb R^n$ are considered with the corresponding gradient descent method with constant step size. Residual measure operators for a given function are defined, and some related error bounds conditions are introduced. The interplay, or the equivalence, among such conditions, are discussed. By using the negative of residual measure operator as a descent direction, an abstract gradient-type method is defined, and its linear convergence is proved. Then necessary and sufficient conditions are obtained for linear convergence of the gradient method, the proximal point algorithm and the forward-backward splitting algorithm, also for possibly non-convex problems. Linear convergence is also shown for proximal alternating linearized minimization and Nesterov's accelerated forward-backward algorithm.