December  2020, 7(2): 511-536. doi: 10.3934/jcd.2020021

Manifold learning for accelerating coarse-grained optimization

1. 

Department of Chemical and Biological Engineering, Princeton University, Princeton, NJ 08544, USA

2. 

Department of Applied Mathematics and Statistics (AMS), Johns Hopkins University, Baltimore, MD 21218, USA

3. 

Department of Mathematics, Imperial College London, London SW7 2AZ, UK

4. 

Department of Chemical and Biomolecular Engineering & AMS, Johns Hopkins University, Baltimore, MD 21218, USA

* Corresponding author

Received  October 2019 Published  July 2020

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.

Citation: Dmitry Pozharskiy, Noah J. Wichrowski, Andrew B. Duncan, Grigorios A. Pavliotis, Ioannis G. Kevrekidis. Manifold learning for accelerating coarse-grained optimization. Journal of Computational Dynamics, 2020, 7 (2) : 511-536. doi: 10.3934/jcd.2020021
References:
[1]

Y. Aït-Sahalia, Maximum likelihood estimation of discretely sampled diffusions: A closed-form approximation approach, Econometrica, 70 (2002), 223-262.  doi: 10.1111/1468-0262.00274.  Google Scholar

[2]

Y. Aït-Sahalia, Closed-form likelihood expansions for multivariate diffusions, Ann. Statist., 36 (2008), 906-937.  doi: 10.1214/009053607000000622.  Google Scholar

[3]

R. Barton, Metamodeling: A state of the art review, Proc. Winter Simul. Conf., (1994), 237–244. doi: 10.1109/WSC.1994.717134.  Google Scholar

[4]

K. ChanG. KarolyiF. Longstaff and A. Sanders, An empirical comparison of alternative models of the short-term interest rate, J. Finance, 47 (1992), 1209-1227.  doi: 10.1111/j.1540-6261.1992.tb04011.x.  Google Scholar

[5]

E. ChiavazzoC. GearC. DsilvaN. Rabin and I. Kevrekidis, Reduced models in chemical kinetics via nonlinear data-mining, Processes, 2 (2014), 112-140.  doi: 10.3390/pr2010112.  Google Scholar

[6]

R. R. Coifman and S. Lafon, Diffusion maps, Appl. Comput. Harmon. Anal., 21 (2006), 5-30.  doi: 10.1016/j.acha.2006.04.006.  Google Scholar

[7]

R. R. Coifman and S. Lafon, Geometric harmonics: A novel tool for multiscale out-of-sample extension of empirical functions, Appl. Comput. Harmon. Anal., 21 (2006), 31-52.  doi: 10.1016/j.acha.2005.07.005.  Google Scholar

[8]

R. CoifmanS. LafonA. LeeM. MaggioniB. NadlerF. Warner and S. Zucker, Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps, Proc. Nat. Acad. Sci. USA, 102 (2005), 7426-7431.  doi: 10.1073/pnas.0500334102.  Google Scholar

[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. doi: 10.1137/1.9780898719857.  Google Scholar

[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. doi: 10.1137/1.9780898718768.  Google Scholar

[11]

C. J. DsilvaR. TalmonR. R. Coifman and I. G. Kevrekidis, Parsimonious representation of nonlinear dynamical systems through manifold learning: A chemotaxis case study, Appl. Comput. Harmon. Anal., 44 (2018), 759-773.  doi: 10.1016/j.acha.2015.06.008.  Google Scholar

[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). doi: 10.1063/1.4828457.  Google Scholar

[13]

A. Duncan, G. Pavliotis and K. Zygalakis, Nonreversible langevin samplers: Splitting schemes, analysis and implementation, preprint, arXiv: 1701.04247. Google Scholar

[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. doi: 10.1109/MHS.1995.494215.  Google Scholar

[15]

M. Fathi and G. Stoltz, Improving dynamical properties of metropolized discretizations of overdamped Langevin dynamics, Numer. Math., 136 (2017), 545-602.  doi: 10.1007/s00211-016-0849-3.  Google Scholar

[16]

C. W. GearD. Givon and I. G. Kevrekidis, Computing on virtual slow manifolds of fast stochastic systems, JNAIAM. J. Numer. Anal. Ind. Appl. Math., 5 (2010), 61-72.   Google Scholar

[17]

C. W. Gear and I. G. Kevrekidis, Projective methods for stiff differential equations: Problems with gaps in their eigenvalue spectrum, SIAM J. Sci. Comput., 24 (2003), 1091-1106.  doi: 10.1137/S1064827501388157.  Google Scholar

[18]

S. Geman and C.-R. Hwang, Diffusions for global optimization, SIAM J. Control Optim., 24 (1986), 1031-1043.  doi: 10.1137/0324060.  Google Scholar

[19]

B. Gidas, Global optimization via the langevin equation, 24th IEEE Conference on Decision and Control, Ft. Lauderdale, FL, 1985,774–778. doi: 10.1109/CDC.1985.268602.  Google Scholar

[20]

J. Gradišek, S. Siegert, R. Friedrich and I. Grabec, Analysis of time series from stochastic processes, Phys. Rev. E, 62 (2000). Google Scholar

[21]

L. Hansen, Large sample properties of generalized method of moments estimators, Econometrica, 50 (1982), 1029-1054.  doi: 10.2307/1912775.  Google Scholar

[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.  Google Scholar

[23]

R. Hooke and T. Jeeves, "Direct search" solution of numerical and statistical problems, J. ACM, 8 (1961), 212-229.  doi: 10.1145/321062.321069.  Google Scholar

[24]

W. Huyer and A. Neumaier, Global optimization by multilevel coordinate search, J. Global Optim., 14 (1999), 331-355.  doi: 10.1023/A:1008382309369.  Google Scholar

[25]

I. T. Jolliffe, Principal Component Analysis, Springer Series in Statistics. Springer-Verlag, New York, 1986. doi: 10.1007/978-1-4757-1904-8.  Google Scholar

[26]

D. R. Jones, A taxonomy of global optimization methods based on response surfaces, J. Global Optim., 21 (2001), 345-383.  doi: 10.1023/A:1012771025575.  Google Scholar

[27]

D. R. JonesC. D. Perttunen and B. E. Stuckman, Lipschitzian optimization without the Lipschitz constant, J. Optim. Theory Appl., 79 (1993), 157-181.  doi: 10.1007/BF00941892.  Google Scholar

[28]

S. KalliadasisS. Krumscheid and G. A. Pavliotis, A new framework for extracting coarse-grained models from time series with multiscale structure, J. Comput. Phys., 296 (2015), 314-328.  doi: 10.1016/j.jcp.2015.05.002.  Google Scholar

[29]

C. Kelley, Iterative Methods for Optimization, Frontiers in Applied Mathematics, 18, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1999. doi: 10.1137/1.9781611970920.  Google Scholar

[30]

I. G. KevrekidisC. W. GearJ. M. HymanP. G. KevrekidisO. Runborg and C. Theodoropoulos, Equation-free, coarse-grained multiscale computation: Enabling mocroscopic simulators to perform system-level analysis, Commun. Math. Sci., 1 (2003), 715-762.  doi: 10.4310/CMS.2003.v1.n4.a5.  Google Scholar

[31]

S. KirkpatrickC. D. Gelatt and M. P. Vecchi, Optimization by simulated annealing, Science, 220 (1983), 671-680.  doi: 10.1126/science.220.4598.671.  Google Scholar

[32]

S. KrumscheidG. A. Pavliotis and S. Kalliadasis, Semiparametric drift and diffusion estimation for multiscale diffusions, Multiscale Model. Simul., 11 (2013), 442-473.  doi: 10.1137/110854485.  Google Scholar

[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). doi: 10.1103/PhysRevE.92.042139.  Google Scholar

[34]

S. LafonY. Keller and R. Coifman, Data fusion and multicue data matching by diffusion maps, IEEE Transac. Pattern Anal. Machine Intelligence, 28 (2006), 1784-1797.  doi: 10.1109/TPAMI.2006.223.  Google Scholar

[35]

G. LiC. Rosenthal and H. Rabitz, High dimensional model representations, J. Phys. Chem. A, 105 (2001), 7765-7777.  doi: 10.1021/jp010450t.  Google Scholar

[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. doi: 10.1007/978-1-4757-5362-2_6.  Google Scholar

[37]

I. Melbourne and A. M. Stuart, A note on diffusion limits of chaotic skew-product flows, Nonlinearity, 24 (2011), 1361-1367.  doi: 10.1088/0951-7715/24/4/018.  Google Scholar

[38]

N. MetropolisA. RosenbluthM. RosenbluthA. Teller and E. Teller, Equation of state calculations by fast computing machines, J. Phys. Chem., 21 (1953), 1087-1092.  doi: 10.2172/4390578.  Google Scholar

[39]

M. MontgomeryR. Meglen and N. Damrauer, General method for the dimension reduction of adaptive control experiments, J. Phys. Chem. A, 110 (2006), 6391-6394.  doi: 10.1021/jp061160l.  Google Scholar

[40]

M. MontgomeryR. Meglen and N. Damrauer, General method for reducing adaptive laser pulse-shaping experiments to a single control variable, J. Phys. Chem. A, 111 (2007), 5126-5129.  doi: 10.1021/jp073132o.  Google Scholar

[41]

J. A. Nelder and R. Mead, A simplex method for function minimization, Comput. J., 7 (1965), 308-313.  doi: 10.1093/comjnl/7.4.308.  Google Scholar

[42]

B. Øksendal, Stochastic Differential Equations, Universitext, Springer-Verlag, Berlin, 2003. doi: 10.1007/978-3-642-14394-6.  Google Scholar

[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. doi: 10.1051/proc:071914.  Google Scholar

[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. doi: 10.1007/978-1-4939-1323-7.  Google Scholar

[45]

G. A. Pavliotis and A. M. Stuart, Parameter estimation for multiscale diffusions, J. Stat. Phys., 127 (2007), 741-781.  doi: 10.1007/s10955-007-9300-6.  Google Scholar

[46]

L. M. Rios and N. V. Sahinidis, Derivative-free optimization: A review of algorithms and comparison of software implementations, J. Global Optim., 56 (2013), 1247-1293.  doi: 10.1007/s10898-012-9951-y.  Google Scholar

[47]

J. Roslund and H. Rabitz, Dynamic dimensionality identification for quantum control, Phys. Rev. Lett., 112 (2014). doi: 10.1103/PhysRevLett.112.143001.  Google Scholar

[48]

C. Schillings and A. M. Stuart, Analysis of the ensemble Kalman filter for inverse problems, SIAM J. Numer. Anal., 55 (2017), 1264-1290.  doi: 10.1137/16M105959X.  Google Scholar

[49]

S. Shan and 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 (2010), 219-241.  doi: 10.1007/s00158-009-0420-2.  Google Scholar

[50]

A. Singer and R. R. Coifman, Non-linear independent component analysis with diffusion maps, Appl. Comput. Harmon. Anal., 25 (2008), 226-239.  doi: 10.1016/j.acha.2007.11.001.  Google Scholar

[51]

E. Vanden-Eijnden, Numerical techniques for multi-scale dynamical systems with stochastic effects, Commun. Math. Sci., 1 (2003), 385-391.  doi: 10.4310/CMS.2003.v1.n2.a11.  Google Scholar

[52]

E. WeinanB. EngquistX. LiW. Ren and E. Vanden-Eijnden, Heterogeneous multiscale methods: A review, Commun. Comput. Phys., 2 (2007), 367-450.   Google Scholar

show all references

References:
[1]

Y. Aït-Sahalia, Maximum likelihood estimation of discretely sampled diffusions: A closed-form approximation approach, Econometrica, 70 (2002), 223-262.  doi: 10.1111/1468-0262.00274.  Google Scholar

[2]

Y. Aït-Sahalia, Closed-form likelihood expansions for multivariate diffusions, Ann. Statist., 36 (2008), 906-937.  doi: 10.1214/009053607000000622.  Google Scholar

[3]

R. Barton, Metamodeling: A state of the art review, Proc. Winter Simul. Conf., (1994), 237–244. doi: 10.1109/WSC.1994.717134.  Google Scholar

[4]

K. ChanG. KarolyiF. Longstaff and A. Sanders, An empirical comparison of alternative models of the short-term interest rate, J. Finance, 47 (1992), 1209-1227.  doi: 10.1111/j.1540-6261.1992.tb04011.x.  Google Scholar

[5]

E. ChiavazzoC. GearC. DsilvaN. Rabin and I. Kevrekidis, Reduced models in chemical kinetics via nonlinear data-mining, Processes, 2 (2014), 112-140.  doi: 10.3390/pr2010112.  Google Scholar

[6]

R. R. Coifman and S. Lafon, Diffusion maps, Appl. Comput. Harmon. Anal., 21 (2006), 5-30.  doi: 10.1016/j.acha.2006.04.006.  Google Scholar

[7]

R. R. Coifman and S. Lafon, Geometric harmonics: A novel tool for multiscale out-of-sample extension of empirical functions, Appl. Comput. Harmon. Anal., 21 (2006), 31-52.  doi: 10.1016/j.acha.2005.07.005.  Google Scholar

[8]

R. CoifmanS. LafonA. LeeM. MaggioniB. NadlerF. Warner and S. Zucker, Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps, Proc. Nat. Acad. Sci. USA, 102 (2005), 7426-7431.  doi: 10.1073/pnas.0500334102.  Google Scholar

[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. doi: 10.1137/1.9780898719857.  Google Scholar

[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. doi: 10.1137/1.9780898718768.  Google Scholar

[11]

C. J. DsilvaR. TalmonR. R. Coifman and I. G. Kevrekidis, Parsimonious representation of nonlinear dynamical systems through manifold learning: A chemotaxis case study, Appl. Comput. Harmon. Anal., 44 (2018), 759-773.  doi: 10.1016/j.acha.2015.06.008.  Google Scholar

[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). doi: 10.1063/1.4828457.  Google Scholar

[13]

A. Duncan, G. Pavliotis and K. Zygalakis, Nonreversible langevin samplers: Splitting schemes, analysis and implementation, preprint, arXiv: 1701.04247. Google Scholar

[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. doi: 10.1109/MHS.1995.494215.  Google Scholar

[15]

M. Fathi and G. Stoltz, Improving dynamical properties of metropolized discretizations of overdamped Langevin dynamics, Numer. Math., 136 (2017), 545-602.  doi: 10.1007/s00211-016-0849-3.  Google Scholar

[16]

C. W. GearD. Givon and I. G. Kevrekidis, Computing on virtual slow manifolds of fast stochastic systems, JNAIAM. J. Numer. Anal. Ind. Appl. Math., 5 (2010), 61-72.   Google Scholar

[17]

C. W. Gear and I. G. Kevrekidis, Projective methods for stiff differential equations: Problems with gaps in their eigenvalue spectrum, SIAM J. Sci. Comput., 24 (2003), 1091-1106.  doi: 10.1137/S1064827501388157.  Google Scholar

[18]

S. Geman and C.-R. Hwang, Diffusions for global optimization, SIAM J. Control Optim., 24 (1986), 1031-1043.  doi: 10.1137/0324060.  Google Scholar

[19]

B. Gidas, Global optimization via the langevin equation, 24th IEEE Conference on Decision and Control, Ft. Lauderdale, FL, 1985,774–778. doi: 10.1109/CDC.1985.268602.  Google Scholar

[20]

J. Gradišek, S. Siegert, R. Friedrich and I. Grabec, Analysis of time series from stochastic processes, Phys. Rev. E, 62 (2000). Google Scholar

[21]

L. Hansen, Large sample properties of generalized method of moments estimators, Econometrica, 50 (1982), 1029-1054.  doi: 10.2307/1912775.  Google Scholar

[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.  Google Scholar

[23]

R. Hooke and T. Jeeves, "Direct search" solution of numerical and statistical problems, J. ACM, 8 (1961), 212-229.  doi: 10.1145/321062.321069.  Google Scholar

[24]

W. Huyer and A. Neumaier, Global optimization by multilevel coordinate search, J. Global Optim., 14 (1999), 331-355.  doi: 10.1023/A:1008382309369.  Google Scholar

[25]

I. T. Jolliffe, Principal Component Analysis, Springer Series in Statistics. Springer-Verlag, New York, 1986. doi: 10.1007/978-1-4757-1904-8.  Google Scholar

[26]

D. R. Jones, A taxonomy of global optimization methods based on response surfaces, J. Global Optim., 21 (2001), 345-383.  doi: 10.1023/A:1012771025575.  Google Scholar

[27]

D. R. JonesC. D. Perttunen and B. E. Stuckman, Lipschitzian optimization without the Lipschitz constant, J. Optim. Theory Appl., 79 (1993), 157-181.  doi: 10.1007/BF00941892.  Google Scholar

[28]

S. KalliadasisS. Krumscheid and G. A. Pavliotis, A new framework for extracting coarse-grained models from time series with multiscale structure, J. Comput. Phys., 296 (2015), 314-328.  doi: 10.1016/j.jcp.2015.05.002.  Google Scholar

[29]

C. Kelley, Iterative Methods for Optimization, Frontiers in Applied Mathematics, 18, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1999. doi: 10.1137/1.9781611970920.  Google Scholar

[30]

I. G. KevrekidisC. W. GearJ. M. HymanP. G. KevrekidisO. Runborg and C. Theodoropoulos, Equation-free, coarse-grained multiscale computation: Enabling mocroscopic simulators to perform system-level analysis, Commun. Math. Sci., 1 (2003), 715-762.  doi: 10.4310/CMS.2003.v1.n4.a5.  Google Scholar

[31]

S. KirkpatrickC. D. Gelatt and M. P. Vecchi, Optimization by simulated annealing, Science, 220 (1983), 671-680.  doi: 10.1126/science.220.4598.671.  Google Scholar

[32]

S. KrumscheidG. A. Pavliotis and S. Kalliadasis, Semiparametric drift and diffusion estimation for multiscale diffusions, Multiscale Model. Simul., 11 (2013), 442-473.  doi: 10.1137/110854485.  Google Scholar

[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). doi: 10.1103/PhysRevE.92.042139.  Google Scholar

[34]

S. LafonY. Keller and R. Coifman, Data fusion and multicue data matching by diffusion maps, IEEE Transac. Pattern Anal. Machine Intelligence, 28 (2006), 1784-1797.  doi: 10.1109/TPAMI.2006.223.  Google Scholar

[35]

G. LiC. Rosenthal and H. Rabitz, High dimensional model representations, J. Phys. Chem. A, 105 (2001), 7765-7777.  doi: 10.1021/jp010450t.  Google Scholar

[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. doi: 10.1007/978-1-4757-5362-2_6.  Google Scholar

[37]

I. Melbourne and A. M. Stuart, A note on diffusion limits of chaotic skew-product flows, Nonlinearity, 24 (2011), 1361-1367.  doi: 10.1088/0951-7715/24/4/018.  Google Scholar

[38]

N. MetropolisA. RosenbluthM. RosenbluthA. Teller and E. Teller, Equation of state calculations by fast computing machines, J. Phys. Chem., 21 (1953), 1087-1092.  doi: 10.2172/4390578.  Google Scholar

[39]

M. MontgomeryR. Meglen and N. Damrauer, General method for the dimension reduction of adaptive control experiments, J. Phys. Chem. A, 110 (2006), 6391-6394.  doi: 10.1021/jp061160l.  Google Scholar

[40]

M. MontgomeryR. Meglen and N. Damrauer, General method for reducing adaptive laser pulse-shaping experiments to a single control variable, J. Phys. Chem. A, 111 (2007), 5126-5129.  doi: 10.1021/jp073132o.  Google Scholar

[41]

J. A. Nelder and R. Mead, A simplex method for function minimization, Comput. J., 7 (1965), 308-313.  doi: 10.1093/comjnl/7.4.308.  Google Scholar

[42]

B. Øksendal, Stochastic Differential Equations, Universitext, Springer-Verlag, Berlin, 2003. doi: 10.1007/978-3-642-14394-6.  Google Scholar

[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. doi: 10.1051/proc:071914.  Google Scholar

[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. doi: 10.1007/978-1-4939-1323-7.  Google Scholar

[45]

G. A. Pavliotis and A. M. Stuart, Parameter estimation for multiscale diffusions, J. Stat. Phys., 127 (2007), 741-781.  doi: 10.1007/s10955-007-9300-6.  Google Scholar

[46]

L. M. Rios and N. V. Sahinidis, Derivative-free optimization: A review of algorithms and comparison of software implementations, J. Global Optim., 56 (2013), 1247-1293.  doi: 10.1007/s10898-012-9951-y.  Google Scholar

[47]

J. Roslund and H. Rabitz, Dynamic dimensionality identification for quantum control, Phys. Rev. Lett., 112 (2014). doi: 10.1103/PhysRevLett.112.143001.  Google Scholar

[48]

C. Schillings and A. M. Stuart, Analysis of the ensemble Kalman filter for inverse problems, SIAM J. Numer. Anal., 55 (2017), 1264-1290.  doi: 10.1137/16M105959X.  Google Scholar

[49]

S. Shan and 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 (2010), 219-241.  doi: 10.1007/s00158-009-0420-2.  Google Scholar

[50]

A. Singer and R. R. Coifman, Non-linear independent component analysis with diffusion maps, Appl. Comput. Harmon. Anal., 25 (2008), 226-239.  doi: 10.1016/j.acha.2007.11.001.  Google Scholar

[51]

E. Vanden-Eijnden, Numerical techniques for multi-scale dynamical systems with stochastic effects, Commun. Math. Sci., 1 (2003), 385-391.  doi: 10.4310/CMS.2003.v1.n2.a11.  Google Scholar

[52]

E. WeinanB. EngquistX. LiW. Ren and E. Vanden-Eijnden, Heterogeneous multiscale methods: A review, Commun. Comput. Phys., 2 (2007), 367-450.   Google Scholar

Figure 1.  Evolution in time of the probability density of current points using either the Langevin equation or SA at constant $T$. The objective function is $f(x) = 0.5x^2$; $10^4$ realizations are used with starting point $x = 1$, $T = 0.5$; and the time step is $dt = 10^{-3}$
Figure 2.  Applying Diffusion Maps to the Swiss roll data set
Figure 3.  One complete run of the algorithm that approaches the global maximum. Six total "coarse iterations" (shown in red) were performed. In addition, a single run of SA using the same number of function evaluations is shown in green. Our algorithm visibly approaches the maximum much faster
Figure 4.  A comparison of the evolving maximum objective value for both methods. SA combined with DMaps needs only a fraction of the total function evaluations compared to simple SA
Figure 5.  Diffusion Maps applied to bursts on a rectangular strip]{Diffusion maps applied to (A) the original 2D data with Euclidean distances, and (B) the transformed data with Mahalanobis distances. In both cases, the inherent dimensionality is recovered in the first two eigenvectors, as the coloring of the data by the leading Diffusion Map coordinates corresponding to these two eigenvectors show
Figure 6.  Estimation of the first drift coefficient $ \theta_1 $. "Theoretical" are obtained numerically from (5), "Euclidean" via DMaps on the original data, and "Mahalanobis" from DMaps on the transformed data. The last subplot shows results from Euclidean DMaps on transformed data, which, as expected, yields incorrect estimates
Figure 7.  Estimation of the second drift coefficient $ \theta_2 $. The subplots are analogous to those in Figure 6
Figure 8.  Coarse-grained (two-dimensional) optimization on a cylindrical surface in three dimensions. One complete run of the algorithm, illustrating the short bursts of trajectories and new points after being lifted by geometric harmonics. Observe that, although the lifting does not perfectly locate the cylinder, the burst trajectories are quickly attracted back to it. The second plot is a top-down view of the first
Figure 9.  Simulation of a short trajectory initialized at perturbed initial conditions $ (x_{ic}, \bf{y}_{ic}) $
Figure 10.  The first diffusion coordinate parameterizes $ x $
Figure 11.  Estimation of the drift coefficient in diffusion map space
Figure 12.  Estimation of the diffusion coefficient in diffusion map space
Figure 13.  Nonlinear transformation of the slow variable $ x $ onto a semicircle in the plane
Figure 14.  Embeddings of the original and transformed data set
Figure 15.  Estimation of the drift coefficient in Diffusion Map space
Figure 16.  Estimation of the diffusion coefficient in Diffusion Map space
Figure 17.  Estimation of the drift coefficient in diffusion map space
Figure 18.  Estimation of the diffusion coefficient in diffusion map space
[1]

Min Xi, Wenyu Sun, Jun Chen. Survey of derivative-free optimization. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 537-555. doi: 10.3934/naco.2020050

[2]

A. M. Bagirov, Moumita Ghosh, Dean Webb. A derivative-free method for linearly constrained nonsmooth optimization. Journal of Industrial & Management Optimization, 2006, 2 (3) : 319-338. doi: 10.3934/jimo.2006.2.319

[3]

Liang Zhang, Wenyu Sun, Raimundo J. B. de Sampaio, Jinyun Yuan. A wedge trust region method with self-correcting geometry for derivative-free optimization. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 169-184. doi: 10.3934/naco.2015.5.169

[4]

Jun Takaki, Nobuo Yamashita. A derivative-free trust-region algorithm for unconstrained optimization with controlled error. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 117-145. doi: 10.3934/naco.2011.1.117

[5]

Wei-Zhe Gu, Li-Yong Lu. The linear convergence of a derivative-free descent method for nonlinear complementarity problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 531-548. doi: 10.3934/jimo.2016030

[6]

Gaohang Yu. A derivative-free method for solving large-scale nonlinear systems of equations. Journal of Industrial & Management Optimization, 2010, 6 (1) : 149-160. doi: 10.3934/jimo.2010.6.149

[7]

Dong-Hui Li, Xiao-Lin Wang. A modified Fletcher-Reeves-Type derivative-free method for symmetric nonlinear equations. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 71-82. doi: 10.3934/naco.2011.1.71

[8]

Aurore Back, Emmanuel Frénod. Geometric two-scale convergence on manifold and applications to the Vlasov equation. Discrete & Continuous Dynamical Systems - S, 2015, 8 (1) : 223-241. doi: 10.3934/dcdss.2015.8.223

[9]

Bülent Karasözen. Survey of trust-region derivative free optimization methods. Journal of Industrial & Management Optimization, 2007, 3 (2) : 321-334. doi: 10.3934/jimo.2007.3.321

[10]

Yukang He, Zhengwen He, Nengmin Wang. Tabu search and simulated annealing for resource-constrained multi-project scheduling to minimize maximal cash flow gap. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020077

[11]

Lan Luo, Zhe Zhang, Yong Yin. Simulated annealing and genetic algorithm based method for a bi-level seru loading problem with worker assignment in seru production systems. Journal of Industrial & Management Optimization, 2019  doi: 10.3934/jimo.2019134

[12]

T. W. Leung, Chi Kin Chan, Marvin D. Troutt. A mixed simulated annealing-genetic algorithm approach to the multi-buyer multi-item joint replenishment problem: advantages of meta-heuristics. Journal of Industrial & Management Optimization, 2008, 4 (1) : 53-66. doi: 10.3934/jimo.2008.4.53

[13]

Jan Haskovec, Nader Masmoudi, Christian Schmeiser, Mohamed Lazhar Tayeb. The Spherical Harmonics Expansion model coupled to the Poisson equation. Kinetic & Related Models, 2011, 4 (4) : 1063-1079. doi: 10.3934/krm.2011.4.1063

[14]

Antonios Zagaris, Christophe Vandekerckhove, C. William Gear, Tasso J. Kaper, Ioannis G. Kevrekidis. Stability and stabilization of the constrained runs schemes for equation-free projection to a slow manifold. Discrete & Continuous Dynamical Systems - A, 2012, 32 (8) : 2759-2803. doi: 10.3934/dcds.2012.32.2759

[15]

Amadeu Delshams, Rodrigo G. Schaefer. Arnold diffusion for a complete family of perturbations with two independent harmonics. Discrete & Continuous Dynamical Systems - A, 2018, 38 (12) : 6047-6072. doi: 10.3934/dcds.2018261

[16]

Mauro Maggioni, James M. Murphy. Learning by active nonlinear diffusion. Foundations of Data Science, 2019, 1 (3) : 271-291. doi: 10.3934/fods.2019012

[17]

Barbara Kaltenbacher, Gunther Peichl. The shape derivative for an optimization problem in lithotripsy. Evolution Equations & Control Theory, 2016, 5 (3) : 399-430. doi: 10.3934/eect.2016011

[18]

Maho Endo, Yuki Kaneko, Yoshio Yamada. Free boundary problem for a reaction-diffusion equation with positive bistable nonlinearity. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3375-3394. doi: 10.3934/dcds.2020033

[19]

Dmitri E. Kvasov, Yaroslav D. Sergeyev. Univariate geometric Lipschitz global optimization algorithms. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 69-90. doi: 10.3934/naco.2012.2.69

[20]

Barbara Brandolini, Carlo Nitsch, Cristina Trombetti. Shape optimization for Monge-Ampère equations via domain derivative. Discrete & Continuous Dynamical Systems - S, 2011, 4 (4) : 825-831. doi: 10.3934/dcdss.2011.4.825

[Back to Top]