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

Yang, Qingzhi

Inverse Probl. 20, No. 4, 1261-1266 (2004).

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.

Reviewer: Rémi Vaillancourt (Ottawa)

MSC:

65F30	Other matrix algorithms (MSC2010)
65F10	Iterative numerical methods for linear systems

Keywords:

relaxed CQ algorithm; split feasibility problem; convergence