Inherently Parallel Algorithms in Feasibility and Optimization and their Applications (eBook)

D. Butnariu, Y. Censor, S. Reich (Autoren)

eBook Download: PDF

2001 | 1. Auflage
516 Seiten
Elsevier Science (Verlag)
978-0-08-050876-4 (ISBN)

Infos

The Haifa 2000 Workshop on Inherently Parallel Algorithms for Feasibility and Optimization and their Applications brought together top scientists in this area. The objective of the Workshop was to discuss, analyze and compare the latest developments in this fast growing field of applied mathematics and to identify topics of research which are of special interest for industrial applications and for further theoretical study.

Inherently parallel algorithms, that is, computational methods which are, by their mathematical nature, parallel, have been studied in various contexts for more than fifty years. However, it was only during the last decade that they have mostly proved their practical usefulness because new generations of computers made their implementation possible in order to solve complex feasibility and optimization problems involving huge amounts of data via parallel processing. These led to an accumulation of computational experience and theoretical information and opened new and challenging questions concerning the behavior of inherently parallel algorithms for feasibility and optimization, their convergence in new environments and in circumstances in which they were not considered before their stability and reliability. Several research groups all over the world focused on these questions and it was the general feeling among scientists involved in this effort that the time has come to survey the latest progress and convey a perspective for further development and concerted scientific investigations. Thus, the editors of this volume, with the support of the Israeli Academy for Sciences and Humanities, took the initiative of organizing a Workshop intended to bring together the leading scientists in the field. The current volume is the Proceedings of the Workshop representing the discussions, debates and communications that took place. Having all that information collected in a single book will provide mathematicians and engineers interested in the theoretical and practical aspects of the inherently parallel algorithms for feasibility and optimization with a tool for determining when, where and which algorithms in this class are fit for solving specific problems, how reliable they are, how they behave and how efficient they were in previous applications. Such a tool will allow software creators to choose ways of better implementing these methods by learning from existing experience.

---

The Haifa 2000 Workshop on "e;Inherently Parallel Algorithms for Feasibility and Optimization and their Applications"e; brought together top scientists in this area. The objective of the Workshop was to discuss, analyze and compare the latest developments in this fast growing field of applied mathematics and to identify topics of research which are of special interest for industrial applications and for further theoretical study.Inherently parallel algorithms, that is, computational methods which are, by their mathematical nature, parallel, have been studied in various contexts for more than fifty years. However, it was only during the last decade that they have mostly proved their practical usefulness because new generations of computers made their implementation possible in order to solve complex feasibility and optimization problems involving huge amounts of data via parallel processing. These led to an accumulation of computational experience and theoretical information and opened new and challenging questions concerning the behavior of inherently parallel algorithms for feasibility and optimization, their convergence in new environments and in circumstances in which they were not considered before their stability and reliability. Several research groups all over the world focused on these questions and it was the general feeling among scientists involved in this effort that the time has come to survey the latest progress and convey a perspective for further development and concerted scientific investigations. Thus, the editors of this volume, with the support of the Israeli Academy for Sciences and Humanities, took the initiative of organizing a Workshop intended to bring together the leading scientists in the field. The current volume is the Proceedings of the Workshop representing the discussions, debates and communications that took place. Having all that information collected in a single book will provide mathematicians and engineers interested in the theoretical and practical aspects of the inherently parallel algorithms for feasibility and optimization with a tool for determining when, where and which algorithms in this class are fit for solving specific problems, how reliable they are, how they behave and how efficient they were in previous applications. Such a tool will allow software creators to choose ways of better implementing these methods by learning from existing experience.

Inhalt

Cover 1
Title Page 4
Copyright Page 5
Contents 10
Preface 8
Chapter 1. A Log-Quadratic Projection Method for Convex Feasibility Problems 12
Chapter 2. Projection Algorithms: Results and Open Problems 22
Chapter 3. Joint and Separate Convexity of the Bregman Distance 34
Chapter 4. A Parallel Algorithm for Non-Cooperative Resource Allocation Games 48
Chapter 5. Asymptotic Behavior of Quasi-Nonexpansive Mappings 60
Chapter 6. The Outer Bregman Projection Method for Stochastic Feasibility Problems in Banach Spaces 80
Chapter 7. Bregman-Legendre Multidistance Projection Algorithms for Convex Feasibility and Optimization 98
Chapter 8. Averaging Strings of Sequential Iterations for Convex Feasibility Problems 112
Chapter 9. Quasi-Fejérian Analysis of Some Optimization Algorithms 126
Chapter 10. On the Theory and Practice of Row Relaxation Methods 164
Chapter 11. From Parallel to Sequential Projection Methods and Vice Versa in Convex Feasibility: Results and Conjectures 198
Chapter 12. Accelerating the Convergence of the Method of Alternating Projections Via Line Search: A Brief Survey 214
Chapter 13. PICO: An Object-Oriented Framework for Parallel Branch and Bound 230
Chapter 14. Approaching Equilibrium in Parallel 278
Chapter 15. Generic Convergence of Algorithms for Solving Stochastic Feasibility Problems 290
Chapter 16. Superlinear Rate of Convergence and Optimal Acceleration Schemes in the Solution of Convex Inequality Problems 308
Chapter 17. Algebraic Reconstruction Techniques Using Smooth Basis Functions for Helical Cone-Beam Tomography 318
Chapter 18. Compact Operators as Products of Projections 336
Chapter 19. Parallel Subgradient Methods for Convex Optimization 346
Chapter 20. Directional Halley and Quasi-Halley Methods in N Variables 356
Chapter 21. Ergodic Convergence to a Zero of the Extended Sum of Two Maximal Monotone Operators 380
Chapter 22. Distributed Asynchronous Incremental Subgradient Methods 392
Chapter 23. Random Algorithms for Solving Convex Inequalities 420
Chapter 24. Parallel Iterative Methods for Sparse Linear Systems 434
Chapter 25. On the Relation Between Bundle Methods for Maximal Monotone Inclusions and Hybrid Proximal Point Algorithms 452
Chapter 26. New Optimized and Accelerated PAM Methods for Solving Large Non-Symmetric Linear Systems: Theory and Practice 468
Chapter 27. The Hybrid Steepest Descent Method for the Variational Inequality Problem Over the Intersection of Fixed Point Sets of Nonexpansive Mappings 484

Textauszug

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.

Abstract

The convex feasibility problem which consists of finding a point in the intersection of convex sets is considered. We suggest a barycenter type projection algorithm, where the usual squared Euclidean distance is replaced by a logarithmic-quadratic distance-like functional. This allows in particular for handling efficiently feasibility problems arising in the nonnegative orthant. The proposed method includes approximate projections and is proven globally convergent under the sole assumption that the given intersection is nonempty and the errors are controllable. Furthermore, we consider the important special case involving the intersection of hyperplanes with the nonnegative orthant and show how in this case the projections can be efficiently computed via Newton's method.

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

  (1)

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

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

  (2)

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.

  (3)

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

  (4)

where...

Produkt-Details

• Erscheint lt. Verlag: 18.6.2001
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Theorie / Studium
• Themenwelt: Mathematik / Informatik ► Mathematik ► Algebra
• Themenwelt: Mathematik / Informatik ► Mathematik ► Analysis
• Themenwelt: Mathematik / Informatik ► Mathematik ► Angewandte Mathematik
• Themenwelt: Mathematik / Informatik ► Mathematik ► Finanz- / Wirtschaftsmathematik
• Themenwelt: Naturwissenschaften
• Themenwelt: Technik
• ISBN-10: 0-08-050876-6 / 0080508766
• ISBN-13: 978-0-08-050876-4 / 9780080508764