Derivative-free superiorization: principle and algorithm. (English) Zbl 1494.65040
Summary: 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.
MSC:
| 65K05 | Numerical mathematical programming methods |
| 90C56 | Derivative-free methods and methods using generalized derivatives |
Keywords:
derivative-free method; superiorization; constrained minimization; component-wise perturbations; proximity function; bounded perturbations; regularizationSoftware:
MultiMinReferences:
| [1] | Audet, C., Dennis, Jr., J.E.: A progressive barrier for derivative-free nonlinear programming. SIAM J. Optim. 20, 445-472 (2009) · Zbl 1187.90266 |
| [2] | Audet, C., Hare, W.: Derivative-Free and Blackbox Optimization. Springer International Publishing, Cham (2017) · Zbl 1391.90001 |
| [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) · Zbl 1459.47023 |
| [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) · Zbl 1116.47052 |
| [5] | Cegielski, A.: Iterative Methods for Fixed Point Problems in Hilbert Spaces. Springer, Berlin (2012) · Zbl 1256.47043 |
| [6] | Cegielski, A., Al-Musallam, F.: Superiorization with level control. Inverse Probl. 33, 044009 (2017) · Zbl 1366.65060 |
| [7] | Censor, Y.: Weak and strong superiorization: Between feasibility-seeking and minimization. Anal. Stiint. Univ. Ovid. Const.-Ser. Mat. 23, 41-54 (2015) · Zbl 1349.90675 |
| [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) · Zbl 1328.65001 |
| [10] | Censor, Y., Heaton, H., Schulte, R.W.: Derivative-free superiorization with component-wise perturbations. Numer. Algorithm. 80, 1219-1240 (2019) · Zbl 07042047 |
| [11] | Censor, Y., Herman, G.T., Jiang, M. (eds.): Special issue on Superiorization: Theory and Applications. Inverse Problem. 33, 040301-044014 (2017) · Zbl 1365.00030 |
| [12] | Censor, Y., Levy, E.: An analysis of the superiorization method via the principle of concentration of measure. Applied Mathematics and Optimization. doi:10.1007/s00245-019-09628-4 (2019) · Zbl 07371841 |
| [13] | Censor, Y., Zaslavski, A.: Strict Fejér monotonicity by superiorization of feasibility-seeking projection methods. J. Optim. Theory Appl. 165, 172-187 (2015) · Zbl 1322.90063 |
| [14] | Conn, A.R., Scheinberg, K., Vicente, L.N.: Introduction to Derivative-Free Optimization. Society for Industrial and Applied Mathematics (SIAM) (2009) · Zbl 1163.49001 |
| [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) · Zbl 1222.90060 |
| [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) · Zbl 0859.65054 |
| [20] | Fletcher, R., Leyffer, S.: Nonlinear programming without a penalty function. Math. Programm. Ser. A 91, 239-269 (2002) · Zbl 1049.90088 |
| [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) · Zbl 1367.92060 |
| [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) · Zbl 1366.65061 |
| [25] | Herman, G.T.: Fundamentals of Computerized Tomography: Image Reconstruction from Projections, 2nd ed.. Springer, Berlin (2009) · Zbl 1280.92002 |
| [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) · Zbl 1459.44002 |
| [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, DS, On perturbed hybrid steepest descent method with minimization or superiorization for subdifferentiable functions, Numer. Algorithm., 85, 353-374 (2020) · Zbl 1514.47096 · doi:10.1007/s11075-019-00818-3 |
| [30] | Kaczmarz, S.: Angenäherte Auflösung von Systemen linearer Gleichungen. Bullet. l’Acad. Polon. Sci. Lett. A35, 355-357 (1937) · JFM 63.0524.02 |
| [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) · Zbl 1059.90146 |
| [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, doi:10.1080/10556788.2018.1560442 (2019) · Zbl 1466.94007 |
| [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) · Zbl 1261.94014 |
| [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. doi: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) · Zbl 1348.47065 |
| [39] | Reich, S., Zaslavski, A.J.: Convergence to approximate solutions and perturbation resilience of iterative algorithms. Inverse Problem. 33, 044005 (2017) · Zbl 1456.47030 |
| [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) · Zbl 1272.90116 |
| [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) · Zbl 1447.47012 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
