String-Averaging Algorithms for Convex Feasibility with Infinitely Many Sets
| Autor: | Homeira Pajoohesh, T. Yung Kong, Gabor T. Herman |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
TheoryofComputation_MISCELLANEOUS
Iterative method Applied Mathematics String (computer science) Regular polygon 46N10 46N40 47H09 47H10 47J25 47N10 65F10 65J99 65K10 90C25 90C30 010103 numerical & computational mathematics 01 natural sciences Computer Science Applications Theoretical Computer Science 010101 applied mathematics Projection (mathematics) Intersection Optimization and Control (math.OC) Signal Processing FOS: Mathematics Limit of a sequence Point (geometry) Limit (mathematics) 0101 mathematics Algorithm Mathematics - Optimization and Control Mathematical Physics Mathematics |
| Popis: | Algorithms for convex feasibility find or approximate a point in the intersection of given closed convex sets. Typically there are only finitely many convex sets, but the case of infinitely many convex sets also has some applications. In this context, a \emph{string} is a finite sequence of points each of which is obtained from the previous point by considering one of the convex sets. In a \emph{string-averaging} algorithm, an iterative step from a first point to a second point computes a number of strings, all starting with the first point, and then calculates a (weighted) average of those strings' end-points: This average is that iterative step's second point, which is used as the first point for the next iterative step. For string-averaging algorithms based on strings in which each point either is the projection of the previous point on one of the convex sets or is equal to the previous point, we present theorems that provide answers to the following question: "How can the iterative steps be specified so that the string-averaging algorithm generates a convergent sequence whose limit lies in the intersection of the sets of a given convex feasibility problem?" This paper focuses on the case where the given collection of convex sets is infinite, whereas prior work on the same question that we are aware of has assumed the collection of convex sets is finite (or has been applicable only to a small subset of the algorithms we consider). The string-averaging algorithms that are shown to generate a convergent sequence whose limit lies in the intersection are also shown to be perturbation resilient, so they can be superiorized to generate sequences that also converge to a point of the intersection but in a manner that is superior with respect to some application-dependent criterion. 30 pages; 1 figure. This revised paper was prepared after the authors received comments from referees and others on the originally posted version |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|