Optimization Online


Finding the projection of a point onto the intersection of convex sets via projections onto halfspaces

L.M. Bregman (bregman***at***math.bgu.ac.il)
Y. Censor (yair***at***math.haifa.ac.il)
S. Reich (sreich***at***techunix.technion.ac.il)
Y. Zepkowitz-Malachi (yael***at***math.haifa.ac.il)

Abstract: We present a modification of Dykstra's algorithm which allows us to avoid projections onto general convex sets. Instead, we calculate projections onto either a halfspace or onto the intersection of two halfspaces. Convergence of the algorithm is established and special choices of the halfspaces are proposed. The option to project onto halfspaces instead of general convex sets makes the algorithm more practical. The fact that the halfspaces are quite general enables us to apply the algorithm in a variety of cases and to generalize a number of known projection algorithms. The problem of projecting a point onto the intersection of closed convex sets receives considerable attention in many areas of mathematics and physics as well as in other fields of science and engineering such as image reconstruction from projections.In this work we propose a new class of algorithms which allow projection onto certain super halfspaces, i.e., halfspaces which contain the convex sets. Each one of the algorithms that we present gives the user freedom to choose the specific super halfspace from a family of such halfspaces. Since projecting a point onto a halfspace is an easy task to perform, the new algorithms may be more useful in practical situations in which the construction of the super halfspaces themselves is not too difficult.

Keywords: Projections, Bregman projections, Convex sets, Best Approximation, Dykstra's Algorithm.

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization )

Category 3: Convex and Nonsmooth Optimization

Citation: Journal of Approximation Theory, Vol. 124 (2003), pp. 194-218.


Entry Submitted: 06/16/2003
Entry Accepted: 06/16/2003
Entry Last Modified: 10/04/2004

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society