Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

Request Permissions   Purchase Content 


Inexact Restoration approach for minimization with inexact evaluation of the objective function

Authors: Nataša Krejić and J. M. Martínez
Journal: Math. Comp. 85 (2016), 1775-1791
MSC (2010): Primary 65K05, 65K10, 90C30, 90C90
Published electronically: September 9, 2015
MathSciNet review: 3471107
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [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 (2010f:90153),
  • [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,
  • [3] F. Bastin, Trust-Region Algorithms for Nonlinear Stochastic Programming and Mixed Logit Models, PhD thesis, University of 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,
  • [5] 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.
  • [6] 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,
  • [7] 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 (2003e:90002)
  • [8] 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 (2011h:90137),
  • [9] 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,
  • [10] 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 (97g:65006)
  • [11] 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 (2010d:90131),
  • [12] 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 (electronic). MR 2085935 (2005d:49049),
  • [13] T. Helgaker, P. Jorgensen, and J. Olsen, Molecular Electronic-Structure Theory, John Wiley & Sons, New York, 2000, 433-502.
  • [14] T. Homem-de-Mello, Variable-sample methods for stochastic optimization, ACM Transactions on Modeling and Computer Simulation 13 (2003), 108-133.
  • [15] 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 (2011j:90184),
  • [16] 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 (2011d:90115),
  • [17] 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 (2011j:49063),
  • [18] 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 (2008m:49169),
  • [19] 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,
  • [20] 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,
  • [21] Claude Le Bris, Computational chemistry from the perspective of numerical analysis, Acta Numer. 14 (2005), 363-444. MR 2168346 (2007f:81285),
  • [22] 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 (2003b:90102),
  • [23] 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 (2001h:90084),
  • [24] R. Pasupathy, On choosing parameters in retrospective-approximation algorithms for stochastic root finding and simulation optimization, Operations Research 58 (2010), 889-901.
  • [25] 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 (2009h:90044),
  • [26] J. O. Royset, Optimality functions in stochastic programming, Math. Program. 135 (2012), no. 1-2, Ser. A, 293-321. MR 2968258,
  • [27] 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 (2010m:90001)
  • [28] 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 (2005f:90001)
  • [29] A. Shapiro and Y. Wardi, Convergence analysis of stochastic algorithms, Math. Oper. Res. 21 (1996), no. 3, 615-628. MR 1403308 (97h:90035),
  • [30] 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 (2004b:90005)
  • [31] Y. Wardi, Stochastic algorithms with Armijo stepsizes for minimization of functions, J. Optim. Theory Appl. 64 (1990), no. 2, 399-417. MR 1042003 (91m:90127),

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

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

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

Keywords: Inexact Restoration, inexact evaluations, global convergence, numerical experiments
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
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society