Why are Lyapunov functions always quadratic?
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:
$\endgroup$ 1Why is the proposed Lyapunov function in these systems always quadratic?
2 Answers
$\begingroup$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.
$\endgroup$ 8 $\begingroup$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.
$\endgroup$
