Projection Methods for Feasibility and their Extensions for Solving General Convex Nondifferentiable Constrained Optimization Problems

Abstract

Sequential orthogonal projections onto convex sets (POCS) is a very well known method for solving convex feasibility problems arising in many important areas of application, especially in signal processing, computed tomography and many other large scale inverse problems as well. It often occurs that the problem to be solved is not feasible, and, in that case, convergence issues arise. Then, POCS should be conveniently underrelaxed, in order to get a least squares solution (a point that minimizes the sum of the distances to the convex sets). This underrelaxation that overcomes unfeasibility is a clue for the extension of POCS to more general methods for solving general not necessarily differentiable convex optimization problems. In this article, we present a generalization of POCS that consists of: 1) substituting the exact projections by subgradient projections for the sets which have a nonempty intersection (constraints set), plus 2) an underrelaxed negative gradient step defined by the subgradient of the function to be minimized. We present convergence proofs and some numerical experiments,
illustrating the behavior of the method as an application of the new uncertainty principles to image reconstruction from incomplete projections.