A note on the CQ algorithm for the split feasibility problem
Biao Qu, Naihua Xiu · Inverse Problems · 2005
Let C and Q be nonempty closed convex sets in ℜ N and ℜ M , respectively, and A an M × N real matrix. The split feasibility problem (SFP) is to find x ∊ C with Ax ∊ Q , if such x exist. Byrne ( 2002 Inverse Problems 18 441–53 ) proposed a CQ algorithm with the following iterative scheme: where γ ∊ (0, 2/ L ), L denotes the largest eigenvalue of the matrix A T A , and P C and P Q denote the orthogonal projections onto C and Q , respectively. In his algorithm, Byrne assumed that the projections P C and P Q are easily calculated. However, in some cases it is impossible or needs too much work to exactly compute the orthogonal projection. Recently, Yang ( 2004 Inverse Problems 20 1261–6 ) presented a relaxed CQ algorithm, in which he replaced P C and P Q by and , that is, the orthogonal projections onto two halfspaces C k and Q k , respectively. Clearly, the latter is easy to implement. One common advantage of the CQ algorithm and the relaxed CQ algorithm is that computation of the matrix inverses is not necessary. However, they use a fixed stepsize related to the largest eigenvalue of the matrix A T A , which sometimes affects convergence of the algorithms. In this paper, we present modifications of the CQ algorithm and the relaxed CQ algorithm by adopting Armijo-like searches. The modified algorithms need not compute the matrix inverses and the largest eigenvalue of the matrix A T A , and make a sufficient decrease of the objective function at each iteration. We also show convergence of the modified algorithms under mild conditions.