Optimization Online


A Parallel Line Search Subspace Correction Method for Composite Convex Optimization

Qian Dong (dongqian***at***lsec.cc.ac.cn)
Xin Liu (liuxin***at***lsec.cc.ac.cn)
Zaiwen Wen (wenzw***at***math.pku.edu.cn)
Yaxiang Yuan (yyx***at***lsec.cc.ac.cn)

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 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.

Keywords: line search, block coordinate descent method, domain decomposition, Jacobian-type iteration, distributed optimization.

Category 1: Optimization Software and Modeling Systems (Parallel Algorithms )

Category 2: Convex and Nonsmooth Optimization

Citation: October 2014

Download: [PDF]

Entry Submitted: 10/07/2014
Entry Accepted: 10/08/2014
Entry Last Modified: 12/18/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society