Algebraic structure and stochastic complexity of Hex game model of robust stability algorithms

Although Kharitonov's theorem provides a simple criterion for a class of systems, checking robust stability is in general not an easy task. In this dissertation, we consider the more general problem of locating the stability boundary in the space of uncertain parameters. The approximate stability crossover region can be searched and locked on by applying concepts borrowed from simplicial algorithms and the game of Hex.; The three basic constitutive components of simplicial algorithms are triangulation, labelling rule, and searching completely labelled simplexes, thereby providing a piecewise linear approximation of the crossover. The objective of this dissertation is to identify the reflection invariance properties of regular pattern triangulation of the space of uncertain parameters. The vertices of the triangulation of the n-D space of parameters form a lattice, which in case of the popular Q-triangulation of operations research is shown to be the {dollar}Asb{lcub}n{rcub}{dollar}-lattice. The vectors orthogonal to the planes of reflection invariance of the lattice are the roots of the real {dollar}Asb{lcub}n{rcub}{dollar} Lie algebra, a representation of which is sl(n + 1, {dollar}IR{dollar}). Further insight into the symmetric properties of the n-D Q-triangulation is gained by taking its graph theoretical dual which is shown to be the n-D Hex game board. The Voronoi cells of the lattice points of Q-triangulation in three dimensional space are shown to be rhombic dodecahedra. Using the lattice points of the n-D Q-triangulation as centers of spheres yields the {dollar}Asb{lcub}n{rcub}{dollar} sphere packing.; With the help afforded by the algebraization of geometric concepts, bounded flatness of the Q-triangulation is proved. The flatness issue is crucial for good accuracy of simplicial algorithms.; Monte Carlo simulations for evaluating stochastic complexity of robust stability algorithms via their Hex game models are also developed. The average complexity turns out to be much lower than the worst case complexity in searching winning paths in two and three dimensional Hex games.