Iteration and evaluation complexity for the minimization of functions whose computation is intrinsically inexact

Birgin, E.; Krejić, N.; Martínez, J.

doi:10.1090/mcom/3445

Iteration and evaluation complexity for the minimization of functions whose computation is intrinsically inexact
HTML articles powered by AMS MathViewer

by E. G. Birgin, N. Krejić and J. M. Martínez HTML | PDF

Math. Comp. 89 (2020), 253-278 Request permission

Abstract:

In many cases in which one wishes to minimize a complicated or expensive function, it is convenient to employ cheap approximations, at least when the current approximation to the solution is poor. Adequate strategies for deciding the accuracy desired at each stage of optimization are crucial for the global convergence and overall efficiency of the process. A recently introduced procedure [E. G. Birgin, N. Krejić, and J. M. Martínez, Math. Comp. 87 (2018), 1307–1326, 2018] based on Inexact Restoration is revisited, modified, and analyzed from the point of view of worst-case evaluation complexity in this work.

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
A. Asimakopulos, Keynes’s General Theory and Accumulation, Cambridge University Press, 1991.
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
Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski, Robust optimization, Princeton Series in Applied Mathematics, Princeton University Press, Princeton, NJ, 2009. MR 2546839, DOI 10.1515/9781400831050
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, J. L. Gardenghi, J. M. Martínez, and S. A. Santos, On the use of third-order models with fourth-order regularization for unconstrained optimization, Optimization Letters, to appear (DOI: 10.1007/s11590-019-01395-z).
E. G. Birgin, J. L. Gardenghi, J. M. Martínez, S. A. Santos, and Ph. L. Toint, Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models, Math. Program. 163 (2017), no. 1-2, Ser. A, 359–368. MR 3632983, DOI 10.1007/s10107-016-1065-8
E. G. Birgin, J. L. Gardenghi, J. M. Martínez, S. A. Santos, and Ph. L. Toint, Evaluation complexity for nonlinear constrained optimization using unscaled KKT conditions and high-order models, SIAM J. Optim. 26 (2016), no. 2, 951–967. MR 3484405, DOI 10.1137/15M1031631
E. G. Birgin and J. M. Martínez, The use of quadratic regularization with a cubic descent condition for unconstrained optimization, SIAM J. Optim. 27 (2017), no. 2, 1049–1074. MR 3659959, DOI 10.1137/16M110280X
E. G. Birgin and J. M. Martínez, On regularization and active-set methods with complexity for constrained optimization, SIAM J. Optim. 28 (2018), no. 2, 1367–1395. MR 3799068, DOI 10.1137/17M1127107
E. G. Birgin and J. M. Martínez, A Newton-like method with mixed factorizations and cubic regularization for unconstrained minimization, Comput. Optim. Appl., to appear. DOI 10.1007/s10589-019-00089-7.
Ernesto G. Birgin, José Mario Martínez, and Marcos Raydan, Nonmonotone spectral projected gradient methods on convex sets, SIAM J. Optim. 10 (2000), no. 4, 1196–1211. MR 1777088, DOI 10.1137/S1052623497330963
E. G. Birgin, J. M. Martínez, and M. Raydan, Spectral projected gradient methods: Review and perspectives, J. Statistical Software 60 (2014), no 3. DOI 10.18637/jss.v060.i03.
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 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
C. Cartis, N. I. M. Gould, and Ph. L. Toint, On the complexity of steepest descent, Newton’s and regularized Newton’s methods for nonconvex unconstrained optimization problems, SIAM J. Optim. 20 (2010), no. 6, 2833–2852. MR 2721157, DOI 10.1137/090774100
Coralia Cartis, Nicholas I. M. Gould, and Philippe L. Toint, Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results, Math. Program. 127 (2011), no. 2, Ser. A, 245–295. MR 2776701, DOI 10.1007/s10107-009-0286-5
Coralia Cartis, Nicholas I. M. Gould, and Philippe L. Toint, Adaptive cubic regularisation methods for unconstrained optimization. Part II: worst-case function- and derivative-evaluation complexity, Math. Program. 130 (2011), no. 2, Ser. A, 295–319. MR 2855872, DOI 10.1007/s10107-009-0337-y
Coralia Cartis, Nick I. Gould, and Philippe L. Toint, Universal regularization methods: varying the power, the smoothness and the accuracy, SIAM J. Optim. 29 (2019), no. 1, 595–615. MR 3919410, DOI 10.1137/16M1106316
B. H. Cervelin, D. Conti, M. A. Diniz-Ehrhardt, and J. M. Martínez, A computer model for particle-like simulation in broiler houses, Computers and Electronics in Agriculture 141 (2017), 1–14. DOI 10.1016/j.compag.2017.07.002.
Frank E. Curtis, Daniel P. Robinson, and Mohammadreza Samadi, A trust region algorithm with a worst-case iteration complexity of $\mathcal {O}(\epsilon ^{-3/2})$ for nonconvex optimization, Math. Program. 162 (2017), no. 1-2, Ser. A, 1–32. MR 3612930, DOI 10.1007/s10107-016-1026-2
Stephan Dempe, Foundations of bilevel programming, Nonconvex Optimization and its Applications, vol. 61, Kluwer Academic Publishers, Dordrecht, 2002. MR 1921449
Jean-Pierre Dussault, $\textrm {ARC_q}$: a new adaptive regularization by cubics, Optim. Methods Softw. 33 (2018), no. 2, 322–335. MR 3750605, DOI 10.1080/10556788.2017.1322080
Y. Ermoliev, Stochastic Programming Methods, Academy of Sciences of the USSR, Kiev, 1967.
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
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
G. N. Grapiglia and Yu. Nesterov, Globally convergent second-order schemes for minimizing twice differentiable functions, CORE Discussion Paper 2016/28, Université Catholique de Louvain, Louvain, Belgium, 2016.
Geovani N. Grapiglia, Jinyun Yuan, and Ya-xiang Yuan, On the convergence and worst-case complexity of trust-region and regularization methods for unconstrained optimization, Math. Program. 152 (2015), no. 1-2, Ser. A, 491–520. MR 3369490, DOI 10.1007/s10107-014-0794-9
A. Griewank, The modification of Newton’s method for unconstrained optimization by bounding cubic terms, Technical Report NA/12, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, 1981.
A. O. Herrera, H. D. Scolnik, G. Chichilnisky, G. C. Gallopin, J. E. Hardoy, Catastrophe or New Society? A Latin America World Model, IDRC, Ottawa, ON, CA, 1976.
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
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
Zhi-Quan Luo, Jong-Shi Pang, and Daniel Ralph, Mathematical programs with equilibrium constraints, Cambridge University Press, Cambridge, 1996. MR 1419501, DOI 10.1017/CBO9780511983658
José Mario Martínez, Local minimizers of quadratic functions on Euclidean balls and spheres, SIAM J. Optim. 4 (1994), no. 1, 159–176. MR 1260413, DOI 10.1137/0804009
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
José Mario Martínez, On high-order model regularization for constrained optimization, SIAM J. Optim. 27 (2017), no. 4, 2447–2458. MR 3735301, DOI 10.1137/17M1115472
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
J. M. Martínez and M. Raydan, Cubic-regularization counterpart of a variable-norm trust-region method for unconstrained minimization, J. Global Optim. 68 (2017), no. 2, 367–385. MR 3649544, DOI 10.1007/s10898-016-0475-8
Yurii Nesterov and B. T. Polyak, Cubic regularization of Newton method and its global performance, Math. Program. 108 (2006), no. 1, Ser. A, 177–205. MR 2229459, DOI 10.1007/s10107-006-0706-8
R. Pasupathy, On choosing parameters in retrospective-approximation algorithms for stochastic root finding and simulation optimization, Oper. Res. 58 (2010), 889–901. DOI 10.1287/opre.1090.0773.
E. Polak and J. O. Royset, Efficient sample sizes in stochastic nonlinear programming, J. Comput. Appl. Math. 217 (2008), no. 2, 301–310. MR 2428700, DOI 10.1016/j.cam.2007.02.014
J. O. Royset, Optimality functions in stochastic programming, Math. Program. 135 (2012), no. 1-2, Ser. A, 293–321. MR 2968258, DOI 10.1007/s10107-011-0453-3
Johannes O. Royset and Roberto Szechtman, Optimal budget allocation for sample average approximation, Oper. Res. 61 (2013), no. 3, 762–776. MR 3079744, DOI 10.1287/opre.2013.1163
Reuven Y. Rubinstein and Alexander Shapiro, Discrete event systems, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, John Wiley & Sons, Ltd., Chichester, 1993. Sensitivity analysis and stochastic optimization by the score function method. MR 1241645