Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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


Authors: E. G. Birgin, N. Krejić and J. M. Martínez
Journal: Math. Comp. 87 (2018), 1307-1326
MSC (2010): Primary 65K05, 65K10, 90C30, 90C90
DOI: https://doi.org/10.1090/mcom/3246
Published electronically: September 19, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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, https://doi.org/10.1007/s10589-007-9147-4
  • [2] 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, https://doi.org/10.1007/s10957-012-0140-4
  • [3] F. Bastin, Trust-region algorithms for nonlinear stochastic programming and mixed logit models, Ph.D. Thesis, University of Namur, Namur, Belgium, 2004.
  • [4] 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, https://doi.org/10.1007/s10287-005-0044-y
  • [5] 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, https://doi.org/10.1016/j.cam.2014.12.031
  • [6] 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, https://doi.org/10.1007/s10957-005-6537-6
  • [7] 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, https://doi.org/10.1007/s13675-015-0052-9
  • [8] 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.
  • [9] 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, https://doi.org/10.1137/110856253
  • [10] 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, https://doi.org/10.1002/(SICI)1099-1506(199611/12)3:6$ \langle$459::AID-NLA82$ \rangle$3.3.CO;2-J
  • [11] 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, https://doi.org/10.1007/s10589-009-9267-0
  • [12] 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, https://doi.org/10.1137/070707828
  • [13] Nicholas J. Higham, Computing a nearest symmetric positive semidefinite matrix, Linear Algebra Appl. 103 (1988), 103-118. MR 943997, https://doi.org/10.1016/0024-3795(88)90223-6
  • [14] T. Homem-de-Mello, Variable-sample methods for stochastic optimization, ACM Transactions on Modeling and Computer Simulation 13 (2003), 108-133.
  • [15] 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, https://doi.org/10.1007/s10957-007-9217-x
  • [16] 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, https://doi.org/10.1016/j.cam.2012.12.020
  • [17] 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, https://doi.org/10.1007/s11075-014-9869-1
  • [18] 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, https://doi.org/10.1090/mcom/3025
  • [19] 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, https://doi.org/10.1023/A:1017567113614
  • [20] 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, https://doi.org/10.1023/A:1004632923654
  • [21] R. Pasupathy, On choosing parameters in Retrospective Approximation algorithms for stochastic root finding and simulation optimization, Operations Research 58 (2010), 889-901.
  • [22] 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, https://doi.org/10.1007/s10589-012-9528-1
  • [23] Reuven Y. Rubinstein and Alexander Shapiro, Discrete Event Systems: Sensitivity Analysis and Stochastic Optimization by the Score Function Method, John Wiley & Sons, Ltd., Chichester, 1993. MR 1241645
  • [24] 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
  • [25] Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszczyński, Lectures on Stochastic Programming: Modeling and Theory, MPS/SIAM Series on Optimization, vol. 9, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Programming Society (MPS), Philadelphia, PA, 2009. MR 2562798

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65K05, 65K10, 90C30, 90C90

Retrieve articles in all journals with MSC (2010): 65K05, 65K10, 90C30, 90C90


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
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
Email: martinez@ime.unicamp.br

DOI: https://doi.org/10.1090/mcom/3246
Keywords: Inexact Restoration, stochastic programming, global convergence, numerical experiments
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)
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society