Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Derivative-free superiorization: principle and algorithm

  • Original Paper
  • Published:
Numerical Algorithms Aims and scope Submit manuscript

Abstract

The superiorization methodology is intended to work with input data of constrained minimization problems, that is, a target function and a set of constraints. However, it is based on an antipodal way of thinking to what leads to constrained minimization methods. Instead of adapting unconstrained minimization algorithms to handling constraints, it adapts feasibility-seeking algorithms to reduce (not necessarily minimize) target function values. This is done by inserting target-function-reducing perturbations into a feasibility-seeking algorithm while retaining its feasibility-seeking ability and without paying a high computational price. A superiorized algorithm that employs component-wise target function reduction steps is presented. This enables derivative-free superiorization (DFS), meaning that superiorization can be applied to target functions that have no calculable partial derivatives or subgradients. The numerical behavior of our derivative-free superiorization algorithm is illustrated on a data set generated by simulating a problem of image reconstruction from projections. We present a tool (we call it a proximity-target curve) for deciding which of two iterative methods is “better” for solving a particular problem. The plots of proximity-target curves of our experiments demonstrate the advantage of the proposed derivative-free superiorization algorithm.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

Notes

  1. The approach followed in the present paper was termed strong superiorization in [13, Section 6] and [7] to distinguish it from weak superiorization, wherein asymptotic convergence to a point in C is studied instead of ε-compatibility.

  2. The term projection has in this field a different meaning than in convex analysis. It stands for a set of estimated line integrals through the image that has to be reconstructed (see [25, p. 3]).

References

  1. Audet, C., Dennis, Jr., J.E.: A progressive barrier for derivative-free nonlinear programming. SIAM J. Optim. 20, 445–472 (2009)

  2. Audet, C., Hare, W.: Derivative-Free and Blackbox Optimization. Springer International Publishing, Cham (2017)

  3. Bargetz, C., Reich, S., Zalas, R.: Convergence properties of dynamic string-averaging projection methods in the presence of perturbations. Numer. Algorithm. 77, 185–209 (2018)

  4. Butnariu, D., Reich, S., Zaslavski, A. J.: Convergence to fixed points of inexact orbits of Bregman-monotone and of nonexpansive operators in Banach spaces. In: Proceedings of Fixed Point Theory and its Applications, Mexico, pp. 11–32 (2006)

  5. Cegielski, A.: Iterative Methods for Fixed Point Problems in Hilbert Spaces. Springer, Berlin (2012)

  6. Cegielski, A., Al-Musallam, F.: Superiorization with level control. Inverse Probl. 33, 044009 (2017)

  7. Censor, Y.: Weak and strong superiorization: Between feasibility-seeking and minimization. Anal. Stiint. Univ. Ovid. Const.-Ser. Mat. 23, 41–54 (2015)

  8. Censor, Y.: Superiorization and Perturbation Resilience of Algorithms: A Bibliography compiled and continuously updated http://math.haifa.ac.il/yair/bib-superiorization-censor.html, last updated: October 27, 2020 (2020)

  9. Censor, Y., Cegielski, A.: Projection methods: An annotated bibliography of books and reviews. Optimization 64, 2343–2358 (2015)

  10. Censor, Y., Heaton, H., Schulte, R.W.: Derivative-free superiorization with component-wise perturbations. Numer. Algorithm. 80, 1219–1240 (2019)

  11. Censor, Y., Herman, G.T., Jiang, M. (eds.): Special issue on Superiorization: Theory and Applications. Inverse Problem. 33, 040301–044014 (2017)

  12. Censor, Y., Levy, E.: An analysis of the superiorization method via the principle of concentration of measure. Applied Mathematics and Optimization. https://doi.org/10.1007/s00245-019-09628-4 (2019)

  13. Censor, Y., Zaslavski, A.: Strict Fejér monotonicity by superiorization of feasibility-seeking projection methods. J. Optim. Theory Appl. 165, 172–187 (2015)

  14. Conn, A.R., Scheinberg, K., Vicente, L.N.: Introduction to Derivative-Free Optimization. Society for Industrial and Applied Mathematics (SIAM) (2009)

  15. Cooley, T.A., Barrett, H.H.: Evaluation of statistical methods for image reconstruction through ROC analysis. IEEE Trans. Med. Imaging 11, 276–282 (1992)

  16. Davidi, R., Garduño, E., Herman, G.T., Langthaler, O., Rowland, S.W., Sardana, S., Ye, Z.: SNARK14: A programming system for the reconstruction of 2D images from 1D projections, available from http://turing.iimas.unam.mx/SNARK14M/SNARK14.pdf (2019)

  17. Diniz-Ehrhardt, M., Martínez, J., Pedroso, L.: Derivative-free methods for nonlinear programming with general lower-level constraints. Comput. Appl. Math. 30, 19–52 (2011)

  18. Echeverría Ciaurri, D., Isebor, O., Durlofsky, L.: Application of derivative-free methodologies to generally constrained oil production optimization problems. Procedia Comput. Sci. 1, 1301–1310 (2012)

  19. Engl, H.W., Hanke, M., Neubauer, A.: Regularization of Inverse Problems. Kluwer Academic Publishers (2000)

  20. Fletcher, R., Leyffer, S.: Nonlinear programming without a penalty function. Math. Programm. Ser. A 91, 239–269 (2002)

  21. Garduño, E., Herman, G.T.: Superiorization of the ML-EM algorithm. IEEE Trans. Nuclear Sci. 61, 162–172 (2014)

  22. Garduño, E., Herman, G.T.: Computerized tomography with total variation and with shearlets. Inverse Probl. 33, 044011 (2017)

  23. Gay, H.A., Niemierko, A.: A free program for calculating EUD-based NTCP and TCP in external beam radiotherapy. Physica Med. 23, 115–25 (2007)

  24. He, H., Xu, H.K.: Perturbation resilience and superiorization methodology of averaged mappings. Inverse Probl. 33, 044007 (2017)

  25. Herman, G.T.: Fundamentals of Computerized Tomography: Image Reconstruction from Projections, 2nd ed.. Springer, Berlin (2009)

  26. Herman, G.T.: Iterative reconstruction techniques and their superiorization for the inversion of the Radon transform. In: Ramlau, R., Scherzer, O. (eds.) The Radon Transform: The First 100 Years and Beyond, pp 217–238. De Gruyter (2019)

  27. Herman, G.T.: Problem structures in the theory and practice of superiorization. J. Appl. Numer. Optim. 2, 71–76 (2020)

  28. Herman, G.T., Garduño, E., Davidi, R., Censor, Y.: Superiorization: An optimization heuristic for medical physics. Med. Phys. 39, 5532–5546 (2012)

  29. Hoseini, M., Saeidi, S., Kim, D.S.: On perturbed hybrid steepest descent method with minimization or superiorization for subdifferentiable functions. Numer. Algorithm. 85, 353–374 (2020)

    Article  MathSciNet  Google Scholar 

  30. Kaczmarz, S.: Angenäherte Auflösung von Systemen linearer Gleichungen. Bullet. l’Acad. Polon. Sci. Lett. A35, 355–357 (1937)

  31. Kolda, T., Lewis, R., Torczon, V.: Optimization by direct search: New perspectives on some classical and modern methods. SIAM Rev. 45, 385–482 (2003)

  32. Li, L., Chen, Y., Liu, Q., Lazic, J., Luo, W., Li, Y.: Benchmarking and evaluating MATLAB derivative-free optimisers for single-objective applications. In: Huang, D.S., Jo, K.H., Figueroa-García, J. (eds.) Intelligent Computing Theories and Application. ICIC 2017, pp 75–88. Springer (2017)

  33. Luo, S., Zhang, Y., Zhou, T., Song, J.: Superiorized iteration based on proximal point method and its application to XCT image reconstruction. ArXiv e-prints, arXiv:1608.03931 (2016)

  34. Luo, S., Zhang, Y., Zhou, T., Song, J., Wang, Y.: XCT image reconstruction by a modified superiorized iteration and theoretical analysis. Optimization Methods and Software, https://doi.org/10.1080/10556788.2018.1560442 (2019)

  35. Metz, C.E.: Some practical issues of experimental design and data analysis in radiological ROC studies. Invest. Radiol. 24, 234–243

  36. Nikazad, T., Davidi, R., Herman, G.T.: Accelerated perturbation resilient block-iterative projection methods with application to image reconstruction. Inverse Probl. 28, 035005 (2012)

  37. Nystrom, H., Jensen, M.F., Nystrom, P.W.: Treatment planning for proton therapy: what is needed in the next 10 years? Brit. J. Radiol. 93(1107), 20190304. https://doi.org/10.1259/bjr.20190304 (2020)

  38. Reich, S., Zalas, R.: A modular string averaging procedure for solving the common fixed point problem for quasi-nonexpansive mappings in Hilbert space. Numer. Algorithm. 72, 297–323 (2016)

  39. Reich, S., Zaslavski, A.J.: Convergence to approximate solutions and perturbation resilience of iterative algorithms. Inverse Problem. 33, 044005 (2017)

  40. Rios, L.M., Sahinidis, N.V.: Derivative-free optimization: A review of algorithms and comparison of software implementations. J. Glob. Optim. 56, 1247–1293 (2013)

  41. Swets, J.A.: ROC analysis applied to the evaluation of medical imaging techniques. Invest. Radiol. 14, 109–112 (1979)

  42. Zaslavski, A.J.: Algorithms for Solving Common Fixed Point Problems. Springer International Publishing (2018)

Download references

Acknowledgments

We thank Nikolaos Sahinidis and Katya Scheinberg for several informative mail exchanges that helped us see better the general picture. We are grateful to Sébastien Le Digabel for calling our attention to the work of Charles Audet and coworkers, particularly the Audet and Dennis paper [1] and the book of Audet and Hare [2]. We greatly appreciate the constructive referee report that helped us improve the paper.

Funding

Edgar Garduño received support from DGAPA-UNAM. The work of Yair Censor is supported by the ISF-NSFC joint research program Grant No. 2874/19. Elias S. Helou was partially supported by CNPq grant no. 310893/2019-4.

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Haifa, Mt. Carmel, Haifa, 3498838, Israel

    Yair Censor

  2. Departamento de Ciencias de la Computación, Instituto de Investigaciones en Matemáticas Aplicadas y en Sistemas, Universidad Nacional Autónoma de México, Cd. Universitaria, 04510, Mexico City, Mexico

    Edgar Garduño

  3. Instituto de Ciências Matemáticas e de Computação, Universidade de São Paulo, São Carlos, São Paulo, 13566-590, Brazil

    Elias S. Helou

  4. Computer Science Ph.D. Program, The Graduate Center, City University of New York, New York, NY, 10016, USA

    Gabor T. Herman

Authors
  1. Yair Censor
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Edgar Garduño
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Elias S. Helou
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Gabor T. Herman
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yair Censor.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Additional information

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Censor, Y., Garduño, E., Helou, E.S. et al. Derivative-free superiorization: principle and algorithm. Numer Algor 88, 227–248 (2021). https://doi.org/10.1007/s11075-020-01038-w

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11075-020-01038-w

Keywords

Mathematics Subject Classification (2010)

Search

Navigation