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

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 far from the solution. 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, On the employment of Inexact Restoration for the minimization of functions whose evaluation is subject to errors, Mathematics of Computation 87, pp. 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.