Dynamical Systems

Lyapunov Stability Theory

GAN (Goodfellow, 2014). Two networks - generator G and discriminator D - in a minimax game. Training sometimes diverges: mode collapse, oscillation, training instability. Lyapunov theory explains when and why: if no Lyapunov function exists for the dynamics (G, D), there is no convergence guarantee. That is exactly why WGAN reformulated the game - to obtain Lyapunov-compatible dynamics. Lyapunov 1892 predicted the GAN problem one hundred twenty-two years before Goodfellow.

  • **GAN and WGAN:** gradient penalty in WGAN is a Lyapunov condition for game dynamics; the W_1 norm decreases along training as a Lyapunov function
  • **RL convergence:** policy gradient converges if the value function serves as a Lyapunov function; Q-learning is stable under Bellman contraction V_dot < 0
  • **Robotics CLF:** Boston Dynamics uses Control Lyapunov Functions in MPC balance controllers - stability guarantees are embedded in the optimization

Предварительные знания

  • Continuous Dynamical Systems

Lyapunov Function: Generalized Energy

2014. Goodfellow proposes the GAN - generator G versus discriminator D in a minimax game. Early experiments are impressive. Then after a few epochs: collapse. The generator produces the same image repeatedly, the discriminator stops learning, losses oscillate without converging. **Mode collapse. Training instability.** The reason: no Lyapunov function exists for the dynamics (G, D) - no convergence guarantee. Not a code bug. A theorem about the absence of guarantees.

Linearization from the previous lesson breaks down when Re(lambda) = 0 - and says nothing about large deviations. A globally applicable tool is needed. **Lyapunov's idea (1892):** instead of solving the equation, find an 'energy' function - a scalar V(x) that does not grow along trajectories. If the energy decreases, the system settles, regardless of where it started.

0

1

Sign In

A **Lyapunov function** V(x) for the system dx/dt = f(x) with equilibrium x*=0 is a continuously differentiable function satisfying: 1. V(0) = 0 2. V(x) > 0 for x != 0 (positive definiteness) 3. V_dot(x) = nablaV * f(x) <= 0 along trajectories If V_dot <= 0 - Lyapunov stability. If V_dot < 0 strictly - asymptotic stability.

Physical picture: a ball on a bowl surface. V(x) is the height (potential energy). Friction enforces V_dot < 0 - the ball rolls to the bottom. No trajectory calculation needed. Knowing the energy decreases is enough to conclude the ball reaches the bottom. Lyapunov applies this reasoning to dynamical systems of arbitrary dimension.

ConditionWhat it provesML example
V > 0, V_dot <= 0Lyapunov stabilityGradient flow stays near minimum
V > 0, V_dot < 0Asymptotic stabilitySGD converges to minimum from a given basin
V > 0, V_dot > 0Instability (Chetaev's theorem)GAN without Lipschitz constraint - guaranteed divergence

Aleksandr Lyapunov, 1892

The dissertation 'The General Problem of the Stability of Motion' - two hundred fifty-one pages, defended in Kharkiv. Lyapunov worked on the stability of rotating celestial bodies. The method of functions is universal: it does not require solving the equation. Finding a suitable V is sufficient. One hundred twenty-two years before GAN became a problem, Lyapunov formulated exactly the condition GAN was missing.

For the system dx/dt = -x³, the function V(x) = x² is proposed. Compute V_dot and determine the stability type.

Asymptotic Stability and Basin of Attraction

Policy gradient in RL converges - but not always. The convergence condition: the value function V(s) serves as a Lyapunov function for the policy dynamics. If V_dot < 0 strictly along policy updates - the algorithm is asymptotically stable. If V_dot <= 0 - the policy does not diverge, but may cycle. The difference between 'no worse' and 'strictly better' is exactly asymptotic stability.

**Theorem (Lyapunov):** If V(x) exists with V(0)=0, V(x)>0, and **V_dot(x) < 0** strictly for x != 0, then the equilibrium x*=0 is **asymptotically stable**: x(t) -> 0 as t -> inf from any initial condition in some neighborhood. This neighborhood is called the **basin of attraction**. If additionally V(x) -> inf as ||x|| -> inf (radially unbounded), stability is **global** - basin of attraction = the entire state space.

Q-learning is stable when the Bellman equation conditions hold - this is also Lyapunov. The Bellman operator T is a contraction, V(Q) = ||Q - Q*||_inf decreases at each iteration. V_dot < 0 in continuous time. The basin of attraction is the entire Q-value space. Hence the convergence guarantee for tabular Q-learning.

PropertyLyapunov stabilityAsymptotic stability
V_dot conditionV_dot <= 0V_dot < 0 strictly
BehaviorStays in a neighborhoodConverges to x*
Physics exampleFrictionless pendulum (center)Pendulum with friction (focus)
ML exampleSGD with zero LR on a plateauAdam with decay, Q-learning Bellman
For controlNot sufficientMinimum controller requirement

A common mistake: confusing 'V_dot <= 0 everywhere' with 'V_dot < 0 everywhere'. For the pendulum with friction: V_dot = -0.3*omega^2. This is <= 0, but equals 0 on the entire axis omega=0 (not only at the origin). Strict negative definiteness does NOT hold. To prove convergence - LaSalle's principle is needed.

A frictionless pendulum has V_dot = 0. A pendulum with friction has V_dot = -gamma*omega^2 <= 0. What is the essential difference in behavior?

LaSalle's Invariance Principle

WGAN (Arjovsky, 2017) - the answer to GAN instability. Instead of cross-entropy: the Wasserstein distance W_1. Gradient penalty enforces 1-Lipschitz on the discriminator. Mathematically this is not just regularization - it constructs a Lyapunov function for the flow dynamics (G, D). The W_1 norm decreases along the training trajectory. V_dot <= 0 - but not strictly: at points where gradients vanish, V_dot = 0. To prove convergence, LaSalle's principle is exactly what is needed.

**LaSalle's Invariance Principle:** Let V_dot(x) <= 0 in a region Omega. Define S = {x : V_dot(x) = 0} - the set where 'energy' is not decreasing. Let M be the largest invariant subset of S (a trajectory starting in M stays in M forever). Then all trajectories from Omega converge to M. Algorithm: 1. Find V with V_dot <= 0 2. Identify S = {V_dot = 0} 3. Find the largest invariant M in S 4. All trajectories -> M

Intuition: a ball in a bowl with friction. On the axis omega=0 (ball momentarily stopped), friction does nothing. But the ball cannot remain there forever with theta != 0 - gravity restarts the motion. The only place to 'stay forever' is the bowl bottom (0, 0). LaSalle formalizes this physical argument for arbitrary nonlinear systems.

Boston Dynamics uses Control Lyapunov Functions (CLF) in balance controllers. The robot dog must remain upright after a kick - a basin of attraction problem. MPC formulates each step as an optimization with a CLF constraint: V_dot <= -alpha*V. Stability guarantees are baked into the optimization itself - not a heuristic, a theorem.

LaSalle stepActionPendulum with friction
1Find V with V_dot <= 0V = (1-cos theta) + omega^2/2, V_dot = -gamma*omega^2
2Define S = {V_dot = 0}S = {omega=0} - entire theta-axis
3Find invariant M in SM = {(0,0), (pi,0)}
4All trajectories -> MNear (0,0): x(t) -> (0,0)

LaSalle is not a replacement for Lyapunov's theorem - it is an extension. It proves asymptotic stability when V_dot <= 0 (not strict), provided the invariant set M is small enough. Ideal case: M = {x*}. If M is larger, trajectories converge to a set rather than a point (e.g., a limit cycle).

If no Lyapunov function can be found, the system must be unstable

Failure to find a Lyapunov function does not prove instability. A function may exist but be nondirectly structured. The Lyapunov method is a sufficient, not necessary, condition for stability.

No general algorithm exists for constructing V for nonlinear systems. For linear systems: V = x^T P x where P satisfies the Lyapunov equation A^T P + PA = -Q. For nonlinear systems, finding V is itself an optimization problem (SOS programming, neural Lyapunov functions). Stable systems with nontrivial V do exist. Instability is proved separately via Chetaev's theorem.

For some system V_dot = -x₁²(x₁² + x₂²). The set S = {V_dot = 0} = {x₁ = 0}. The only invariant point on the axis x₁ = 0 is the origin. What follows?

Key Takeaways

  • **Lyapunov function V(x) > 0, V_dot <= 0** - generalized energy that does not grow along trajectories; stability without solving the equation
  • **V_dot < 0 strictly** - asymptotic stability, x(t)->0; V_dot <= 0 - Lyapunov stability only (orbits preserved)
  • **Radial unboundedness** V -> inf as ||x|| -> inf gives global stability from any initial point (basin = entire space)
  • **LaSalle:** even with V_dot <= 0, trajectories converge to the largest invariant M in {V_dot=0}; if M = {x*} - asymptotic stability

Related Topics

Lyapunov theory is the central result bridging dynamical systems and control theory:

  • Continuous Dynamical Systems — Linearization is a special case; Lyapunov works where linearization fails (Re(lambda)=0, large deviations)
  • Bifurcations — At the stability boundary (V_dot=0 over a large region), bifurcations arise - phase portrait structure changes
  • Control Theory — CLF is the foundation for designing stabilizing controllers in MPC and robotics

Вопросы для размышления

  • WGAN is not just a trick: the W_1 norm is a Lyapunov function for the flow dynamics (G, D). Gradient penalty creates the V_dot <= 0 condition. Why does a standard GAN correspond to a system without a Lyapunov function - and what does that say about the nature of mode collapse?
  • For linear systems V = x^T P x always exists when the system is stable (P from the Lyapunov equation A^T P + PA = -Q). For nonlinear systems there is no algorithm. How do neural Lyapunov functions attempt to solve this - and why is it an active research area?
  • Boston Dynamics enforces stability via CLF at each MPC step. What happens when the real robot dynamics differ from the model? How robust is Lyapunov theory to model errors?

Связанные уроки

  • dyn-02 — Linearization is the precursor of Lyapunov: works only near equilibrium, not where Lyapunov is required
  • dyn-04 — Bifurcations arise at the stability boundary where V_dot=0 over a large region
  • dyn-08 — CLF - control Lyapunov functions in MPC and robotics
  • de-03 — ODE systems and eigenvalue stability - historical context of the method
  • cvx-01 — Convex functions are Lyapunov candidates for gradient flow optimization
  • de-01
  • la-13-eigenvectors
Lyapunov Stability Theory