Inexact restoration for minimization with inexact evaluation both of the objective function and the constraints. (English) Zbl 1522.90195
Summary: In a recent paper an Inexact Restoration method for solving continuous constrained optimization problems was analyzed from the point of view of worst-case functional complexity and convergence. On the other hand, the Inexact Restoration methodology was employed, in a different research, to handle minimization problems with inexact evaluation and simple constraints. These two methodologies are combined in the present report, for constrained minimization problems in which both the objective function and the constraints, as well as their derivatives, are subject to evaluation errors. Together with a complete description of the method, complexity and convergence results will be proved.
MSC:
| 90C30 | Nonlinear programming |
| 65K05 | Numerical mathematical programming methods |
| 49M37 | Numerical methods based on nonlinear programming |
| 90C60 | Abstract computational complexity for mathematical programming problems |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Andreani, R., An inexact-restoration method for nonlinear bilevel programming problems, Comput. Optim. Appl., 307-328 (2009) · Zbl 1170.90484 · doi:10.1007/s10589-007-9147-4 |
| [2] | Andreani, Roberto, On sequential optimality conditions for smooth constrained optimization, Optimization, 627-641 (2011) · Zbl 1225.90123 · doi:10.1080/02331930903578700 |
| [3] | Andreani, Roberto, Strict constraint qualifications and sequential optimality conditions for constrained optimization, Math. Oper. Res., 693-717 (2018) · Zbl 1516.90091 · doi:10.1287/moor.2017.0879 |
| [4] | Aroux\'{e}t, Ma. Bel\'{e}n, Inexact restoration method for nonlinear optimization without derivatives, J. Comput. Appl. Math., 26-43 (2015) · Zbl 1321.65093 · doi:10.1016/j.cam.2015.04.047 |
| [5] | M. T. Ayvaz, A linked simulation-optimization model for simultaneously estimating the Manning’s surface roughness values and their parameter structures in shallow water flows, J. Hydrol. 500 (2013), 183-199. |
| [6] | Banihashemi, Nahid, Inexact restoration for Euler discretization of box-constrained optimal control problems, J. Optim. Theory Appl., 726-760 (2013) · Zbl 1263.49029 · doi:10.1007/s10957-012-0140-4 |
| [7] | Banihashemi, Nahid, Inexact restoration and adaptive mesh refinement for optimal control, J. Ind. Manag. Optim., 521-542 (2014) · Zbl 1277.49038 · doi:10.3934/jimo.2014.10.521 |
| [8] | Bellavia, Stefania, Adaptive regularization algorithms with inexact evaluations for nonconvex optimization, SIAM J. Optim., 2881-2915 (2019) · Zbl 1427.90228 · doi:10.1137/18M1226282 |
| [9] | S. Bellavia, G. Gurioli, B. Morini, and Ph.L. Toint, High-order Evaluation Complexity of a Stochastic Adaptive Regularization Algorithm for Nonconvex Optimization Using Inexact Function Evaluations and Randomly Perturbed Derivatives, Preprint, 2005.04639, 2020. · Zbl 1481.90287 |
| [10] | Bellavia, Stefania, Inexact restoration with subsampled trust-region methods for finite-sum minimization, Comput. Optim. Appl., 701-736 (2020) · Zbl 1445.90102 · doi:10.1007/s10589-020-00196-w |
| [11] | Bellavia, Stefania, A stochastic first-order trust-region method with inexact restoration for finite-sum minimization, Comput. Optim. Appl., 53-84 (2023) · Zbl 1510.90257 · doi:10.1007/s10589-022-00430-7 |
| [12] | Berahas, Albert S., Sequential quadratic optimization for nonlinear equality constrained stochastic optimization, SIAM J. Optim., 1352-1379 (2021) · Zbl 1469.90134 · doi:10.1137/20M1354556 |
| [13] | Birgin, E. G., Assessing the reliability of general-purpose inexact restoration methods, J. Comput. Appl. Math., 1-16 (2015) · Zbl 1310.90088 · doi:10.1016/j.cam.2014.12.031 |
| [14] | Birgin, E. G., On the employment of inexact restoration for the minimization of functions whose evaluation is subject to errors, Math. Comp., 1307-1326 (2018) · Zbl 1383.65060 · doi:10.1090/mcom/3246 |
| [15] | Birgin, E. G., Iteration and evaluation complexity for the minimization of functions whose computation is intrinsically inexact, Math. Comp., 253-278 (2020) · Zbl 1461.65130 · doi:10.1090/mcom/3445 |
| [16] | Birgin, E. G., Inexact restoration for derivative-free expensive function minimization and applications, J. Comput. Appl. Math., Paper No. 114193, 15 pp. (2022) · Zbl 1494.65038 · doi:10.1016/j.cam.2022.114193 |
| [17] | Birgin, Ernesto G., Constrained optimization with integer and continuous variables using inexact restoration and projected gradients, Bull. Comput. Appl. Math., 55-70 (2016) · Zbl 1392.90104 |
| [18] | Birgin, E. G., Local convergence of an inexact-restoration method and numerical experiments, J. Optim. Theory Appl., 229-247 (2005) · Zbl 1116.90094 · doi:10.1007/s10957-005-6537-6 |
| [19] | Bueno, L. F., Inexact restoration method for derivative-free optimization with smooth constraints, SIAM J. Optim., 1189-1213 (2013) · Zbl 1280.65050 · doi:10.1137/110856253 |
| [20] | Bueno, L. F., A flexible inexact-restoration method for constrained optimization, J. Optim. Theory Appl., 188-208 (2015) · Zbl 1322.90093 · doi:10.1007/s10957-014-0572-0 |
| [21] | Bueno, L. F., An inexact restoration approach to optimization problems with multiobjective constraints under weighted-sum scalarization, Optim. Lett., 1315-1325 (2016) · Zbl 1353.90143 · doi:10.1007/s11590-015-0928-x |
| [22] | Bueno, Lu\'{\i }s Felipe, On the complexity of an inexact restoration method for constrained optimization, SIAM J. Optim., 80-101 (2020) · Zbl 1453.90162 · doi:10.1137/18M1216146 |
| [23] | F. E. Curtis, M. J. O’Neill, and D. P. Robinson, Worst-case complexity of an SQP method for nonlinear equality constrained optimization, COR@L Technical Report 21T-015, Lehigh University, January 6, 2022. |
| [24] | F. E. Curtis, D. P. Robinson, and B. Zhou, Inexact sequential quadratic optimization for minimizing a stochastic objective function subject to deterministic nonlinear equality constraints, COR@L Technical Report 22T-01, Lehigh University, July 9, 2021. |
| [25] | Echebest, N., An inexact restoration derivative-free filter method for nonlinear programming, Comput. Appl. Math., 693-718 (2017) · Zbl 1359.65092 · doi:10.1007/s40314-015-0253-0 |
| [26] | Ferreira, P. S., Global convergence of a derivative-free inexact restoration filter algorithm for nonlinear programming, Optimization, 271-292 (2017) · Zbl 1365.90237 · doi:10.1080/02331934.2016.1263629 |
| [27] | Fischer, Andreas, A new line search inexact restoration approach for nonlinear programming, Comput. Optim. Appl., 333-346 (2010) · Zbl 1220.90122 · doi:10.1007/s10589-009-9267-0 |
| [28] | Francisco, Juliano B., Non-monotone inexact restoration method for nonlinear programming, Comput. Optim. Appl., 867-888 (2020) · Zbl 1446.90148 · doi:10.1007/s10589-019-00129-2 |
| [29] | Francisco, Juliano B., Nonmonotone inexact restoration approach for minimization with orthogonality constraints, Numer. Algorithms, 1651-1684 (2021) · Zbl 1471.65050 · doi:10.1007/s11075-020-00948-z |
| [30] | Francisco, Juliano B., Inexact restoration method for minimization problems arising in electronic structure calculations, Comput. Optim. Appl., 555-590 (2011) · Zbl 1263.90090 · doi:10.1007/s10589-010-9318-6 |
| [31] | Gomes-Ruggiero, M. A., Spectral projected gradient method with inexact restoration for minimization with nonconvex constraints, SIAM J. Sci. Comput., 1628-1652 (2009) · Zbl 1220.90123 · doi:10.1137/070707828 |
| [32] | Gonzaga, Cl\'{o}vis C., A globally convergent filter method for nonlinear programming, SIAM J. Optim., 646-669 (2003) · Zbl 1079.90129 · doi:10.1137/S1052623401399320 |
| [33] | Gratton, Serge, Minimizing convex quadratics with variable precision conjugate gradients, Numer. Linear Algebra Appl., Paper No. e2337, 20 pp. (2021) · Zbl 07332751 · doi:10.1002/nla.2337 |
| [34] | Gratton, S., An algorithm for the minimization of nonsmooth nonconvex functions using inexact evaluations and its worst-case complexity, Math. Program., 1-24 (2021) · Zbl 1465.90071 · doi:10.1007/s10107-020-01466-5 |
| [35] | Gratton, S., A note on solving nonlinear optimization problems in variable precision, Comput. Optim. Appl., 917-933 (2020) · Zbl 1446.90149 · doi:10.1007/s10589-020-00190-2 |
| [36] | Karas, Elizabeth W., Numerical comparison of merit function with filter criterion in inexact restoration algorithms using hard-spheres problems, Comput. Optim. Appl., 427-441 (2009) · Zbl 1181.90245 · doi:10.1007/s10589-007-9162-5 |
| [37] | Kaya, C. Yal\c{c}in, Inexact restoration for Runge-Kutta discretization of optimal control problems, SIAM J. Numer. Anal., 1492-1517 (2010) · Zbl 1230.49029 · doi:10.1137/090766668 |
| [38] | Kaya, C. Y., Euler discretization and inexact restoration for optimal control, J. Optim. Theory Appl., 191-206 (2007) · Zbl 1135.49019 · doi:10.1007/s10957-007-9217-x |
| [39] | Kouri, D. P., Inexact objective function evaluations in a trust-region algorithm for PDE-constrained optimization under uncertainty, SIAM J. Sci. Comput., A3011-A3029 (2014) · Zbl 1312.49033 · doi:10.1137/140955665 |
| [40] | Kreji\'{c}, Nata\v{s}a, Inexact restoration approach for minimization with inexact evaluation of the objective function, Math. Comp., 1775-1791 (2016) · Zbl 1335.65053 · doi:10.1090/mcom/3025 |
| [41] | LeVeque, Randall J., Finite Difference Methods for Ordinary and Partial Differential Equations, xvi+341 pp. (2007), Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA · Zbl 1127.65080 · doi:10.1137/1.9780898717839 |
| [42] | Martinez, J. M., Inexact-restoration method with Lagrangian tangent decrease and new merit function for nonlinear programming, J. Optim. Theory Appl., 39-58 (2001) · Zbl 1052.90089 · doi:10.1023/A:1017567113614 |
| [43] | Mart\'{\i }nez, J. M., Inexact-restoration algorithm for constrained optimization, J. Optim. Theory Appl., 135-163 (2000) · Zbl 0969.90094 · doi:10.1023/A:1004632923654 |
| [44] | Mart\'{\i }nez, Jos\'{e} Mario, Optimization and Control With Applications. Inexact restoration methods for nonlinear programming: advances and perspectives, Appl. Optim., 271-291 (2005), Springer, New York · Zbl 1118.90319 · doi:10.1007/0-387-24255-4\_12 |
| [45] | Miele, A., Sequential gradient-restoration algorithm for the minimization of constrained functions-ordinary and conjugate gradient versions, J. Optim. Theory Appl., 213-243 (1969) · Zbl 0174.14403 · doi:10.1007/BF00927947 |
| [46] | J. L. Picanco, J. M. Mart\'nez, C. Pfeiffer, and J. F. Meyer (eds.), Conflitos, Riscos e Impactos Associados a Barragens, CRIAB Publication, Institute of Advanced Studies of University of Campinas, 2023. |
| [47] | Rosen, J. B., The gradient projection method for nonlinear programming. II. Nonlinear constraints, J. Soc. Indust. Appl. Math., 514-532 (1961) · Zbl 0231.90048 |
| [48] | A. J. C. Saint-Venant, Th\'eorie du mouvement non-permanent des eaux, avec application aux crues des rivi\`ere at \`a l’introduction des mar\'ees dans leur lit, C. R. S\'eances Acad. Sci. 73 (1871), 147-154. · JFM 03.0482.04 |
| [49] | Shi, Hao-Jun Michael, Adaptive finite-difference interval estimation for noisy derivative-free optimization, SIAM J. Sci. Comput., A2302-A2321 (2022) · Zbl 1492.90198 · doi:10.1137/21M1452470 |
| [50] | Silva, C\^andida Elisa P., A filter inexact-restoration method for nonlinear programming, TOP, 126-146 (2008) · Zbl 1170.90493 · doi:10.1007/s11750-008-0038-3 |
| [51] | Walpen, Jorgelina, The demand adjustment problem via inexact restoration method, Comput. Appl. Math., Paper No. 204, 19 pp. (2020) · Zbl 1463.90042 · doi:10.1007/s40314-020-01189-5 |
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.
