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
Additional Information
- E. G. Birgin
- Affiliation: Department of Computer Science, Institute of Mathematics and Statistics, University of São Paulo, Rua do Matão, 1010, Cidade Universitária, 05508-090, São Paulo, SP, Brazil
- MR Author ID: 662583
- Email: egbirgin@ime.usp.br
- N. Krejić
- Affiliation: Department of Mathematics and Informatics, Faculty of Sciences, University of Novi Sad, Trg Dositeja Obradovića 4, 21000 Novi Sad, Serbia
- Email: natasak@uns.ac.rs
- J. M. Martínez
- Affiliation: Department of Applied Mathematics, Institute of Mathematics, Statistics, and Scientific Computing (IMECC), University of Campinas, 13083-859 Campinas SP, Brazil
- MR Author ID: 120570
- Email: martinez@ime.unicamp.br
- Received by editor(s): March 28, 2016
- Received by editor(s) in revised form: November 24, 2016
- Published electronically: September 19, 2017
- Additional Notes: This work was partially supported by the Brazilian agencies FAPESP (grants 2010/10133-0, 2013/03447-6, 2013/05475-7, 2013/07375-0, and 2014/18711-3) and CNPq (grants 309517/2014-1 and 303750/2014-6) and by the Serbian Ministry of Education, Science, and Technological Development (grant 174030)
- © Copyright 2017 American Mathematical Society
- Journal: Math. Comp. 87 (2018), 1307-1326
- MSC (2010): Primary 65K05, 65K10, 90C30, 90C90
- DOI: https://doi.org/10.1090/mcom/3246
- MathSciNet review: 3766389