Theory of stability regions for a class of nonhyperbolic dynamical systems and its application to constraint satisfaction problems

Abstract

The concept of a stability region (region of attraction) of nonlinear dynamical systems is widely applied in many fields such as engineering and the sciences. In this paper, we develop a comprehensive theory of the stability region and its boundary for a class of nonhyperbolic dynamical systems. We then apply the theory to develop an effective method for solving constraint satisfaction problems. Several necessary and sufficient conditions for an equilibrium manifold (the generalized concept of an equilibrium point) to lie on the stability boundary of the class of nonhyperbolic dynamical systems are derived. The stability boundary of such nonhyperbolic dynamical systems is completely characterized and shown to consist of the union of the stable manifolds of the equilibrium manifolds on the stability boundary. An effective scheme to estimate the stability region of such a dynamical system by using an energy function is developed. These analytical results are then applied to the development of computational methods to systematically find feasible regions of constraint satisfaction problems. Several numerical examples are given to illustrate the effectiveness of the computational method.