Linear Differential Inclusions for Computational Contraction Theory

Contraction Workshop @ CDC 2024

Akash Harapanahalli, Samuel Coogan

School of Electrical and Computer Engineering, Georgia Institute of Technology

December 15, 2024

An LDI Perspective to Contraction Analysis (Part 1)

%

A linear differential inclusion (LDI) is of the form \[ \dot{x} \in \Omega x, \quad x(0) = x_0, \] where \(x\in\mathbb{R}^n\), \(\Omega\subseteq\mathbb{R}^{n\times n}\) is a set of matrices.

Proposition 1 (Exponential Stability of LDIs [1])

If there exists \(c\in\mathbb{R}\) such that \(\mu(A) \leq c\) for every \(A\in\Omega\), then \[ |x(t)| \leq e^{ct} |x(0)| \] for any trajectory \(t\mapsto x(t)\) of the LDI.

[1] C. Desoer and M. Vidyasagar, Feedback systems: Input-output properties. SIAM, 1975.

An LDI Perspective to Contraction Analysis (Part 2)

Consider some differentiable function \(f:\mathbb{R}^n\to\mathbb{R}^m\).

Proposition 2 (Jacobian Linear Inclusion [2])

If \(\{\frac{\partial f}{\partial x}(x) : x\in\mathbb{R}^n\} \subseteq \mathcal{J}\), then for any \(x,x'\in\mathbb{R}^n\). \[ f(x) - f(x') \in \overline{\operatorname{co}}(\mathcal{J}) (x - x'). \]

Intuition: Apply mean value theorem to the line segment connecting \(x\) and \(x'\)

[2] S. Boyd, L. E. Ghaoui, E. Feron, and V. Balakrishnan, Linear matrix inequalities in system and control theory. SIAM, 1994.

An LDI Perspective to Contraction Analysis (Part 3)

Consider \(\dot{x} = f(x)\) for \(C^1\) smooth \(f\). Set \(\varepsilon = x - x'\).

Proposition 2: \(\dot{\varepsilon} = f(x) - f(x') \in \overline{\operatorname{co}}(\mathcal{J}) (x - x') = \overline{\operatorname{co}}(\mathcal{J}) \varepsilon\)

Proposition 1 + Convexity: \(\sup_{J\in\mathcal{J}} \mu(J) \leq c \implies |\varepsilon(t)| \leq e^{ct}|\varepsilon(0)|\)

Result is the usual norm bound. For any two trajectories \(t\mapsto x(t),x'(t)\), \[ |x(t) - x'(t)| \leq e^{ct} |x(0) - x'(0)| \]

• [3], [4]: Fundamental Theorem + Coppel + Gronwall yields the result using sub-additivity of \(\mu\), integrating the line segment connecting \(x\) and \(x'\): \[ f(x) - f(x') = \left(\smallint_0^1 Df(sx(t) + (1-s)x'(t)) \ \mathrm{d}s \right) (x - x'). \]

[3] Z. Aminzare and E. D. Sontag, “Contraction methods for nonlinear systems: A brief introduction and some open problems,” IEEE CDC, 2014.
[4] A. Davydov, S. Jafarpour, and F. Bullo, “Non-euclidean contraction theory for robust nonlinear stability,” IEEE TAC, 2022.

Why is this Equivalent Viewpoint Useful?

Theoretical Infinitesimal Linearization (closed-form) \(\iff\) Computational Error LDI Analysis (set)

Computational Advantage: Automatic, parallelizable and differentiable constructions of overapproximating interval Jacobian sets using modern tools: automatic differentiation and interval analysis [5]

import immrax as irx
import jax.numpy as jnp

f = lambda x : jnp.array([x[0]**2, x[1]**3 + jnp.sin(x[0])]) # Dynamics
J = irx.jacM(f) # autodiff + interval analysis
print(J(irx.interval([-1., -1.], [1., 1.]))) # Interval Overapprox of Jacobian

Can apply any strategy from LDI analysis [2], including LMI-based control design.

Example: Stable feedback control design on error LDI \(\implies\) contracting feedback tracking control

[5] A. Harapanahalli, S. Jafarpour, and S. Coogan, “immrax: A parallelizable and differentiable toolbox for interval analysis and mixed monotone reachability in JAX,” IFAC ADHS, 2024
[2] S. Boyd, L. E. Ghaoui, E. Feron, and V. Balakrishnan, Linear matrix inequalities in system and control theory. SIAM, 1994.

Mixed Jacobian LDI: Contraction to Known Trajectories [6]

In many applications, a nominal trajectory is fixed: reachable set computation, tracking control design, training, etc.
An elementwise application of the mean value theorem obtains a different inclusion: potential improvement for fixed \(x'\).

Mixed Jacobian LDI

Fixing a point \(x'\in\mathbb{R}^n\), an element-wise application of mean value yields \[ \begin{gather*} \begin{aligned} (M_{x'}f& (x, s))_{ij} \\ &:= \frac{\partial f_i}{\partial x_j} (x_1,\dots,x_{j-1},s_jx_j + (1-s_j)x'_j,x'_{j+1},\dots,x'_n) \end{aligned} \\ M_{x'}f(\mathbb{R}^n,[0,1]^n) \subseteq \mathcal{M}\implies f(x) - f(x') \in \overline{\operatorname{co}}(\mathcal{M}) (x - x'), % |x(t) - x'(t)| \leq e^{ct} |x_0 - x'_0| \end{gather*} \] for any \(x\in\mathbb{R}^n\).

Proposition 1 + Convexity: \(\sup_{M\in\mathcal{M}} \mu(M) \leq c \implies |\varepsilon(t)| \leq e^{ct}|\varepsilon(0)|\)

[6] A. Harapanahalli, and S. Coogan, “A linear differential inclusion for contraction analysis to known trajectories,” arXiv preprint, 2024

Application: Reachable Sets Using Matrix Measures

Reachable Set Computation: [7] Simulate nominal \(t\mapsto x'\), upper bound logarithmic norm around \(x'\), bloat/shrink a norm ball.

Interval Overapproximations: [8] Use interval overapproximations of the Jacobian to overapproximate logarithmic norm.

Automated: immrax automatically computes interval \([\mathcal{M}]\) matrices, SDP searches for \(\|\cdot\|_{2,P^{1/2}}\) norms.

Novelty: Compare directly to \(x'\), not arbitrary trajectories. Strict Improvement: \([\mathcal{M}]\subseteq[\mathcal{J}]\)

\(4\) state robot arm model, projection onto \(q_1\)-\(q_2\) pictured

[7] J. Maidens and M. Arcak, “Reachability analysis of nonlinear systems using matrix measures,” IEEE TAC, 2014.
[8] C. Fan, J. Kapinski, X. Jin, and S. Mitra, “Simulation-driven reachability using matrix measures,” ACM TECS, vol. 17, no. 1, pp. 1–28, 2017.

Conclusions

• An LDI encompassing the error dynamics recovers the norm-based matrix measure contraction bound
• When comparing to a known trajectory of the system, the mixed Jacobian LDI potentially provides better results compared to using the normal Jacobian set

For all the details, please see the preprint

https://arxiv.org/pdf/2411.11587

Thank you for your attention!
Presenting “Efficient Reachable Sets on Lie Groups Using Lie Algebra Monotonicity and Tangent Intervals” tomorrow:
MoA20.2, 10:20 - 10:40, Suite 9

References

[1]

C. Desoer and M. Vidyasagar, Feedback systems: Input-output properties. Society for Industrial; Applied Mathematics, 1975.

[2]

S. Boyd, L. E. Ghaoui, E. Feron, and V. Balakrishnan, Linear matrix inequalities in system and control theory. SIAM, 1994.

[3]

Z. Aminzare and E. D. Sontag, “Contraction methods for nonlinear systems: A brief introduction and some open problems,” in 53rd IEEE conference on decision and control, IEEE, 2014, pp. 3835–3847.

[4]

A. Davydov, S. Jafarpour, and F. Bullo, “Non-euclidean contraction theory for robust nonlinear stability,” IEEE Transactions on Automatic Control, vol. 67, no. 12, pp. 6667–6681, 2022.

[5]

A. Harapanahalli, S. Jafarpour, and S. Coogan, “Immrax: A parallelizable and differentiable toolbox for interval analysis and mixed monotone reachability in JAX,” IFAC-PapersOnLine, vol. 58, no. 11, pp. 75–80, 2024, doi: https://doi.org/10.1016/j.ifacol.2024.07.428. Available: https://www.sciencedirect.com/science/article/pii/S2405896324005275

[6]

A. Harapanahalli and S. Coogan, “A linear differential inclusion for contraction analysis to known trajectories.” 2024. Available: https://arxiv.org/abs/2411.11587

[7]

J. Maidens and M. Arcak, “Reachability analysis of nonlinear systems using matrix measures,” IEEE Transactions on Automatic Control, vol. 60, no. 1, pp. 265–270, 2014.

[8]

C. Fan, J. Kapinski, X. Jin, and S. Mitra, “Simulation-driven reachability using matrix measures,” ACM Transactions on Embedded Computing Systems (TECS), vol. 17, no. 1, pp. 1–28, 2017.