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

Krejić, Nataša; Martínez, J.

doi:10.1090/mcom/3025

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