TY - GEN

T1 - On the difficulty of deciding asymptotic stability of cubic homogeneous vector fields

AU - Ahmadi, Amir Ali

PY - 2012/11/26

Y1 - 2012/11/26

N2 - It is well-known 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 NP-hard and pose the question of determining whether it is even decidable. As a byproduct of the reduction that establishes our NP-hardness result, we obtain a Lyapunov-inspired 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.

AB - It is well-known 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 NP-hard and pose the question of determining whether it is even decidable. As a byproduct of the reduction that establishes our NP-hardness result, we obtain a Lyapunov-inspired 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.

UR - http://www.scopus.com/inward/record.url?scp=84869408750&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84869408750&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84869408750

SN - 9781457710957

T3 - Proceedings of the American Control Conference

SP - 3334

EP - 3339

BT - 2012 American Control Conference, ACC 2012

T2 - 2012 American Control Conference, ACC 2012

Y2 - 27 June 2012 through 29 June 2012

ER -