Inexact Restoration approach for minimization with inexact evaluation of the objective function
HTML articles powered by AMS MathViewer
- by Nataša Krejić and J. M. Martínez PDF
- Math. Comp. 85 (2016), 1775-1791 Request permission
Abstract:
A new method is introduced for minimizing a function that can be computed only inexactly, with different levels of accuracy. The challenge is to evaluate the (potentially very expensive) objective function with low accuracy as far as this does not interfere with the goal of getting high accuracy minimization at the end. For achieving this goal the problem is reformulated in terms of constrained optimization and handled with an Inexact Restoration technique. Convergence is proved and numerical experiments motivated by Electronic Structure Calculations are presented, which indicate that the new method overcomes current approaches for solving large-scale problems.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, PhD thesis, University of 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, J. M. Martínez, L. Martínez, and G. B. Rocha, Sparse projected-gradient method as a linear-scaling low-memory alternative to diagonalization in self-consistent field electronic structure calculations, Journal of Chemical Theory and Computation 9 (2013), 1043-1051.
- 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
- Andrew R. Conn, Nicholas I. M. Gould, and Philippe L. Toint, Trust-region methods, MPS/SIAM Series on Optimization, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Programming Society (MPS), Philadelphia, PA, 2000. MR 1774899, DOI 10.1137/1.9780898719857
- 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
- Michael P. Friedlander and Mark Schmidt, Hybrid deterministic-stochastic methods for data fitting, SIAM J. Sci. Comput. 34 (2012), no. 3, A1380–A1405. MR 2970257, DOI 10.1137/110830629
- Gene H. Golub and Charles F. Van Loan, Matrix computations, 3rd ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. MR 1417720
- 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
- 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
- T. Helgaker, P. Jorgensen, and J. Olsen, Molecular Electronic-Structure Theory, John Wiley & Sons, New York, 2000, 433-502.
- T. Homem-de-Mello, Variable-sample methods for stochastic optimization, ACM Transactions on Modeling and Computer Simulation 13 (2003), 108-133.
- Elizabeth W. Karas, Clóvis C. Gonzaga, and Ademir A. Ribeiro, Local convergence of filter methods for equality constrained non-linear programming, Optimization 59 (2010), no. 8, 1153–1171. MR 2738599, DOI 10.1080/02331930903085342
- Elizabeth W. Karas, Elvio A. Pilotta, and Ademir A. Ribeiro, Numerical comparison of merit function with filter criterion in inexact restoration algorithms using hard-spheres problems, Comput. Optim. Appl. 44 (2009), no. 3, 427–441. MR 2570601, DOI 10.1007/s10589-007-9162-5
- C. Yalçin Kaya, Inexact restoration for Runge-Kutta discretization of optimal control problems, SIAM J. Numer. Anal. 48 (2010), no. 4, 1492–1517. MR 2684344, DOI 10.1137/090766668
- 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
- Claude Le Bris, Computational chemistry from the perspective of numerical analysis, Acta Numer. 14 (2005), 363–444. MR 2168346, DOI 10.1017/S096249290400025X
- 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.
- 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
- 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
- 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
- A. Shapiro and Y. Wardi, Convergence analysis of stochastic algorithms, Math. Oper. Res. 21 (1996), no. 3, 615–628. MR 1403308, DOI 10.1287/moor.21.3.615
- James C. Spall, Introduction to stochastic search and optimization, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience [John Wiley & Sons], Hoboken, NJ, 2003. Estimation, simulation, and control. MR 1968388, DOI 10.1002/0471722138
- Y. Wardi, Stochastic algorithms with Armijo stepsizes for minimization of functions, J. Optim. Theory Appl. 64 (1990), no. 2, 399–417. MR 1042003, DOI 10.1007/BF00939456
Additional Information
- Nataša 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): May 8, 2014
- Received by editor(s) in revised form: November 6, 2014, and December 8, 2014
- Published electronically: September 9, 2015
- Additional Notes: The first author’s research was supported by the Serbian Ministry of Education, Science, and Technological Development, Grant no. 174030
The second author’s research was supported by FAPESP (Fundação de Amparo à Pesquisa do Estado de São Paulo under projects CEPID-Cemeai on Industrial Mathematics 2013/07375-0 and PT 2006/53768-0, and CNPq under projects 300933-2009-6 and 400926-2013-0 - © Copyright 2015 American Mathematical Society
- Journal: Math. Comp. 85 (2016), 1775-1791
- MSC (2010): Primary 65K05, 65K10, 90C30, 90C90
- DOI: https://doi.org/10.1090/mcom/3025
- MathSciNet review: 3471107