Hybrid Jacobian and Gauss-Seidel proximal block coordinate update methods for linearly constrained convex programming
arXiv:1608.03928
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.
arXiv commentAccepted in SIAM Journal on Optimization
References in corpus (13)
- ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates
- Global Convergence of ADMM in Nonconvex Nonsmooth Optimization
- Coordinate Friendly Structures, Algorithms and Applications
- A Block Successive Upper Bound Minimization Method of Multipliers for Linearly Constrained Convex Optimization
- Parallel Multi-Block ADMM with o(1/k) Convergence
- A Three-Operator Splitting Scheme and its Optimization Applications
- On the convergence properties of a majorized ADMM for linearly constrained convex optimization problems with coupled objective functions
- Iteration Complexity Analysis of Block Coordinate Descent Methods
- Randomized First-Order Methods for Saddle Point Optimization
- Randomized Primal-Dual Proximal Block Coordinate Updates
- Extended ADMM and BCD for Nonseparable Convex Minimization Models with Quadratic Coupling Terms: Convergence Analysis and Insights
- Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming
- Alternating direction method of multipliers for regularized multiclass support vector machines