×

zbMATH — the first resource for mathematics

Manifold learning for accelerating coarse-grained optimization. (English) Zbl 1450.37082
Summary: Algorithms proposed for solving high-dimensional optimization problems with no derivative information frequently encounter the “curse of dimensionality, ” becoming ineffective as the dimension of the parameter space grows. One feature of a subclass of such problems that are effectively low-dimensional is that only a few parameters (or combinations thereof) are important for the optimization and must be explored in detail. Knowing these parameters/combinations in advance would greatly simplify the problem and its solution. We propose the data-driven construction of an effective (coarse-grained, “trend”) optimizer, based on data obtained from ensembles of brief simulation bursts with an “inner” optimization algorithm, that has the potential to accelerate the exploration of the parameter space. The trajectories of this “effective optimizer” quickly become attracted onto a slow manifold parameterized by the few relevant parameter combinations. We obtain the parameterization of this low-dimensional, effective optimization manifold on the fly using data mining/manifold learning techniques on the results of simulation (inner optimizer iteration) burst ensembles and exploit it locally to “jump” forward along this manifold. As a result, we can bias the exploration of the parameter space towards the few, important directions and, through this “wrapper algorithm,” speed up the convergence of traditional optimization algorithms.
MSC:
37M99 Approximation methods and numerical treatment of dynamical systems
37N40 Dynamical systems in optimization and economics
68U01 General topics in computing methodologies
68T05 Learning and adaptive systems in artificial intelligence
90C56 Derivative-free methods and methods using generalized derivatives
Software:
KELLEY; MCS; MultiMin
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Y. Aït-Sahalia, Maximum likelihood estimation of discretely sampled diffusions: A closed-form approximation approach, Econometrica, 70, 223-262 (2002) · Zbl 1104.62323
[2] Y. Aït-Sahalia, Closed-form likelihood expansions for multivariate diffusions, Ann. Statist., 36, 906-937 (2008) · Zbl 1246.62180
[3] R. Barton, Metamodeling: A state of the art review, Proc. Winter Simul. Conf., (1994), 237-244.
[4] K. Chan; G. Karolyi; F. Longstaff; A. Sanders, An empirical comparison of alternative models of the short-term interest rate, J. Finance, 47, 1209-1227 (1992)
[5] E. Chiavazzo; C. Gear; C. Dsilva; N. Rabin; I. Kevrekidis, Reduced models in chemical kinetics via nonlinear data-mining, Processes, 2, 112-140 (2014)
[6] R. R. Coifman; S. Lafon, Diffusion maps, Appl. Comput. Harmon. Anal., 21, 5-30 (2006) · Zbl 1095.68094
[7] R. R. Coifman; S. Lafon, Geometric harmonics: A novel tool for multiscale out-of-sample extension of empirical functions, Appl. Comput. Harmon. Anal., 21, 31-52 (2006) · Zbl 1095.68095
[8] R. Coifman; S. Lafon; A. Lee; M. Maggioni; B. Nadler; F. Warner; S. Zucker, Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps, Proc. Nat. Acad. Sci. USA, 102, 7426-7431 (2005) · Zbl 1405.42043
[9] A. R. Conn, N. I. M. Gould and P. L. Toint, Trust-Region Methods, MPS/SIAM Series on Optimization, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2000.
[10] A. R. Conn, K. Scheinberg and L. N. Vicente, Introduction to Derivative-Free Optimization, MPS/SIAM Series on Optimization, 8, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2009. · Zbl 1163.49001
[11] C. J. Dsilva; R. Talmon; R. R. Coifman; I. G. Kevrekidis, Parsimonious representation of nonlinear dynamical systems through manifold learning: A chemotaxis case study, Appl. Comput. Harmon. Anal., 44, 759-773 (2018) · Zbl 1390.68523
[12] C. J. Dsilva, R. Talmon, N. Rabin, R. R. Coifman and I. G. Kevrekidis, Nonlinear intrinsic variables and state reconstruction in multiscale simulations, J. Chemical Phys., 139 (2013).
[13] A. Duncan, G. Pavliotis and K. Zygalakis, Nonreversible langevin samplers: Splitting schemes, analysis and implementation, preprint, arXiv: 1701.04247.
[14] R. Eberhart and J. Kennedy, A new optimizer using particle swarm theory, Proc. Sixth Internat. Symposium Micro Machine Human Science, Nagoya, Japan, 1995, 39-43.
[15] M. Fathi; G. Stoltz, Improving dynamical properties of metropolized discretizations of overdamped Langevin dynamics, Numer. Math., 136, 545-602 (2017) · Zbl 1458.65007
[16] C. W. Gear; D. Givon; I. G. Kevrekidis, Computing on virtual slow manifolds of fast stochastic systems, JNAIAM. J. Numer. Anal. Ind. Appl. Math., 5, 61-72 (2010) · Zbl 1432.65088
[17] C. W. Gear; I. G. Kevrekidis, Projective methods for stiff differential equations: Problems with gaps in their eigenvalue spectrum, SIAM J. Sci. Comput., 24, 1091-1106 (2003) · Zbl 1034.65056
[18] S. Geman; C.-R. Hwang, Diffusions for global optimization, SIAM J. Control Optim., 24, 1031-1043 (1986) · Zbl 0602.60071
[19] B. Gidas, Global optimization via the langevin equation, 24th IEEE Conference on Decision and Control, Ft. Lauderdale, FL, 1985,774-778.
[20] J. Gradišek, S. Siegert, R. Friedrich and I. Grabec, Analysis of time series from stochastic processes, Phys. Rev. E, 62 (2000).
[21] L. Hansen, Large sample properties of generalized method of moments estimators, Econometrica, 50, 1029-1054 (1982) · Zbl 0502.62098
[22] J. H. Holland, Adaptation in Natural and Artificial Systems. An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, University of Michigan Press, Ann Arbor, Mich., 1975. · Zbl 0317.68006
[23] R. Hooke; T. Jeeves, “Direct search” solution of numerical and statistical problems, J. ACM, 8, 212-229 (1961) · Zbl 0111.12501
[24] W. Huyer; A. Neumaier, Global optimization by multilevel coordinate search, J. Global Optim., 14, 331-355 (1999) · Zbl 0956.90045
[25] I. T. Jolliffe, Principal Component Analysis, Springer Series in Statistics. Springer-Verlag, New York, 1986. · Zbl 1011.62064
[26] D. R. Jones, A taxonomy of global optimization methods based on response surfaces, J. Global Optim., 21, 345-383 (2001) · Zbl 1172.90492
[27] D. R. Jones; C. D. Perttunen; B. E. Stuckman, Lipschitzian optimization without the Lipschitz constant, J. Optim. Theory Appl., 79, 157-181 (1993) · Zbl 0796.49032
[28] S. Kalliadasis; S. Krumscheid; G. A. Pavliotis, A new framework for extracting coarse-grained models from time series with multiscale structure, J. Comput. Phys., 296, 314-328 (2015) · Zbl 1352.62136
[29] C. Kelley, Iterative Methods for Optimization, Frontiers in Applied Mathematics, 18, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1999. · Zbl 0934.90082
[30] I. G. Kevrekidis; C. W. Gear; J. M. Hyman; P. G. Kevrekidis; O. Runborg; C. Theodoropoulos, Equation-free, coarse-grained multiscale computation: Enabling mocroscopic simulators to perform system-level analysis, Commun. Math. Sci., 1, 715-762 (2003) · Zbl 1086.65066
[31] S. Kirkpatrick; C. D. Gelatt; M. P. Vecchi, Optimization by simulated annealing, Science, 220, 671-680 (1983) · Zbl 1225.90162
[32] S. Krumscheid; G. A. Pavliotis; S. Kalliadasis, Semiparametric drift and diffusion estimation for multiscale diffusions, Multiscale Model. Simul., 11, 442-473 (2013) · Zbl 1411.60085
[33] S. Krumscheid, M. Pradas, G. Pavliotis and S. Kalliadasis, Data-driven coarse graining in action: Modeling and prediction of complex systems, Phys. Rev. E, 92 (2015).
[34] S. Lafon; Y. Keller; R. Coifman, Data fusion and multicue data matching by diffusion maps, IEEE Transac. Pattern Anal. Machine Intelligence, 28, 1784-1797 (2006)
[35] G. Li; C. Rosenthal; H. Rabitz, High dimensional model representations, J. Phys. Chem. A, 105, 7765-7777 (2001)
[36] M. Locatelli, Simulated annealing algorithms for continuous global optimization, in Handbook of Global Optimization, Nonconvex Optim. Appl., 62, Kluwer Acad. Publ., Dordrecht, 2002,179-229. · Zbl 1111.90361
[37] I. Melbourne; A. M. Stuart, A note on diffusion limits of chaotic skew-product flows, Nonlinearity, 24, 1361-1367 (2011) · Zbl 1220.37009
[38] N. Metropolis; A. Rosenbluth; M. Rosenbluth; A. Teller; E. Teller, Equation of state calculations by fast computing machines, J. Phys. Chem., 21, 1087-1092 (1953) · Zbl 1431.65006
[39] M. Montgomery; R. Meglen; N. Damrauer, General method for the dimension reduction of adaptive control experiments, J. Phys. Chem. A, 110, 6391-6394 (2006)
[40] M. Montgomery; R. Meglen; N. Damrauer, General method for reducing adaptive laser pulse-shaping experiments to a single control variable, J. Phys. Chem. A, 111, 5126-5129 (2007)
[41] J. A. Nelder; R. Mead, A simplex method for function minimization, Comput. J., 7, 308-313 (1965) · Zbl 0229.65053
[42] B. Øksendal, Stochastic Differential Equations, Universitext, Springer-Verlag, Berlin, 2003.
[43] A. Papavasiliou, Particle filters for multiscale diffusions, in Conference Oxford sur les méthodes de Monte Carlo séquentielles, ESAIM Proc., 19, EDP Sci., Les Ulis, 2007,108-114. · Zbl 1330.60061
[44] G. A. Pavliotis, Stochastic Processes and Applications. Diffusion Processes, the Fokker-Planck and Langevin Equations, Texts in Applied Mathematics, 60, Springer, New York, 2014. · Zbl 1318.60003
[45] G. A. Pavliotis; A. M. Stuart, Parameter estimation for multiscale diffusions, J. Stat. Phys., 127, 741-781 (2007) · Zbl 1137.82016
[46] L. M. Rios; N. V. Sahinidis, Derivative-free optimization: A review of algorithms and comparison of software implementations, J. Global Optim., 56, 1247-1293 (2013) · Zbl 1272.90116
[47] J. Roslund and H. Rabitz, Dynamic dimensionality identification for quantum control, Phys. Rev. Lett., 112 (2014).
[48] C. Schillings; A. M. Stuart, Analysis of the ensemble Kalman filter for inverse problems, SIAM J. Numer. Anal., 55, 1264-1290 (2017) · Zbl 1366.65101
[49] S. Shan; G. G. Wang, Survey of modeling and optimization strategies to solve high-dimensional design problems with computationally-expensive black-box functions, Struct. Multidiscip. Optim., 41, 219-241 (2010) · Zbl 1274.74291
[50] A. Singer; R. R. Coifman, Non-linear independent component analysis with diffusion maps, Appl. Comput. Harmon. Anal., 25, 226-239 (2008) · Zbl 1144.62044
[51] E. Vanden-Eijnden, Numerical techniques for multi-scale dynamical systems with stochastic effects, Commun. Math. Sci., 1, 385-391 (2003) · Zbl 1088.60060
[52] E. Weinan; B. Engquist; X. Li; W. Ren; E. Vanden-Eijnden, Heterogeneous multiscale methods: A review, Commun. Comput. Phys., 2, 367-450 (2007) · Zbl 1164.65496
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.