Separable Approximations and Decomposition Methods for the Augmented Lagrangian

In this paper we study decomposition methods based on separable approximations for mini-mizing the augmented Lagrangian. In particular, we study and compare the Diagonal Quadratic Approximation Method (DQAM) of Mulvey and Ruszczyński [13] and the Parallel Coordinate Descent Method (PCDM) of Richtárik and Takác ̌ [23]. We show that the two methods are equivalent for feasibility problems up to the selection of a single step-size parameter. Further-more, we prove an improved complexity bound for PCDM under strong convexity, and show that this bound is at least 8(L′/L̄)(ω−1)2 times better than the best known bound for DQAM, where ω is the degree of partial separability and L ′ and L ̄ are the maximum and average of the block Lipschitz constants of the gradient of the quadratic penalty appearing in the augmented Lagrangian.