Raphael M. Jungers

Julien M. Hendrickx, Karl Henrik Johansson, Raphael M. Jungers et al.

The resilience of Supervisory Control and Data Acquisition (SCADA) systems for electric power networks for certain cyber-attacks is considered. We analyze the vulnerability of the measurement system to false data attack on communicated measurements. The vulnerability analysis problem is shown to be NP-hard, meaning that unless $P = NP$ there is no polynomial time algorithm to analyze the vulnerability of the system. Nevertheless, we identify situations, such as the full measurement case, where it can be solved efficiently. In such cases, we show indeed that the problem can be cast as a generalization of the minimum cut problem involving costly nodes. We further show that it can be reformulated as a standard minimum cut problem (without costly nodes) on a modified graph of proportional size. An important consequence of this result is that our approach provides the first exact efficient algorithm for the vulnerability analysis problem under the full measurement assumption. Furthermore, our approach also provides an efficient heuristic algorithm for the general NP-hard problem. Our results are illustrated by numerical studies on benchmark systems including the IEEE 118-bus system.

Amir Ali Ahmadi, Raphael M. Jungers, Pablo A. Parrilo et al.

We study stability criteria for discrete time switching systems. We investigate the structure of sets of LMIs that are a sufficient condition for stability (i.e., such that any switching system which satisfies these LMIs is stable). We provide an exact characterization of these sets. As a corollary, we show that it is PSPACE-complete to recognize whether a particular set of LMIs implies the stability of a switching system.

Fulvio Forni, Raphael M. Jungers, Rodolphe Sepulchre

The notion of path-complete positivity is introduced as a way to generalize the property of positivity from one LTI system to a family of switched LTI systems whose switching rule is constrained by a finite automaton. The generalization builds upon the analogy between stability and positivity, the former referring to the contraction of a norm, the latter referring to the contraction of a cone (or, equivalently, a projective norm). We motivate and investigate the potential of path-positivity and we propose an algorithm for the automatic verification of positivity.

Raphael M. Jungers, Alessandro D'Innocenzo, Maria D. Di Benedetto

We analyze a classification of two main families of controllers that are of interest when the feedback loop is subject to switching propagation delays due to routing via a wireless multi-hop communication network. We show that we can cast this problem as a subclass of classical switching systems, which is a non-trivial generalization of classical LTI systems with timevarying delays. We consider both cases where delay-dependent and delay independent controllers are used, and show that both can be modeled as switching systems with unconstrained switchings. We provide NP-hardness results for the stability verification problem, and propose a general methodology for approximate stability analysis with arbitrary precision. We finally give evidence that non-trivial design problems arise for which new algorithmic methods are needed.

Amir Ali Ahmadi, Raphael M. Jungers

We introduce the concept of sos-convex Lyapunov functions for stability analysis of both linear and nonlinear difference inclusions (also known as discrete-time switched systems). These are polynomial Lyapunov functions that have an algebraic certificate of convexity and that can be efficiently found via semidefinite programming. We prove that sos-convex Lyapunov functions are universal (i.e., necessary and sufficient) for stability analysis of switched linear systems. We show via an explicit example however that the minimum degree of a convex polynomial Lyapunov function can be arbitrarily higher than a non-convex polynomial Lyapunov function. In the case of switched nonlinear systems, we prove that existence of a common non-convex Lyapunov function does not imply stability, but existence of a common convex Lyapunov function does. We then provide a semidefinite programming-based procedure for computing a full-dimensional subset of the region of attraction of equilibrium points of switched polynomial systems, under the condition that their linearization be stable. We conclude by showing that our semidefinite program can be extended to search for Lyapunov functions that are pointwise maxima of sos-convex polynomials.

Vladimir Yu. Protasov, Raphael M. Jungers

We introduce a new approach to evaluate the largest Lyapunov exponent of a family of nonnegative matrices. The method is based on using special positive homogeneous functionals on $R^{d}_+,$ which gives iterative lower and upper bounds for the Lyapunov exponent. They improve previously known bounds and converge to the real value. The rate of convergence is estimated and the efficiency of the algorithm is demonstrated on several problems from applications (in functional analysis, combinatorics, and lan- guage theory) and on numerical examples with randomly generated matrices. The method computes the Lyapunov exponent with a prescribed accuracy in relatively high dimensions (up to 60). We generalize this approach to all matrices, not necessar- ily nonnegative, derive a new universal upper bound for the Lyapunov exponent, and show that such a lower bound, in general, does not exist.

Raphael M. Jungers, Nicola Guglielmi, Antonio Cicone

We describe new methods for deciding the stability of switching systems. The methods build on two ideas previously appeared in the literature: the polytope norm iterative construction, and the lifting procedure. Moreover, the combination of these two ideas allows us to introduce a pruning algorithm which can importantly reduce the computational burden. We prove several appealing theoretical properties of our methods like a finiteness computational result which extends a known result for unlifted sets of matrices, and provide numerical examples of their good behaviour.

Nikolaos Athanasopoulos, Konstantinos Smpoukis, Raphael M. Jungers

We study discrete time linear constrained switching systems with additive disturbances, in which the switching may be on the system matrices, the disturbance sets, the state constraint sets or a combination of the above. In our general setting, a switching sequence is admissible if it is accepted by an automaton. For this family of systems, stability does not necessarily imply the existence of an invariant set. Nevertheless, it does imply the existence of an invariant multi-set, which is a relaxation of invariance and the object of our work. First, we establish basic results concerning the characterization, approximation and computation of the minimal and the maximal admissible invariant multi-set. Second, by exploiting the topological properties of the directed graph which defines the switching constraints, we propose invariant multi-set constructions with several benefits. We illustrate our results in benchmark problems in control.