Xin Liu, 中国科学院


A Parallel Line Search Subspace Correction Method for Composite Convex Optimizatio


We investigate a parallel subspace correction framework for composite convex optimization. The variables are first divided into a few blocks based on certain rules. At each iteration, the algorithms solve a suitable subproblem on each block simultaneously, construct a search direction by combining their solutions on all blocks, then identify a new point along this direction using a step size satisfying the Armijo line search condition. They are called PSCLN and PSCLO, respectively, depending on whether there are overlapping regions between two immediately adjacent blocks of variables. Their convergence is established under mild assumptions. We compare PSCLN and PSCLO with the parallel version of the fast iterative thresholding algorithm and the fixed-point continuation method using the Barzilar-Borwein step size and the greedy coordinate block descent method for solving the ell_1-regularized minimization problems. Our numerical results show that PSCLN and PSCLO can run fast and return solutions no worse than those from the state-of-the-art algorithms. It is also observed that the overlapping domain decomposition scheme is helpful when the data of the problem has certain special structures.


Qian Dong, Zaiwen Wen and Yaxiang Yuan

« Back