Inexact restoration for minimization with inexact evaluation both of the objective function and the constraints

Bueno, L.; Larreal, F.; Martínez, J.

doi:10.1090/mcom/3855

Inexact restoration for minimization with inexact evaluation both of the objective function and the constraints
HTML articles powered by AMS MathViewer

by L. F. Bueno, F. Larreal and J. M. Martínez

Math. Comp. 93 (2024), 293-326

DOI: https://doi.org/10.1090/mcom/3855

Published electronically: May 11, 2023

HTML | PDF | Request permission

Abstract:

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.

References

R. Andreani, S. L. C. Castro, J. L. Chela, A. Friedlander, and S. A. Santos, An inexact-restoration method for nonlinear bilevel programming problems, Comput. Optim. Appl. 43 (2009), no. 3, 307–328. MR 2511917, DOI 10.1007/s10589-007-9147-4
Roberto Andreani, Gabriel Haeser, and J. M. Martínez, On sequential optimality conditions for smooth constrained optimization, Optimization 60 (2011), no. 5, 627–641. MR 2801388, DOI 10.1080/02331930903578700
Roberto Andreani, José Mario Martínez, Alberto Ramos, and Paulo J. S. Silva, Strict constraint qualifications and sequential optimality conditions for constrained optimization, Math. Oper. Res. 43 (2018), no. 3, 693–717. MR 3846067, DOI 10.1287/moor.2017.0879
Ma. Belén Arouxét, Nélida E. Echebest, and Elvio A. Pilotta, Inexact restoration method for nonlinear optimization without derivatives, J. Comput. Appl. Math. 290 (2015), 26–43. MR 3370390, DOI 10.1016/j.cam.2015.04.047
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.
Nahid Banihashemi and C. Yalçın Kaya, Inexact restoration for Euler discretization of box-constrained optimal control problems, J. Optim. Theory Appl. 156 (2013), no. 3, 726–760. MR 3022307, DOI 10.1007/s10957-012-0140-4
Nahid Banihashemi and C. Yalçin Kaya, Inexact restoration and adaptive mesh refinement for optimal control, J. Ind. Manag. Optim. 10 (2014), no. 2, 521–542. MR 3124702, DOI 10.3934/jimo.2014.10.521
Stefania Bellavia, Gianmarco Gurioli, Benedetta Morini, and Philippe L. Toint, Adaptive regularization algorithms with inexact evaluations for nonconvex optimization, SIAM J. Optim. 29 (2019), no. 4, 2881–2915. MR 4031478, DOI 10.1137/18M1226282
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, arXiv:2005.04639, 2020.
Stefania Bellavia, Nataša Krejić, and Benedetta Morini, Inexact restoration with subsampled trust-region methods for finite-sum minimization, Comput. Optim. Appl. 76 (2020), no. 3, 701–736. MR 4115581, DOI 10.1007/s10589-020-00196-w
Stefania Bellavia, Nataša Krejić, Benedetta Morini, and Simone Rebegoldi, A stochastic first-order trust-region method with inexact restoration for finite-sum minimization, Comput. Optim. Appl. 84 (2023), no. 1, 53–84. MR 4530286, DOI 10.1007/s10589-022-00430-7
Albert S. Berahas, Frank E. Curtis, Daniel Robinson, and Baoyu Zhou, Sequential quadratic optimization for nonlinear equality constrained stochastic optimization, SIAM J. Optim. 31 (2021), no. 2, 1352–1379. MR 4259203, DOI 10.1137/20M1354556
E. G. Birgin, L. F. Bueno, and J. M. Martínez, Assessing the reliability of general-purpose inexact restoration methods, J. Comput. Appl. Math. 282 (2015), 1–16. MR 3313085, DOI 10.1016/j.cam.2014.12.031
E. G. Birgin, N. Krejić, and J. M. Martínez, On the employment of inexact restoration for the minimization of functions whose evaluation is subject to errors, Math. Comp. 87 (2018), no. 311, 1307–1326. MR 3766389, DOI 10.1090/mcom/3246
E. G. Birgin, N. Krejić, and J. M. Martínez, Iteration and evaluation complexity for the minimization of functions whose computation is intrinsically inexact, Math. Comp. 89 (2020), no. 321, 253–278. MR 4011542, DOI 10.1090/mcom/3445
E. G. Birgin, N. Krejić, and J. M. Martínez, Inexact restoration for derivative-free expensive function minimization and applications, J. Comput. Appl. Math. 410 (2022), Paper No. 114193, 15. MR 4396565, DOI 10.1016/j.cam.2022.114193
Ernesto G. Birgin, Rafael D. Lobato, and José Mario Martínez, Constrained optimization with integer and continuous variables using inexact restoration and projected gradients, Bull. Comput. Appl. Math. 4 (2016), no. 2, 55–70. MR 3601877
E. G. Birgin and J. M. Martínez, Local convergence of an inexact-restoration method and numerical experiments, J. Optim. Theory Appl. 127 (2005), no. 2, 229–247. MR 2186122, DOI 10.1007/s10957-005-6537-6
L. F. Bueno, A. Friedlander, J. M. Martínez, and F. N. C. Sobral, Inexact restoration method for derivative-free optimization with smooth constraints, SIAM J. Optim. 23 (2013), no. 2, 1189–1213. MR 3069098, DOI 10.1137/110856253
L. F. Bueno, G. Haeser, and J. M. Martínez, A flexible inexact-restoration method for constrained optimization, J. Optim. Theory Appl. 165 (2015), no. 1, 188–208. MR 3327421, DOI 10.1007/s10957-014-0572-0
L. F. Bueno, G. Haeser, and J. M. Martínez, An inexact restoration approach to optimization problems with multiobjective constraints under weighted-sum scalarization, Optim. Lett. 10 (2016), no. 6, 1315–1325. MR 3529849, DOI 10.1007/s11590-015-0928-x
Luís Felipe Bueno and José Mario Martínez, On the complexity of an inexact restoration method for constrained optimization, SIAM J. Optim. 30 (2020), no. 1, 80–101. MR 4046784, DOI 10.1137/18M1216146
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.
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.
N. Echebest, M. L. Schuverdt, and R. P. Vignau, An inexact restoration derivative-free filter method for nonlinear programming, Comput. Appl. Math. 36 (2017), no. 1, 693–718. MR 3611625, DOI 10.1007/s40314-015-0253-0
P. S. Ferreira, E. W. Karas, M. Sachine, and F. N. C. Sobral, Global convergence of a derivative-free inexact restoration filter algorithm for nonlinear programming, Optimization 66 (2017), no. 2, 271–292. MR 3589633, DOI 10.1080/02331934.2016.1263629
Andreas Fischer and Ana Friedlander, A new line search inexact restoration approach for nonlinear programming, Comput. Optim. Appl. 46 (2010), no. 2, 333–346. MR 2644209, DOI 10.1007/s10589-009-9267-0
Juliano B. Francisco, Douglas S. Gonçalves, Fermín S. V. Bazán, and Lila L. T. Paredes, Non-monotone inexact restoration method for nonlinear programming, Comput. Optim. Appl. 76 (2020), no. 3, 867–888. MR 4115586, DOI 10.1007/s10589-019-00129-2
Juliano B. Francisco, Douglas S. Gonçalves, Fermín S. V. Bazán, and Lila L. T. Paredes, Nonmonotone inexact restoration approach for minimization with orthogonality constraints, Numer. Algorithms 86 (2021), no. 4, 1651–1684. MR 4229641, DOI 10.1007/s11075-020-00948-z
Juliano B. Francisco, J. M. Martínez, Leandro Martínez, and Feodor Pisnitchenko, Inexact restoration method for minimization problems arising in electronic structure calculations, Comput. Optim. Appl. 50 (2011), no. 3, 555–590. MR 2860977, DOI 10.1007/s10589-010-9318-6
M. A. Gomes-Ruggiero, J. M. Martínez, and S. A. Santos, Spectral projected gradient method with inexact restoration for minimization with nonconvex constraints, SIAM J. Sci. Comput. 31 (2009), no. 3, 1628–1652. MR 2491539, DOI 10.1137/070707828
Clóvis C. Gonzaga, Elizabeth Karas, and Márcia Vanti, A globally convergent filter method for nonlinear programming, SIAM J. Optim. 14 (2003), no. 3, 646–669. MR 2085935, DOI 10.1137/S1052623401399320
Serge Gratton, Ehouarn Simon, David Titley-Peloquin, and Philippe L. Toint, Minimizing convex quadratics with variable precision conjugate gradients, Numer. Linear Algebra Appl. 28 (2021), no. 1, Paper No. e2337, 20. MR 4184093, DOI 10.1002/nla.2337
S. Gratton, E. Simon, and Ph. L. Toint, An algorithm for the minimization of nonsmooth nonconvex functions using inexact evaluations and its worst-case complexity, Math. Program. 187 (2021), no. 1-2, Ser. A, 1–24. MR 4246296, DOI 10.1007/s10107-020-01466-5
S. Gratton and Ph. L. Toint, A note on solving nonlinear optimization problems in variable precision, Comput. Optim. Appl. 76 (2020), no. 3, 917–933. MR 4115588, DOI 10.1007/s10589-020-00190-2
Elizabeth W. Karas, Elvio A. Pilotta, and Ademir A. Ribeiro, Numerical comparison of merit function with filter criterion in inexact restoration algorithms using hard-spheres problems, Comput. Optim. Appl. 44 (2009), no. 3, 427–441. MR 2570601, DOI 10.1007/s10589-007-9162-5
C. Yalçin Kaya, Inexact restoration for Runge-Kutta discretization of optimal control problems, SIAM J. Numer. Anal. 48 (2010), no. 4, 1492–1517. MR 2684344, DOI 10.1137/090766668
C. Y. Kaya and J. M. Martínez, Euler discretization and inexact restoration for optimal control, J. Optim. Theory Appl. 134 (2007), no. 2, 191–206. MR 2332460, DOI 10.1007/s10957-007-9217-x
D. P. Kouri, M. Heinkenschloss, D. Ridzal, and B. G. van Bloemen Waanders, Inexact objective function evaluations in a trust-region algorithm for PDE-constrained optimization under uncertainty, SIAM J. Sci. Comput. 36 (2014), no. 6, A3011–A3029. MR 3293456, DOI 10.1137/140955665
Nataša Krejić and J. M. Martínez, Inexact restoration approach for minimization with inexact evaluation of the objective function, Math. Comp. 85 (2016), no. 300, 1775–1791. MR 3471107, DOI 10.1090/mcom/3025
Randall J. LeVeque, Finite difference methods for ordinary and partial differential equations, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2007. Steady-state and time-dependent problems. MR 2378550, DOI 10.1137/1.9780898717839
J. M. Martinez, Inexact-restoration method with Lagrangian tangent decrease and new merit function for nonlinear programming, J. Optim. Theory Appl. 111 (2001), no. 1, 39–58. MR 1850678, DOI 10.1023/A:1017567113614
J. M. Martínez and E. A. Pilotta, Inexact-restoration algorithm for constrained optimization, J. Optim. Theory Appl. 104 (2000), no. 1, 135–163. MR 1741394, DOI 10.1023/A:1004632923654
José Mario Martínez and Elvio A. Pilotta, Inexact restoration methods for nonlinear programming: advances and perspectives, Optimization and control with applications, Appl. Optim., vol. 96, Springer, New York, 2005, pp. 271–291. MR 2144380, DOI 10.1007/0-387-24255-4_{1}2
A. Miele, H. Y. Huang, and J. C. Heideman, Sequential gradient-restoration algorithm for the minimization of constrained functions—ordinary and conjugate gradient versions, J. Optim. Theory Appl. 4 (1969), 213–243. MR 255024, DOI 10.1007/BF00927947
J. L. Picanço, 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.
J. B. Rosen, The gradient projection method for nonlinear programming. II. Nonlinear constraints, J. Soc. Indust. Appl. Math. 9 (1961), 514–532. MR 135991, DOI 10.1137/0109044
A. J. C. Saint-Venant, Théorie du mouvement non-permanent des eaux, avec application aux crues des rivière at à l’introduction des marées dans leur lit, C. R. Séances Acad. Sci. 73 (1871), 147–154.
Hao-Jun Michael Shi, Yuchen Xie, Melody Qiming Xuan, and Jorge Nocedal, Adaptive finite-difference interval estimation for noisy derivative-free optimization, SIAM J. Sci. Comput. 44 (2022), no. 4, A2302–A2321. MR 4461581, DOI 10.1137/21M1452470
Cândida Elisa P. Silva and M. Teresa T. Monteiro, A filter inexact-restoration method for nonlinear programming, TOP 16 (2008), no. 1, 126–146. MR 2407402, DOI 10.1007/s11750-008-0038-3
Jorgelina Walpen, Pablo A. Lotito, Elina M. Mancinelli, and Lisandro Parente, The demand adjustment problem via inexact restoration method, Comput. Appl. Math. 39 (2020), no. 3, Paper No. 204, 19. MR 4121147, DOI 10.1007/s40314-020-01189-5