  In this paper, we propose a new convex approach to stability analysis of
nonlinear systems with polynomial vector fields. First, we consider an
arbitrary convex polytope that contains the equilibrium in its interior. Then,
we decompose the polytope into several convex sub-polytopes with a common
vertex at the equilibrium. Then, by using Handelman's theorem, we derive a new
set of affine feasibility conditions -solvable by linear programming- on each
sub-polytope. Any solution to this feasibility problem yields a piecewise
polynomial Lyapunov function on the entire polytope. This is the first result
which utilizes Handelman's theorem and decomposition to construct piecewise
polynomial Lyapunov functions on arbitrary polytopes. In a computational
complexity analysis, we show that for large number of states and large degrees
of the Lyapunov function, the complexity of the proposed feasibility problem is
less than the complexity of certain semi-definite programs associated with
alternative methods based on Sum-of-Squares or Polya's theorem. Using different
types of convex polytopes, we assess the accuracy of the algorithm in
estimating the region of attraction of the equilibrium point of the
reverse-time Van Der Pol oscillator.
