Joint Spectral Radius (JSR)

struct ScaledHybridSystem{T, H <: Union{DiscreteSwitchedLinearSystem, ConstrainedDiscreteSwitchedLinearSystem}} <: HybridSystems.AbstractHybridSystem
    system::H
    γ::T
end

Discrete-time system where each reset map is scaled by γ, that is, the reset map x ↦ Ax of system is replaced by x ↦ Ax/γ.

gripenberg(s::AbstractDiscreteSwitchedSystem; δ=1e-2,
                max_eval = 10000, max_ρ_eval = max_eval,
                max_norm_eval = max_eval, max_length = 50,
                matrix_norm = A -> opnorm(A, 2), verbose = 1)

Gripenberg algorithm [G96] for computing an upper bound ub and a lower bound lb to the Joint Spectral Radius such that ub - lb ≤ 1e-2.

[G96] Gripenberg, G. Computing the joint spectral radius. Linear Algebra and its Applications, Elsevier, 1996, 234, 43-60

soslyap(s::AbstractSwitchedSystem, d; optimizer_constructor=nothing)

Find Sum-of-Squares Lyapunov functions; i.e. solves [(5), PJ08] or gives moment matrices certifying the infeasibility of the problem. Use ScaledHybridSystem to use a different growth rate than 1.

[PJ08] P. Parrilo and A. Jadbabaie. Approximation of the joint spectral radius using sum of squares. Linear Algebra and its Applications, Elsevier, 2008, 428, 2385-2402

soslyapbs(s::AbstractSwitchedSystem, d::Integer,
          soslb, dual,
          sosub, primal;
          verbose=0, tol=1e-5, step=0.5, scaling=quickub(s),
          ranktols=tol, disttols=tol, kws...)

Find the smallest γ such that soslyap is feasible.

sosbuildsequence(s::AbstractSwitchedSystem, d::Integer;
                 v_0=:Random, p_0=:Random, l::Integer=1,
                 Δt::Float64=1., niter::Integer=42,
                 kws...)

Compute the truncation of length l of the high growth rate infinite sequence produced by the algorithm introduced in [LJP17]. The trajectory ends at mode v_0 (or a random one if v_0 is :Random) and is built backward as explained in [LJP17]. The measures used to guide the construction are the infeasibility certificates of highest growth rate computed by soslyap with polynomials of degree 2d. The starting polynomial is either p_0, or a random strictly sum-of-squares polynomial if p_0 is :Random or the primal solution of soslyap certifying the best upper bound for mode v_0.

• [LJP17] B. Legat, R. M. Jungers, and P. A. Parrilo.

Certifying unstability of Switched Systems using Sum of Squares Programming, arXiv preprint arXiv:1710.01814, 2017.

findsmp(seq::HybridSystems.DiscreteSwitchingSequence)

Extract the cycle of highest growth rate in the sequence seq.

sosextractcycle(s::AbstractDiscreteSwitchedSystem, dual, d::Integer;
                ranktols=1e-5, disttols=1e-5)

Extract cycles of high growth rate from atomic occupation measures given by the infeasibility certificates of highest growth rate computed by soslyap. The method is detailed in [LJP17].

• [LJP17] B. Legat, R. M. Jungers, and P. A. Parrilo.

Certifying unstability of Switched Systems using Sum of Squares Programming, arXiv preprint arXiv:1710.01814, 2017.