The method of reflection-projection for convex feasibility problems with an obtuse cone

Heinz Bauschke (bauschkececm.sfu.ca)
Serge Kruk (sgkrukacm.org)

Abstract: The convex feasibility problem asks to find a point in the intersection of finitely many closed convex sets in Euclidean space. This problem is of fundamental importance in mathematics and physical sciences, and it can be solved algorithmically by the classical method of cyclic projections. In this paper, the case where one of the constraints is an obtuse cone is considered. Because the nonnegative orthant as well as the set of positive semidefinite symmetric matrices form obtuse cones, we cover a large and substantial class of feasibility problems. Motivated by numerical experiments, the method of reflection-projection is proposed: it modifies cyclic projections in that it replaces the projection onto the obtuse cone by the corresponding reflection. This new method is not covered by the standard frameworks of projection algorithms because of the reflection. The main result states that the method does converge to a solution whenever the underlying convex feasibility problem is consistent. As prototypical applications, we discuss in detail the implementation of two-set feasibility problems aiming to find a nonnegative (resp. positive semidefinite) solution to linear constraints in $\R^n$ (resp. in $\Sn$, the space of symmetric $n$-by-$n$ matrices), and we report on numerical experiments. The behavior of the method for two inconsistent constraints is analyzed as well.

Keywords: convex feasibility problem, obtuse cone, projection methods, self-dual cone

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: Technical report, Oakland University, Rochester MI, February 2002

Download: [Compressed Postscript][PDF]

Entry Submitted: 02/25/2002
Entry Accepted: 02/25/2002
Entry Last Modified: 02/25/2002

Modify/Update this entry