LINEAR CONVERGENCE RATE OF THE GENERALIZED ALTERNATING DIRECTION METHOD OF MULTIPLIERS FOR A CLASS OF CONVEX MINIMIZATION PROBLEMS

Rencently, the generalized alternating direction method of multipliers (GADMM) proposed by Eckstein and Bertsekas has received intensive attention from a broad spectrum of areas. In this paper, we firstly prove some important inequalities for the sequence generated by the GADMM for solving the convex optimization problems and establish the local linear convergence rate of GADMM, which generalize the corresponding results in [D. Han and X. Yuan, Local linear convergence of the alternating direction method of multipliers for quadratic programs, SIAM J. Numer. Anal., 51 (2013), pp. 3446-3457] from quadratic programs case to the convex optimization problems. Secondly, we also establish the global linear convergence rate of GADMM for solving the convex optimization problems that the subdifferentials of the underlying functions are piecewise linear multifunctions.

Automated summary

This paper proves important inequalities and establishes local and global linear convergence rates for GADMM in solving convex optimization problems.