ABSTRACT:
Weakly connected Markov processes are used to model stochastic dynamics across different scales. They are widely used in electrical engineering, finance and molecular dynamics simulations. In many of these applications it is becoming increasingly important to both efficiently simulate these processes as well as to control them. Classical algorithms for the control of Markov Processes cannot be directly applied to weakly connected Markov processes. The problem with existing approaches is that they exhibit an extremely slow convergence rate due to the existence of multiscale effects. We show why existing algorithms are slow, and propose a new class of algorithms with more favourable convergence properties and computational complexity. In our approach we use spectral graph theory to derive a hierarchy of models that are valid at different resolutions. We then propose a polynomial time algorithm that uses the finest resolution model only when required. The rate of convergence of the algorithm is discussed as well as its complexity.
ADDITIONAL INFORMATION:
Panos’ interests are in the development and analysis of quantitative optimization models under uncertainty. Stochastic optimization models are used in many areas such as economics, finance, engineering, and energy systems. Realistic models have a large number of variables, and multiple interactions across time and space. Advanced computational methods, and analytical approximations that take advantage of problem structure are needed in order to analyze realistic models. Panos works on the development of computational methods and applications.
http://www.doc.ic.ac.uk/~pp500/