Convergence analysis of some algorithms for convex optimization from variational analysis perspectives

Abstract

In this thesis, we focus on some canonical nonsmooth convex optimization problems, and study the local convergence rates for some benchmark numerical algorithms from variational analysis perspectives. We first consider the minimization of the sum of two convex functions, one of which is nonsmooth, and discuss how to derive the local linear convergence rates for the proximal gradient method (PGM), the proximal alternating linearized minimization (PALM) algorithm, and the randomized block coordinate proximal gradient method (R-BCPGM). A new analytic framework based on the error bound/calmness/metric subregularity condition is proposed for convergence rate analysis. We then consider a separable convex minimization problem with linear constraints, and apply the new analytic framework to study the alternating direction method of multipliers (ADMM). The local linear convergence rates are derived for the ADMM and its variants. We also propose a new globally convergent proximal Newton type method for a broad class of nonsmooth composite convex optimization problems without requiring strong convexity assumptions, and establish its local superlinear and quadratic convergence rates under the metric subregularity condition. Our analysis is based on sophisticated applications of some advanced variational analysis notations and techniques such as the calmness property, the metric subregularity property, the calm intersection theorem and perturbation analysis techniques.