Optimization Online


Perturbation resilience and superiorization of iterative algorithms

Yair Censor (yair***at***math.haifa.ac.il)
Ran Davidi (r_davidi***at***yahoo.com)
Gabor T. Herman (gabortherman***at***yahoo.com)

Abstract: Iterative algorithms aimed at solving some problems are discussed. For certain problems, such as finding a common point in the intersection of a finite number of convex sets, there often exist iterative algorithms that impose very little demand on computer resources. For other problems, such as finding that point in the intersection at which the value of a given function is optimal, algorithms tend to need more computer memory and longer execution time. A methodology is presented whose aim is to produce automatically for an iterative algorithm of the first kind a "superiorized version" of it that retains its computational efficiency but nevertheless goes a long way towards solving an optimization problem. This is possible to do if the original algorithm is "perturbation resilient," which is shown to be the case for various projection algorithms for solving the consistent convex feasibility problem. The superiorized versions of such algorithms use perturbations that steer the process in the direction of a superior feasible point, which is not necessarily optimal, with respect to the given function. After presenting these intuitive ideas in a precise mathematical form, they are illustrated in image reconstruction from projections for two different projection algorithms superiorized for the function whose value is the total variation of the image.

Keywords: iterative algorithms, convex feasibility problem, superiorization, perturbation resilience, projection methods.

Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization )

Category 2: Applications -- Science and Engineering (Biomedical Applications )

Citation: Inverse Problems, vol. 26 (2010) 065008 (12pp).

Download: [PDF]

Entry Submitted: 04/29/2010
Entry Accepted: 04/29/2010
Entry Last Modified: 05/21/2010

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