  


On the Difficulty of Deciding Asymptotic Stability of Cubic Homogeneous Vector Fields
Amir Ali Ahmadi(a_a_amit.edu) Abstract: It is wellknown that asymptotic stability (AS) of homogeneous polynomial vector fields of degree one (i.e., linear systems) can be decided in polynomial time e.g. by searching for a quadratic Lyapunov function. Since homogeneous vector fields of even degree can never be AS, the next interesting degree to consider is equal to three. In this paper, we prove that deciding AS of homogeneous cubic vector fields is strongly NPhard and pose the question of determining whether it is even decidable. As a byproduct of the reduction that establishes our NPhardness result, we obtain a Lyapunovinspired technique for proving positivity of forms. We also show that for asymptotically stable homogeneous cubic vector fields in as few as two variables, the minimum degree of a polynomial Lyapunov function can be arbitrarily large. Finally, we show that there is no monotonicity in the degree of polynomial Lyapunov functions that prove AS; i.e., a homogeneous cubic vector field with no homogeneous polynomial Lyapunov function of some degree $d$ can very well have a homogeneous polynomial Lyapunov function of degree less than $d$. Keywords: complexity of deciding stability, differential equations, polynomial and sum of squares Lyapunov functions Category 1: Nonlinear Optimization (Systems governed by Differential Equations Optimization ) Category 2: Applications  Science and Engineering (Control Applications ) Category 3: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Citation: Submitted for publication. Download: [PDF] Entry Submitted: 12/04/2011 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  