A Parallel Line Search Subspace Correction Method for Composite Convex Optimization  

作　　者：Qian Dong Xin Liu Zai-Wen Wen Ya-Xiang Yuan 

机构地区：[1]State Key Laboratory of Scientific and Engineering Computing,Academy of Mathematics and Systems Science,Chinese Academy of Sciences,Beijing,China [2]Beijing International Center for Mathematical Research,Peking University,Beijing,China

出　　处：《Journal of the Operations Research Society of China》2015年第2期163-187,共25页中国运筹学会会刊（英文）

基　　金：Qian Dong was supported in part by the National Natural Science Foundation of China(Nos.11331012,11321061 and 11461161005);Xin Liu was supported in part by the National Natural Science Foundation of China(Nos.11101409,11331012,11471325 and 11461161005);China 863 Program(No.2013AA122902);the National Center for Mathematics and Interdisciplinary Sciences,Chinese Academy of Sciences;Zai-Wen Wen was supported in part by the National Natural Science Foundation of China(Nos.11322109 and 91330202);Ya-Xiang Yuan was supported in part by the National Natural Science Foundation of China(Nos.11331012,11321061 and 11461161005).

摘　　要：In this paper,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 imme-diately 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 Barzilai-Borwein step size and the greedy coordinate block descent method for solving the l1-regularized minimization problems.Our numerical results showthatPSCLN andPSCLOcan run fast and return solutions notworse than those from the state-of-theart algorithms on most test problems.It is also observed that the overlapping domain decomposition scheme is helpful when the data of the problem has certain special structures.

关 键 词：Line search Block coordinate descent method Domain decomposition Jacobian-type iteration Distributed optimization 

分 类 号：O17[理学—数学]