Hybrid Jacobian and Gauss-Seidel proximal block coordinate update methods for linearly constrained convex programming

Abstract

Recent years have witnessed the rapid development of block coordinate update (BCU) methods, which are particularly suitable for problems involving large-sized data and/or variables. In optimization, BCU first appears as the coordinate descent method that works well for smooth problems or those with separable nonsmooth terms and/or separable constraints. As nonseparable constraints exist, BCU can be applied under primal-dual settings. In the literature, it has been shown that for weakly convex problems with nonseparable linear constraint, BCU with fully Gauss-Seidel updating rule may fail to converge and that with fully Jacobian rule can converge sublinearly. However, empirically the method with Jacobian update is usually slower than that with Gauss-Seidel rule. To maintain their advantages, we propose a hybrid Jacobian and Gauss-Seidel BCU method for solving linearly constrained multi-block structured convex programming, where the objective may have a nonseparable quadratic term and separable nonsmooth terms. At each primal block variable update, the method approximates the augmented Lagrangian function at an affine combination of the previous two iterates, and the affinely mixing matrix with desired nice properties can be chosen through solving a semidefinite programming. We show that the hybrid method enjoys the theoretical convergence guarantee as Jacobian BCU. In addition, we numerically demonstrate that the method can perform as well as Gauss-Seidel method and better than a recently proposed randomized primal-dual BCU method.

Accepted in SIAM Journal on Optimization

References in corpus (6)

• Global Convergence of ADMM in Nonconvex Nonsmooth Optimization
• Coordinate Friendly Structures, Algorithms and Applications
• A Three-Operator Splitting Scheme and its Optimization Applications
• Randomized Primal-Dual Proximal Block Coordinate Updates
• Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming
• Alternating direction method of multipliers for regularized multiclass support vector machines

Cited by in corpus (2)

• Randomized Primal-Dual Proximal Block Coordinate Updates
• Accelerated Primal-Dual Proximal Block Coordinate Updating Methods for Constrained Convex Optimization