A Parallel Line Search Subspace Correction Method for Composite Convex Optimization
- PDF / 762,453 Bytes
- 25 Pages / 439.37 x 666.142 pts Page_size
- 115 Downloads / 196 Views
A Parallel Line Search Subspace Correction Method for Composite Convex Optimization Qian Dong1 · Xin Liu1 · Zai-Wen Wen2 · Ya-Xiang Yuan1
Received: 7 October 2014 / Accepted: 6 February 2015 / Published online: 9 May 2015 © Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press and Springer-Verlag Berlin Heidelberg 2015
Abstract 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-
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), and 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).
B
Qian Dong [email protected] Xin Liu [email protected] Zai-Wen Wen [email protected] Ya-Xiang Yuan [email protected]
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
123
164
Q. Dong et al.
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 1 -regularized minimization problems. Our numerical results show that PSCLN and PSCLO can run fast and return solutions not worse 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. Keywords Line search · Block coordinate descent method · Domain decomposition · Jacobian-type iteration · Distributed optimization Mathematics Subject Classification
90C25 · 49M27
1 Introduction In this paper, we consider the composite convex optimization problem min ϕ(x) := f (x) + h(x),
x∈Rn
(1.1)
where f (x) is differentiable convex function and h(x) is a convex function that is possib
Data Loading...
