Stochastic Systems Seminar
Abstract:
This presentation is devoted to certain contemporary developments in the area of Singular Perturbations, Stochastics, and Optimisation. We refer to the developments where
novel stochastic techniques have been developed to tackle difficult deterministic problems
and conversely. Often these techniques evolved from consideration of problems that exhibit
discontinuous asymptotic behaviour as one or more parameters tend to zero; the so-called
"singular perturbations." The use of stochastic methods to tackle deterministic control problems was pioneered by H. Kushner and P. Dupuis.
We apply a philosophically similar approach to certain, notoriously hard, problems of
discrete mathematics - such as the Hamiltonian Cycle and the Traveling Salesman Problems.
Namely, we map these problems into convex domains where continuum analysis can be
carried out. The convexification of domains underpinning the reported results is achieved by
assigning probabilistic interpretation to key elements of the original deterministic problems.
The topic has now evolved to the point where there are many, both theoretical and algorithmic, results that exploit the nexus between graph theoretic structures and both probabilistic and algebraic entities of related Markov chains. These include moments of first return
times, limiting frequencies of visits to nodes, or the spectra of certain matrices traditionally
associated with the analysis of Markov chains. There are also interesting connections with
singular perturbation theory of mathematical programs that can be tackled with the help of
an algebraic construct known as "Grobner basis" that can help decouple decision variables of
an algebraic variety defined by optimality conditions of a polynomial mathematical program.
Buchberger's computational algorithm can be used to compute such a basis.