Superiorization

Superiorization is an iterative method for constrained optimization. It is used for improving the efficacy of an iterative method whose convergence is resilient to certain kinds of perturbations. Such perturbations are designed to "force" the perturbed algorithm to produce more useful results for the intended application than the ones that are produced by the original iterative algorithm. The perturbed algorithm is called the superiorized version of the original unperturbed algorithm. If the original algorithm is computationally efficient and useful in terms of the target application and if the perturbations are inexpensive to calculate, the method may be used to steer iterates without additional computation cost.

Areas of application

The superiorization methodology is very general and has been used successfully in many important practical applications, such as iterative reconstruction of images from their projections,G.T. Herman, Fundamentals of Computerized Tomography: Image Reconstruction from Projections, Springer-Verlag, London, UK, 2nd Edition, 2009. E.S. Helou, M.V.W. Zibetti and E.X. Miqueles, Superiorization of incremental optimization algorithms for statistical tomographic image reconstruction, Inverse Problems, Vol. 33 (2017), 044010. Q. Yang, W. Cong and G. Wang, Superiorization-based multi-energy CT image reconstruction, Inverse Problems, Vol. 33 (2017), 044014. single-photon emission computed tomography,S. Luo and T. Zhou, Superiorization of EM algorithm and its application in single-photon emission computed tomography (SPECT), Inverse Problems and Imaging, Vol. 8, pp. 223–246, (2014). radiation therapyR. Davidi, Y. Censor, R.W. Schulte, S. Geneser and L. Xing, Feasibility-seeking and superiorization algorithms applied to inverse treatment planning in radiation therapy, Contemporary Mathematics, Vol. 636, pp. 83–92, (2015). E. Bonacker, A. Gibali, K-H. Küfer and P. Süss, Speedup of lexicographic optimization by superiorization and its applications to cancer radiotherapy treatment, Inverse Problems, Vol. 33 (2017), 044012. J. Zhu and S. Penfold, Total variation superiorization in dual-energy CT reconstruction for proton therapy treatment planning, Inverse Problems, Vol. 33 (2017), 044013. and nondestructive testing,M.J. Schrapp and G.T. Herman, Data fusion in X-ray computed tomography using a superiorization approach, Review of Scientific Instruments, Vol. 85, 053701 (9pp), (2014). just to name a few. A special issue of the journal ''Inverse Problems''Superiorization: Theory and Applications, Special Issue of the journal Inverse Problems, Volume 33, Number 4, April 2017 is devoted to superiorization, both theoryH. He and H-K. Xu, Perturbation resilience and superiorization methodology of averaged mappings, Inverse Problems, Vol. 33 (2017), 044007. H-K. Xu, Bounded perturbation resilience and superiorization techniques for the projected scaled gradient method, Inverse Problems, Vol. 33 (2017), 044008. Nikazad, Touraj, and Mokhtar Abbasi. "A unified treatment of some perturbed fixed point iterative methods with an infinite pool of operators." Inverse Problems 33.4 (2017): 044002. and applications.

Objective function reduction and relation with constrained optimization

An important case of superiorization is when the original algorithm is "feasibility-seeking" (in the sense that it strives to find some point in a feasible region that is compatible with a family of constraints) and the perturbations that are introduced into the original iterative algorithm aim at reducing (not necessarily minimizing) a given merit function. In this case, superiorization has a unique place in optimization theory and practice.

Many constrained optimization methods are based on methods for unconstrained optimization that are adapted to deal with constraints. Such is, for example, the class of projected gradient methods wherein the unconstrained minimization inner step "leads" the process and a projection onto the whole constraints set (the feasible region) is performed after each minimization step in order to regain feasibility. This projection onto the constraints set is in itself a non-trivial optimization problem and the need to solve it in every iteration hinders projected gradient methods and limits their efficacy to only feasible sets that are "simple to project onto". Barrier methods or penalty methods likewise are based on unconstrained optimization combined with various "add-on"s that guarantee that the constraints are preserved. Regularization methods embed the constraints into a "regularized" objective function and proceed with unconstrained solution methods for the new regularized objective function.

In contrast to these approaches, the superiorization methodology can be viewed as an antipodal way of thinking. Instead of adapting unconstrained minimization algorithms to handling constraints, it adapts feasibility-seeking algorithms to reduce merit function values. This is done while retaining the feasibility-seeking nature of the algorithm and without paying a high computational price. Furthermore, general-purpose approaches have been developed for automatically superiorizing iterative algorithms for large classes of constraints sets and merit functions; these provide algorithms for many application tasks.

Further sources

The superiorization methodology and perturbation resilience of algorithms are reviewed in,G.T. Herman, E. Garduño, R. Davidi and Y. Censor, Superiorization: An optimization heuristic for medical physics, Medical Physics, Vol. 39, pp. 5532–5546, (2012). G.T. Herman, Superiorization for image analysis, in: Combinatorial Image Analysis, Lecture Notes in Computer Science Vol. 8466, Springer, 2014, pp. 1–7. Y. Censor, Weak and strong superiorization: Between feasibility-seeking and minimization, Analele Stiintifice ale Universitatii Ovidius Constanta-Seria Matematica, Vol. 23, pp. 41–54, (2015). see also.Y. Censor, R. Davidi, G.T. Herman, R.W. Schulte and L. Tetruashvili, Projected subgradient minimization versus superiorization, Journal of Optimization Theory and Applications, Vol. 160, pp. 730–747, (2014). Current work on superiorization can be appreciated from a continuously updated Internet page. SNARK14 is a software package for the reconstruction if 2D images from 1D projections that has a built-in capability of superiorizing any iterative algorithm for any merit function.

References

{{Reflist

Iterative methods
Mathematical optimization