A Log-Quadratic Projection Method for Convex Feasibility Problems

A. Auslendera,*; Marc Teboulleb,†    a Laboratoire d'Econometrie de L'Ecole Polytechnique, 1 Rue Descartes, Paris 75005, France
b School of Mathematical Sciences, Tel-Aviv University, Ramat-Aviv 69978, Israel
* Partially supported by the French-Israeli Scientific Program Arc-en-Ciel.
† Partially supported by the French-Israeli Scientific Program Arc-en-Ciel and the Israeli Ministry of Science under Grant No. 9636-1-96.

1 INTRODUCTION

The convex feasibility (CF) problem consists of finding a point in the intersection of convex sets. It occurs in a wide variety of contexts within mathematics as well as in many applied sciences problems and particularly in image reconstruction problems. For nice surveys on CF problems, projections algorithms toward their solutions and an extensive bibliography we refer for example to [4] and [8]. Let Ci, i = 1,…, m be given closed convex set of p with a nonempty intersection C := C1∩…∩Cm. The CF problem then consists of finding some point x∈ C.

One the basic approach to solve the CF problem is simply to use projections onto each set Ci and to generate a sequence of points converging a solution of the CF problem. There are many ways of using projections to generate a solution to the CF problem, (see e.g., [4]. In this paper we will focus on the simple idea of averaging projections (barycenter method) which goes back at least to Cimmino [7] who has considered the special case when each Ci is a half-space. Later this method has been extended by Auslender [1], to general convex sets. Denoting by PCi the projection onto the set Ci the barycenter projection method consists of two main steps.

Barycenter Projection Method. Start with x0 ∈ n and generate the sequence {xk} via:

(i) Project on i:pki=PCi(xk),∀i=1,…,m,,

(ii) Average Projections: k+1=m−1∑i=1mpki.

More generally, in the averaging step, one can assign nonnegative weights such that ki≥w>0 and replace step (ii) above by

k+1=∑i=1mwki−1pki/∑i=1mwki−1.

Clearly step (ii) above is then recovered with the choice ki=m−1,∀k.

This basic algorithm produces a sequence {xk} which converges to a solution of the CF problem, provided the intersection C is assumed nonempty, see e.g., [1]. As already mentioned, there exists several other variants ([4], [8]) of projection types algorithms for solving the CF problem, but in order to make this paper self-contained and transparent we will focus only on the above idea of averaging projections. Yet, we would like to emphasize that the algorithm and results we developed below can be extended as well to many of these variants involving projections-based methods.

In many applications, the convex feasibility problem occurs in the nonnegative orthant, namely we search for a point ∈C∩ℝ+n. In such cases, even when the Ci are simple hyperplanes we do not have an explicit formula for the projection Ci∩ℝ+n, i.e., when intersecting the hyperplanes with the nonnegative orthant. In fact, in order to take into account the geometry of ∩ℝ+n, it appears more natural to use projections not necessarily based on Euclidean quadratic squared distances, but rather on some other type of projections-like operators that which will be able to ensure automatically the positiveness of the required point solving CF in these cases. This has lead several authors to consider non-quadratic distance-like functions. Most common has been the use of Breg- man type distances, see for example the work of Censor and Elfving [6] and references therein. Yet, when using non quadratic distance-like functions, the projections cannot be computed exactly or analytically. It is therefore required to build a nonorthogonal (nonlinear) projection algorithm which first allows to control the errors with inexact computations, and secondly allows for computing the projections efficiently, e.g., via Newton’s method. Previous works using non-quadratic projections do not address these issues. Motivated by these recent approaches based on nonorthogonal Bregman type projections, see e.g., [5], [6], in this paper we also suggest a nonorthogonal projection algorithm for CF, which is based on a Logarithmic-Quadratic (LQ) distance-like functional and is not of the Bregman-type. As we shall see, the LQ functional and its associated conjugate functional which also plays a key role in nonlinear projections, enjoy remarkable and very important properties not shared by any other non-quadratic distance-like functions previously used and proposed in the literature. We refer the reader to [2], [3], where the LQ-distance like functional has been introduced, for further details explaining its advantages over Bregman type distances and Csizar’s φ-divergence ([12]) when used for solving variational inequalities and convex programming problems. Further properties of the LQ functional are also given in Section 3. We derive a convergent projection algorithm, under very mild assumptions on the problems data and which address the two issues alluded above. We believe and hope that our contribution is a first step toward the development of various (other than barycentric type) efficient non-orthogonal projections methods for the convex feasibility problem arising in the non-negative orthant.

2 THE LOG-QUADRATIC PROJECTION

We begin by introducing the LQ distance-like functional used to generate the nonorthogonal projections. Let ν > μ > 0 be given fixed parameters, and define

t=ν2t−12+μt−logt−1ift>0+∞otherwise

Given φ as defined above, we define dφ for ,y∈ℝ++p by

φxy=∑j=1pyj2φxj/yj.

The functional dφ with φ as defined in (1) was first introduced in [2] and enjoys the following basic properties:

• dφ is an homogeneous function of order 2, i.e.,
dφ(αx,αy) = α2dφ(x,y), ∀α > 0.

• (x,y)∈ℝ++p×ℝ++p we have:

φxy≥0and,dφxy=0iffx=y.

The first property is obvious from the definition (1), while the second property follows from the strict convexity of φ and noting that φ(1) = φ′(1) = 0, which implies,

φ(t) ≥ 0, and φ(t) = 0 if and only if t = 1.

We define the Log-Quadratic (LQ for short) projection onto ∩ℝ+n, based on dφ via: for each ∈ℝ++p,

Cy:=argmindφxy:x∈C∩ℝ+p

Throughout this paper we make the following assumption: ∩ℝ++p≠∅.

Note that this assumption is very minimal (in fact a standard constraint qualification) and is necessary to make the LQ projection meaningful. It will be useful to use the notation

′ab:=a1φ′b1/a1,…,apφ′bp/apT∀a,b,∈ℝ++p

where...