Why are Lyapunov functions always quadratic?

Question

Consider stable linear system $\dot x= Ax + Bu$. We’ll show that the Lyapunov bound is tight with $V (z) = z^T W^{−1}z$. Multiply $AW_c + W_c A^T + B B^T = 0$ on left & right by ${W_c}^{−1}$ to get

$${W_c}^{−1}A + A^T {W_c}^{−1} + {W_c}^{−1}BB^T {W_c}^{−1} = 0$$

now we can find and bound $V$

$$V (z,w) \leq w^Tw$$

My question is:

Why is the proposed Lyapunov function in these systems always quadratic?

Answer 1

I feel the original question of why quadratic Lyapunov functions always work in the stable linear case has not been answered.

Building on the above we need to find $P>0$ such that ${A^T}P + PA + Q = 0$ holds for $Q>0$. Since we know that the state transition matrix for linear systems has the form $e^{At}$ and we are looking at $V=x^TPx $ let,

$$ P = \int_0^\infty {{e^{{A^T}t}}Q{e^{At}}dt} = \int_0^\infty {F\left( t \right)dt} $$

Then,

$$ {x^T}Px = \int_0^\infty {x{{\left( t \right)}^T}Qx\left( t \right)dt} $$

Observe,

$$ \dot F\left( t \right) = {A^T}{e^{{A^T}t}}Q{e^{At}} + {e^{{A^T}t}}Q{e^{At}}A = {A^T}F\left( t \right) + F\left( t \right)A $$

And by the fundamental theorem of calculus,

$$ F\left( s \right) - F\left( 0 \right) = \int_0^s {\dot F\left( t \right)dt} = {A^T}\left( {\int_0^s {F\left( t \right)dt} } \right) + \left( {\int_0^s {F\left( t \right)dt} } \right)A $$

Also, note $ F\left( 0 \right) = Q $ and as $ s \to \infty $ we have $F\left( s \right) \to 0$ and so in the limit, $\int_0^s {F\left( t \right)dt} \to P$ and the Lyapunov equation is satisfied.

Answer 2

Suppose we have a linear dynamical system of the form

$$\mathrm{\dot x} = \mathrm A \mathrm x$$

We want to search for quadratic Lyapunov functions of the form

$$V (\mathrm x) := \mathrm x^T \mathrm P \mathrm x$$

where $\mathrm P = \mathrm P^T \succ \mathrm O_n$. The Lie derivative along the flow of the dynamical system is

$$\dot V (\mathrm x) = \mathrm x^T (\mathrm A^T \mathrm P + \mathrm P \mathrm A) \mathrm x$$

We want $V$ to be positive definite and $\dot V$ to be negative definite. Hence, we obtain the following linear matrix inequalities (LMIs) in $\mathrm P$

$$\mathrm P \succ \mathrm O_n \qquad \qquad \mathrm A^T \mathrm P + \mathrm P \mathrm A \prec \mathrm O_n$$

which can be solved efficiently using semidefinite programming (SDP). Alternatively, one can efficiently solve Lyapunov matrix equations of the form

$$\mathrm A^T \mathrm P + \mathrm P \mathrm A + \mathrm Q = \mathrm O_n$$

where $\mathrm Q = \mathrm Q^T \succ \mathrm O_n$. Either way, finding $\mathrm P$ is computationally cheap.

Note that the level sets of quadratic Lyapunov functions are ellipsoids, which are arguably the simplest convex sets. A centered ellipsoid in $\mathbb R^n$ can be described using only

$$\binom{n+1}{2} + 1$$

parameters. By contrast, a convex polytope in $\mathbb R^n$ can be described by an arbitrarily large number of linear inequalities. There is no upper bound on the descriptive complexity of a convex polytope.

To summarize, linear dynamical systems have quadratic Lyapunov functions of low descriptive complexity that can be computed easily and quickly. This is indeed a blessing, as most dynamical systems do not allow us to find Lyapunov functions at a low computational cost.