The relaxed CQ algorithm solving the split feasibility problem. (English) Zbl 1066.65047

Let \(C\) and \(Q\) be nonempty closed convex sets in \({\mathbb R}^N\) and \({\mathbb R}^M\), respectively, and \(A\) an \(M\times N\) real matrix. The split feasibility problem (SFP) is to find \(x\in C\) with \(Ax\in Q\), if such \(x\) exits. The author presents the following relaxed CQ algorithm: \(x^{k+1}=P_{C_k}(x^k+\gamma A^T(P_{Q_k}-I)Ax^k)\) for solving the SFP by replacing the sets \(C=\{x\in {\mathbb R}^N\,| \, c(x)\leq 0\}\) and \(Q=\{y\in {\mathbb R}^M\,| \, q(y)\leq 0\}\), where \(c\) and \(q\) are convex functions, by the larger sets \(C_k=\{x\in {\mathbb R}^N\,| \, c(x^k)+\langle \xi^k,x-x^k\rangle \leq 0\}\) and \(Q_k=\{y\in {\mathbb R}^M\,| \, q(Ax^k)+\langle \eta^k,y-Ax^k\rangle \leq 0\}\) where the subgradients are \(\xi^k\in\partial c(x^k)\) and \(\eta^k\in\partial q(Ax^k)\). Here \(P_{C_k}\) and \(P_{Q_k}\) are projections onto \(C_k\) and \(Q_k\), and \(\gamma\in(0,2/L)\) where \(L\) denotes the largest eigenvalue of \(A^TA\). The convergence of the algorithm is established and another algorithm for SFP is given.


65F30 Other matrix algorithms (MSC2010)
65F10 Iterative numerical methods for linear systems
Full Text: DOI