Departmental Colloquium
Jerzy Filar
University of South Australia
Hamiltonian Cycles, Critical Parameters and Gröbner Bases
Abstract: Solutions of many of most important mathematical problems depend
on values of one or more parameters. Sometimes, values of these
parameters are known rather precisely, sometimes they are only
rough estimates of true values and, interestingly, there are also
important situations where previously ``missing" parameters can be
inserted into a problem to aid its analysis. Furthermore, there
are often situations when configurations of two or more parameters
arise where the nature of solutions to the original problem
changes qualitatively at these precise critical
configurations. This presentation outlines two, seemingly
separate, lines of research that are nonetheless connected by the
underlying approach that focuses on the importance of
understanding the behaviour of solutions to problems in
neighbourhoods of critical values of parameters.
The first line considers the classical (NP-hard) problem of
determining whether a given graph possesses a Hamiltonian cycle.
Exploiting singularly perturbed controlled Markov chains and their
fundamental matrices we reduce the problem to that of minimising
the variability of the ``first return time" to the home node. The
latter is a highly structured, non-convex, optimisation problem
whose properties shed light on both the theoretical complexity of
the problem and its algorithmic tractability. A recent innovation
in this approach is the restriction to doubly stochastic Markov
chains.
The second line considers a perturbed mathematical programming
problem where both the objective and the constraint functions are
polynomial in all underlying decision variables and in the
perturbation parameter $\varepsilon.$ We study the behaviour of
the solutions of such a perturbed problem as $\varepsilon
\rightarrow 0.$ Though the solutions of mathematical programming
problems are real, we consider the Kuhn-Tucker optimality system
as a $1-$dimensional complex algebraic variety in a
multi-dimensional complex space. We then use Buchberger's
elimination algorithm of the Gröbner bases theory to replace the
defining equations of the variety by its Gröbner basis, that has
the property that one of its elements is bivariate, that is, a
polynomial in $\varepsilon$ and only one of the decision
variables.
We conclude by speculating that the above algebraic reduction
procedure lends itself to the identification of critical
parameter configurations in a wide range of mathematical models
describing interactions between natural and human development
processes.
Friday September 11, 2009 at 3:00 PM in SEO 636