Perturbation Resilience and Superiorization of Iterative Algorithms

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 drive the process in the direction of the optimizer of 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.

Accepted for publication in Inverse Problems, 2010

Cited by in corpus (27)

• Algorithms for the Split Variational Inequality Problem
• The Split Common Null Point Problem
• Total variation superiorization schemes in proton computed tomography image reconstruction
• Superiorization: An optimization heuristic for medical physics
• Convergence and Perturbation Resilience of Dynamic String-Averaging Projection Methods
• Generalized Row-Action Methods for Tomographic Imaging
• Total Variation Superiorized Conjugate Gradient Method for Image Reconstruction
• Can Linear Superiorization Be Useful for Linear Optimization Problems?
• Convergence Properties of Dynamic String Averaging Projection Methods in the Presence of Perturbations
• Solutions to inexact resolvent inclusion problems with applications to nonlinear analysis and optimization
• Superiorized algorithm for reconstruction of CT images from sparse-view and limited-angle polyenergetic data
• A generalized projection-based scheme for solving convex constrained optimization problems
• Zero-Convex Functions, Perturbation Resilience, and Subgradient Projections for Feasibility-Seeking Methods
• A new convergence analysis and perturbation resilience of some accelerated proximal forward-backward algorithms with errors
• Computerized Tomography with Total Variation and with Shearlets
• Speedup of lexicographic optimization by superiorization and its applications to cancer radiotherapy treatment
• Hierarchical Convex Optimization by the Hybrid Steepest Descent Method with Proximal Splitting Operators -- Enhancements of SVM and Lasso
• Superiorized Adaptive Projected Subgradient Method with Application to MIMO Detection
• Accelerating two projection methods via perturbations with application to Intensity-Modulated Radiation Therapy
• Superiorization and Perturbation Resilience of Algorithms: A Continuously Updated Bibliography
• String-Averaging Algorithms for Convex Feasibility with Infinitely Many Sets
• Dykstra splitting and an approximate proximal point algorithm for minimizing the sum of convex functions
• Feasibility-based Fixed Point Networks
• Strict Fejér Monotonicity by Superiorization of Feasibility-Seeking Projection Methods
• Finite-Value Superiorization for Variational Inequality Problems
• Projected Subgradient Minimization versus Superiorization
• A Generalized Block-Iterative Projection Method for the Common Fixed Point Problem Induced by Cutters