Inverse Problems · 2005 · 165 citations · 10 references
Natural SciencesComputer ScienceAlgorithmsOptimizationTheory Of ComputationConstrained OptimizationConvex OptimizationLinear ProgrammingMatrix ComputationNonlinear ProgrammingConvex Feasibility ProblemsConvex SetsProjectionsSpectral Radius
The split feasibility problem (SFP) seeks a point \(x\) in a convex set \(C\) whose image under a linear map \(A\) lies in another convex set \(Q\); Byrne’s CQ algorithm solves it via projections onto \(C\) and \(Q\), but exact projections can be difficult to compute. The study aims to develop several algorithms based on Byrne’s CQ algorithm to solve the split feasibility problem. These algorithms modify the CQ framework to avoid exact projections onto the convex sets, making them more practical and easier to implement. Compared with the CQ algorithm, the proposed methods are more practical, easier to implement, and can be regarded as improvements of the CQ algorithm.
Let C and Q be nonempty, closed convex sets in Rn and Rm respectively, and A be an m × n real matrix. The split feasibility problem (SFP) is to find x ∊ C with Ax ∊ Q, if such points exist. Byrne proposed the following CQ algorithm to solve the SFP: where γ ∊ (0, 2/ρ(ATA)) with ρ(ATA) the spectral radius of the matrix ATA and PC and PQ denote the orthogonal projections onto C and Q, respectively. However, in some cases, it is difficult or even impossible to compute PC and PQ exactly. In this paper, based on the CQ algorithm, we present several algorithms to solve the SFP. Compared with the CQ algorithm, our algorithms are more practical and easier to implement. They can be regarded as improvements of the CQ algorithm.
10
Practical methods of optimization
Mathematics and Computers in Simulation · 1988 · 5.9K citations
On Projection Algorithms for Solving Convex Feasibility Problems
Heinz H. Bauschke, Jonathan M. Borwein · SIAM Review · 1996 · 1.7K citations
Computing, Mathematics, Algorithms +11