Block-coordinate primal-dual method for nonsmooth minimization over linear constraints (Q2415202)

The authors propose a randomized block-coordinate extension of the Chambolle-Pock primal-dual proximal-point type algorithm for computationally solving a class of bilevel optimization problems that generalize the optimization problems consisting in minimizing convex and separable nonsmooth functions subject to linear constraints. Some other problems where the algorithm can be applied are mentioned: linear programming, composite minimization, distributed optimization, inverse problems. The convergence of the method is guaranteed under quite weak assumptions that do not involve usually standard additional hypotheses like smoothness or strong convexity of the objective function or full-rank condition on the involved matrix and permit applying the algorithm even to misspecified or noisy systems. Possible generalizations concerning adding strong convexity hypotheses or additional smooth terms to the objective function, or parallelization are briefly discussed, too, being followed by some numerical experiments on basis pursuit with and without noise and robust principal component analysis where the new method outperforms existing ones from the literature. For the entire collection see [Zbl 1407.90006].