×

A derivative-free trust-region algorithm for the optimization of functions smoothed via Gaussian convolution using adaptive multiple importance sampling. (English) Zbl 1390.90410

Summary: In this paper we consider the optimization of a functional \(F\) defined as the convolution of a function \(f\) with a Gaussian kernel. We propose this type of objective function for the optimization of the output of complex computational simulations, which often present some form of deterministic noise and need to be smoothed for the results to be meaningful. We introduce a derivative-free algorithm that computes trial points from the minimization of a regression model of the noisy function \(f\) over a trust region. The regression model is constructed from function values at sample points that are chosen randomly around iterates and trial points of the algorithm. The weights given to the individual sample points in the regression problem are obtained according to an adaptive multiple importance sampling strategy. This has two advantages. First, it makes it possible to reuse all noisy function values collected over the course of the optimization. Second, the resulting regression model converges to the second-order Taylor approximation of the convolution functional \(F\). We prove that, with probability one, each limit point of the iterates is a stationary point of \(F\). Computational experiments on a set of benchmark problems with noisy functions compare the proposed algorithm with the deterministic derivative-free trust-region method the proposed method is based on. It is demonstrated that the proposed algorithm performs similarly efficiently in the early stages of the optimization and is able to overcome convergence problems of the original method, where the algorithm might get trapped in spurious local minima induced by the noise.

MSC:

90C15 Stochastic programming
90C30 Nonlinear programming
90C56 Derivative-free methods and methods using generalized derivatives
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] L. K. Alford, R. F. Beck, J. T. Johnson, D. Lyzenga, O. Nwogu, and A. Zundel, {\it Design, implementation, and evaluation of a system for environmental and ship motion forecasting}, in Proceedings of the 30th Symposium on Naval Hydrodynamics, Hobart, Tasmania, Australia, 2014.
[2] B. Arouna, {\it Adaptative Monte Carlo, a variance reduction technique}, Monte Carlo Methods Appl., 10 (2004), pp. 1-24. · Zbl 1063.65003
[3] A. S. Bandeira, K. Scheinberg, and L. N. Vicente, {\it Computation of sparse low degree interpolating polynomials and their application to derivative-free optimization}, Math. Program., 134 (2012), pp. 223-257. · Zbl 1254.65072
[4] A. S. Bandeira, K. Scheinberg, and L. N. Vicente, {\it Convergence of trust-region methods based on probabilistic models}, SIAM J. Optim., 24 (2014), 1238-1264. · Zbl 1311.90186
[5] S. C. Billups, J. Larson, and P. Graf, {\it Derivative-free optimization of expensive functions with computational error using weighted regression}, SIAM J. Optim., 23 (2013), pp. 27-53. · Zbl 1295.90106
[6] J. Blanchet, C. Cartis, M. Menickelly, and K. Scheinberg, {\it Convergence Rate Analysis of a Stochastic Trust Region Method for Nonconvex Optimization}, preprint, arXiv:1609.07428, 2016.
[7] J. Borggaard, D. Pelletier, and K. E. Vugrin, {\it On sensitivity analysis for problems with numerical noise}, in Proceedings of the 9th AIAA/NASA/USAF/ISSMO Symposium on Multidisciplinary Analysis and Optimization, American Institute of Aeronautics and Astronautics, Reston, VA, 2002, .
[8] M. F. Bugallo, V. Elvira, L. Martino, D. Luengo, J. Miguez, and P. M. Djuric, {\it Adaptive importance sampling: The past, the present, and the future}, IEEE Signal Process. Mag., 34 (2017), pp. 60-79.
[9] K.-H. Chang, L. J. Hong, and H. Wan, {\it Stochastic trust-region response-surface method (STRONG)—A new response-surface framework for simulation optimization}, INFORMS J. Comput., 25 (2013), pp. 230-243.
[10] R. Chen, M. Menickelly, and K. Scheinberg, {\it Stochastic optimization using a trust-region method and random models}, Math. Program. (2017), . · Zbl 1401.90136
[11] W. S. Cleveland and C. Loader, {\it Smoothing by local regression: Principles and methods}, in Statistical Theory and Computational Aspects of Smoothing, Springer, New York, 1996, pp. 10-49.
[12] A. R. Conn, I. M. Elfadel, W. Molzen Jr, P. O’Brien, P. N. Strenski, C. Visweswariah, and C. Whan, {\it Gradient-based optimization of custom circuits using a static-timing formulation}, in Proceedings of the 36th Annual ACM/IEEE Design Automation Conference, ACM, New York, 1999, pp. 452-459.
[13] A. R. Conn, N. I. M. Gould, and P. L. Toint, {\it Trust Region Methods}, SIAM, Philadelphia, PA, 2000. · Zbl 0958.65071
[14] A. R. Conn, K. Scheinberg, and P. L. Toint, {\it A derivative free optimization algorithm in practice}, in Proceedings of 7th AIAA/USAF/NASA/ISSMO Symposium on Multidisciplinary Analysis and Optimization, American Institute of Aeronautics and Astronautics, Reston, VA, 1998, . · Zbl 1042.90617
[15] A. R. Conn, K. Scheinberg, and L. N. Vicente, {\it Geometry of interpolation sets in derivative free optimization}, Math. Program., 111 (2008), pp. 141-172. · Zbl 1163.90022
[16] A. R. Conn, K. Scheinberg, and L. N. Vicente, {\it Global convergence of general derivative-free trust-region algorithms to first- and second-order critical points}, SIAM J. Optim., 20 (2009), pp. 387-415. · Zbl 1187.65062
[17] A. R. Conn, K. Scheinberg, and L. N. Vicente, {\it Introduction to Derivative-Free Optimization}, SIAM, Philadelphia, PA, 2009. · Zbl 1163.49001
[18] J. Cornuet, J.-M. Marin, A. Mira, and C. P. Robert, {\it Adaptive multiple importance sampling}, Scand. J. Statist., 39 (2012), pp. 798-812. · Zbl 1319.62059
[19] A. Custódio, K. Scheinberg, and L. Vicente, {\it Methodologies and software for derivative-free optimization}, in Advances and Trends in Optimization with Engineering Applications, T. Terlaky, M. Anjos, and S. Ahmed, eds., MOS-SIAM Ser. Optim., SIAM, Philadelphia, 2017, pp. 495-506.
[20] G. Deng and M. C. Ferris, {\it Adaptation of the UOBYQA algorithm for noisy functions}, in Proceedings of the 2006 Winter Simulation Conference, 2006, IEEE Press, Piscataway, NJ, pp. 312-319.
[21] G. Fasano, J. L. Morales, and J. Nocedal, {\it On the geometry phase in model-based algorithms for derivative-free optimization}, Optim. Methods Softw., 24 (2009), pp. 145-154. · Zbl 1154.90589
[22] P. Glasserman, {\it Monte Carlo Methods in Financial Engineering}, Stoch. Model. Appl. Probab. 53, Springer, New York, 2004. · Zbl 1038.91045
[23] R. Hooke and T. A. Jeeves, {\it “Direct search” solution of numerical and statistical problems}, J. ACM, 8 (1961), pp. 212-229, . · Zbl 0111.12501
[24] J. Jacod and P. E. Protter, {\it Probability Essentials}, 2nd ed., Universitext, Springer, Berlin, 2004. · Zbl 1014.60004
[25] C. T. Kelley, {\it Iterative Methods for Optimization}, SIAM, Philadelphia, PA, 1999. · Zbl 0934.90082
[26] C. T. Kelley, {\it Implicit Filtering}, Software Environ. Tools 23, SIAM, Philadelphia, PA, 2011, .
[27] J. M. Larson and S. C. Billups, {\it Stochastic Derivative-Free Optimization Using a Trust Region Framework}, Technical report, , 2013. · Zbl 1381.90098
[28] A. Maggiar, {\it Optimization of Smoothed Functionals and Applications of Nonlinear Programming to Fastest Path Finding for Vehicles in Anisotropic Media}, Ph.D. thesis, Northwestern University, Evanston, IL, 2014.
[29] M. Marazzi and J. Nocedal, {\it Wedge trust region methods for derivative free optimization}, Math. Program., 91 (2002), pp. 289-305. · Zbl 1049.90134
[30] J. J. Moré, B. S. Garbow, and K. E. Hillstrom, {\it Testing unconstrained optimization software}, ACM Trans. Math. Softw., 7 (1981), pp. 17-41. · Zbl 0454.65049
[31] J. J. Moré and S. M. Wild, {\it Benchmarking derivative-free optimization algorithms}, . · Zbl 1187.90319
[32] J. J. Moré and S. M. Wild, {\it Benchmarking derivative-free optimization algorithms}, SIAM J. Optim., 20 (2009), pp. 172-191. · Zbl 1187.90319
[33] J. J. Moré and S. M. Wild, {\it Estimating computational noise}, SIAM J. Sci. Comput., 33 (2011), pp. 1292-1314. · Zbl 1243.65016
[34] J. J. Moré and S. M. Wild, {\it Estimating derivatives of noisy simulations}, ACM Trans. Math. Softw., 38 (2012), p. 19. · Zbl 1365.65056
[35] A. Nedić and D. P. Bertsekas, {\it The effect of deterministic noise in subgradient methods}, Math. Program., 125 (2010), pp. 75-99. · Zbl 1205.90225
[36] J. A. Nelder and R. Mead, {\it A simplex method for function minimization}, Comput. J., 7 (1965), pp. 308-313, . · Zbl 0229.65053
[37] H. B. Nielsen, {\it UCTP–Test Problems for Unconstrained Optimization}, Technical report, Technical University of Denmark, Kongens Lyngby, Denmark, 2000.
[38] J. Nocedal and S. J. Wright, {\it Numerical Optimization}, 2nd ed., Springer Ser. Oper. Res. Financ. Eng., Springer, New York, 2006. · Zbl 1104.65059
[39] O. G. Nwogu, {\it Interaction of finite-amplitude waves with vertically-sheared current fields}, J. Fluid Mech., 627 (2009), pp. 179-213. · Zbl 1171.76338
[40] O. G. Nwogu and D. R. Lyzenga, {\it Surface wavefield estimation from coherent marine radars}, IEEE Geosci. Remote Sens. Lett., 7 (2010), pp. 631-635.
[41] A. Owen and Y. Zhou, {\it Safe and effective importance sampling}, J. Amer. Statist. Assoc., 95 (2000), pp. 135-143. · Zbl 0998.65003
[42] A. B. Owen, {\it Monte Carlo Theory, Methods and Examples}, , 2013.
[43] M. J. D. Powell, {\it UOBYQA: Unconstrained optimization by quadratic approximation}, Math. Program., 92 (2002), pp. 555-582. · Zbl 1014.65050
[44] K. Scheinberg and P. L. Toint, {\it Self-correcting geometry in model-based algorithms for derivative-free unconstrained optimization}, SIAM J. Optim., 20 (2010), pp. 3512-3532. · Zbl 1209.65017
[45] S. Shashaani, F. Hashemi, and R. Pasupathy, {\it Astro-df: A Class of Adaptive Sampling Trust-Region Algorithms for Derivative-Free Stochastic Optimization}, preprint, arXiv:1610.06506, 2016. · Zbl 1403.90541
[46] E. Veach and L. J. Guibas, {\it Optimally combining sampling techniques for Monte Carlo rendering}, in Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques, ACM, New York, 1995, pp. 419-428.
[47] C. Visweswariah and R. A. Rohrer, {\it Piecewise approximate circuit simulation}, IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., 10 (1991), pp. 861-870.
[48] K. E. Vugrin, {\it On the Effects of Noise on Parameter Identification Optimization Problems}, Ph.D. thesis, Virginia Polytechnic Institute and State University, Blacksburg, VA, 2005.
[49] A. Wächter, J. Staum, A. Maggiar, and M. Feng, {\it Sample Average Approximation with Adaptive Importance Sampling}, Technical report, Northwestern University, Evanston, IL, , 2017.
[50] X. Zhang, P. Bandyk, and R. F. Beck, {\it Seakeeping computations using double-body basis flows}, Appl. Ocean Res., 32 (2010), pp. 471-482.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.