On the employment of inexact restoration for the minimization of functions whose evaluation is subject to errors

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

doi:10.1090/mcom/3246

On the employment of inexact restoration for the minimization of functions whose evaluation is subject to errors
HTML articles powered by AMS MathViewer

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

Math. Comp. 87 (2018), 1307-1326 Request permission

Abstract:

Inexact Restoration is a well established technique for continuous minimization problems with constraints. Recently, it has been used by Krejić and Martínez for optimization of functions whose evaluation is necessarily inexact and comes from an iterative process. This technique will be generalized in the present paper and it will be applied to stochastic optimization and related problems. New convergence results will be given and numerical results will be presented.

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
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
F. Bastin, Trust-region algorithms for nonlinear stochastic programming and mixed logit models, Ph.D. Thesis, University of Namur, Namur, Belgium, 2004.
Fabian Bastin, Cinzia Cirillo, and Philippe L. Toint, An adaptive Monte Carlo algorithm for computing mixed logit estimators, Comput. Manag. Sci. 3 (2006), no. 1, 55–79. MR 2196398, DOI 10.1007/s10287-005-0044-y
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 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
E. G. Birgin and J. M. Martínez, On the application of an augmented Lagrangian algorithm to some portfolio problems, EURO J. Comput. Optim. 4 (2016), no. 1, 79–92. MR 3500983, DOI 10.1007/s13675-015-0052-9
E. G. Birgin, J. M. Martínez, and M. Raydan, Spectral projected gradient methods: Review and perspectives, Journal of Statistical Software 60 (2014), no. 3 (DOI: 10.18637/jss.v060.i03). http://www.jstatsoft.org/v60/i03.
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
René Escalante and Marcos Raydan, Dykstra’s algorithm for a constrained least-squares matrix problem, Numer. Linear Algebra Appl. 3 (1996), no. 6, 459–471. MR 1419256, DOI 10.1002/(SICI)1099-1506(199611/12)3:6<459::AID-NLA82>3.3.CO;2-J
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
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
Nicholas J. Higham, Computing a nearest symmetric positive semidefinite matrix, Linear Algebra Appl. 103 (1988), 103–118. MR 943997, DOI 10.1016/0024-3795(88)90223-6
T. Homem-de-Mello, Variable-sample methods for stochastic optimization, ACM Transactions on Modeling and Computer Simulation 13 (2003), 108–133.
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 Nataša Krklec, Line search methods with variable sample size for unconstrained optimization, J. Comput. Appl. Math. 245 (2013), 213–231. MR 3016246, DOI 10.1016/j.cam.2012.12.020
Nataša Krejić and Nataša Krklec Jerinkić, Nonmonotone line search methods with variable sample size, Numer. Algorithms 68 (2015), no. 4, 711–739. MR 3325823, DOI 10.1007/s11075-014-9869-1
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
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
R. Pasupathy, On choosing parameters in Retrospective Approximation algorithms for stochastic root finding and simulation optimization, Operations Research 58 (2010), 889–901.
Johannes O. Royset, On sample size control in sample average approximations for solving smooth stochastic programs, Comput. Optim. Appl. 55 (2013), no. 2, 265–309. MR 3053787, DOI 10.1007/s10589-012-9528-1
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
A. Ruszczyński and A. Shapiro (eds.), Stochastic programming, Handbooks in Operations Research and Management Science, vol. 10, Elsevier Science B.V., Amsterdam, 2003. MR 2051791
Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszczyński, Lectures on stochastic programming, MPS/SIAM Series on Optimization, vol. 9, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Programming Society (MPS), Philadelphia, PA, 2009. Modeling and theory. MR 2562798, DOI 10.1137/1.9780898718751