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 constraints, 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 multiblock

Block coordinate update (BCU) methods enjoy low per-update computational complexity because every time only one or a few block variables would need to be updated among possibly a large number of blocks. They are also easily parallelized and thus have been particularly popular for solving problems involving large-scale dataset and/or variables. In this paper, we propose a primaldual BCU method for solving linearly constrained convex program with multi-block variables. The method is an accelerated version of a primaldual algorithm proposed by the authors, which applies randomization in selecting block variables to update and establishes an <i>O</i>(1/<i>t</i>) convergence rate under convexity assumption. We show that the rate can be accelerated to O ( 1 / t 2 ) if the objective is strongly convex. In addition, if one block variable is independent of the others in the objective, we then show that the algorithm can

In this paper, we propose a randomized primaldual proximal block coordinate updating framework for a general multi-block convex optimization model with coupled objective function and linear constraints. Assuming mere convexity, we establish its <i>O</i>(1/<i>t</i>) convergence rate in terms of the objective value and feasibility measure. The framework includes several existing algorithms as special cases such as a primaldual method for bilinear saddle-point problems (PD-S), the proximal Jacobian alternating direction method of multipliers (Prox-JADMM) and a randomized variant of the ADMM for multi-block convex optimization. Our analysis recovers and/or strengthens the convergence properties of several existing algorithms. For example, for PD-S our result leads to the same order of convergence rate without the previously assumed boundedness condition on the constraint sets, and for Prox-JADMM the new