Search

We study the safety verification problem for discrete-time stochastic systems. We propose an approach for safety verification termed set-erosion strategy that verifies the safety of a stochastic system on a safe set through the safety of its associated deterministic system on an eroded subset. The amount of erosion is captured by the probabilistic bound on the distance between stochastic trajectories and their associated deterministic counterpart. Building on our recent work [1], we establish a sharp probabilistic bound on this distance. Combining this bound with the set-erosion strategy, we establish a general framework for the safety verification of stochastic systems. Our method is flexible and can work effectively with any deterministic safety verification techniques. We exemplify our method by incorporating barrier functions designed for deterministic safety verification, obtaining barrier certificates much tighter than existing results. Numerical experiments are conducted to demonstrate the efficacy and superiority of our method.

In this paper we study the reachability problem for discrete-time nonlinear stochastic systems. Our goal is to present a unified framework for calculating the probabilistic reachable set of discrete-time systems in the presence of both deterministic input and stochastic noise. By adopting a suitable separation strategy, the probabilistic reachable set is decoupled into a deterministic reachable set and the effect of the stochastic noise. To capture the effect of the stochastic noise, in particular sub-Gaussian noise, we provide a probabilistic bound on the distance between a stochastic trajectory and its deterministic counterpart. The key to our approach is a novel energy function called the Averaged Moment Generating Function, which we leverage to provide a high probability bound on this distance. We show that this probabilistic bound is tight for a large class of discrete-time nonlinear stochastic systems and is exact for linear stochastic dynamics. By combining this tight probabilistic bound with the existing methods for deterministic reachability analysis, we propose a flexible framework that can efficiently compute probabilistic reachable sets of stochastic systems. We also provide two case studies for applying our framework to Lipschitz bound reachability and interval-based reachability. Three numerical experiments are conducted to validate the theoretical results., Comment: arXiv admin note: text overlap with arXiv:2407.12225

We address the reachability problem for continuous-time stochastic dynamic systems. Our objective is to present a unified framework that characterizes the reachable set of a dynamic system in the presence of both stochastic disturbances and deterministic inputs. To achieve this, we devise a strategy that effectively decouples the effects of deterministic inputs and stochastic disturbances on the reachable sets of the system. For the deterministic part, many existing methods can capture the deterministic reachability. As for the stochastic disturbances, we introduce a novel technique that probabilistically bounds the difference between a stochastic trajectory and its deterministic counterpart. The key to our approach is introducing a novel energy function termed the Averaged Moment Generating Function that yields a high probability bound for this difference. This bound is tight and exact for linear stochastic dynamics and applicable to a large class of nonlinear stochastic dynamics. By combining our innovative technique with existing methods for deterministic reachability analysis, we can compute estimations of reachable sets that surpass those obtained with current approaches for stochastic reachability analysis. We validate the effectiveness of our framework through various numerical experiments. Beyond its immediate applications in reachability analysis, our methodology is poised to have profound implications in the broader analysis and control of stochastic systems. It opens avenues for enhanced understanding and manipulation of complex stochastic dynamics, presenting opportunities for advancements in related fields.

We present an implementation of interval analysis and mixed monotone interval reachability analysis as function transforms in Python, fully composable with the computational framework JAX. The resulting toolbox inherits several key features from JAX, including computational efficiency through Just-In-Time Compilation, GPU acceleration for quick parallelized computations, and Automatic Differentiability. We demonstrate the toolbox's performance on several case studies, including a reachability problem on a vehicle model controlled by a neural network, and a robust closed-loop optimal control problem for a swinging pendulum.

Interval Markov decision processes are a class of Markov models where the transition probabilities between the states belong to intervals. In this paper, we study the problem of efficient estimation of the optimal policies in Interval Markov Decision Processes (IMDPs) with continuous action-space. Given an IMDP, we show that the pessimistic (resp. the optimistic) value iterations, i.e., the value iterations under the assumption of a competitive adversary (resp. cooperative agent), are monotone dynamical systems and are contracting with respect to the $\ell_{\infty}$-norm. Inspired by this dynamical system viewpoint, we introduce another IMDP, called the action-space relaxation IMDP. We show that the action-space relaxation IMDP has two key features: (i) its optimal value is an upper bound for the optimal value of the original IMDP, and (ii) its value iterations can be efficiently solved using tools and techniques from convex optimization. We then consider the policy optimization problems at each step of the value iterations as a feedback controller of the value function. Using this system-theoretic perspective, we propose an iteration-distributed implementation of the value iterations for approximating the optimal value of the action-space relaxation IMDP.

We present a framework based on interval analysis and monotone systems theory to certify and search for forward invariant sets in nonlinear systems with neural network controllers. The framework (i) constructs localized first-order inclusion functions for the closed-loop system using Jacobian bounds and existing neural network verification tools; (ii) builds a dynamical embedding system where its evaluation along a single trajectory directly corresponds with a nested family of hyper-rectangles provably converging to an attractive set of the original system; (iii) utilizes linear transformations to build families of nested paralleletopes with the same properties. The framework is automated in Python using our interval analysis toolbox $\texttt{npinterval}$, in conjunction with the symbolic arithmetic toolbox $\texttt{sympy}$, demonstrated on an $8$-dimensional leader-follower system.

In this paper, we propose a computationally efficient framework for interval reachability of systems with neural network controllers. Our approach leverages inclusion functions for the open-loop system and the neural network controller to embed the closed-loop system into a larger-dimensional embedding system, where a single trajectory over-approximates the original system's behavior under uncertainty. We propose two methods for constructing closed-loop embedding systems, which account for the interactions between the system and the controller in different ways. The interconnection-based approach considers the worst-case evolution of each coordinate separately by substituting the neural network inclusion function into the open-loop inclusion function. The interaction-based approach uses novel Jacobian-based inclusion functions to capture the first-order interactions between the open-loop system and the controller by leveraging state-of-the-art neural network verifiers. Finally, we implement our approach in a Python framework called ReachMM to demonstrate its efficiency and scalability on benchmarks and examples ranging to $200$ state dimensions.

In this paper, we present a toolbox for interval analysis in numpy, with an application to formal verification of neural network controlled systems. Using the notion of natural inclusion functions, we systematically construct interval bounds for a general class of mappings. The toolbox offers efficient computation of natural inclusion functions using compiled C code, as well as a familiar interface in numpy with its canonical features, such as n-dimensional arrays, matrix/vector operations, and vectorization. We then use this toolbox in formal verification of dynamical systems with neural network controllers, through the composition of their inclusion functions.

In this paper, we present a contraction-guided adaptive partitioning algorithm for improving interval-valued robust reachable set estimates in a nonlinear feedback loop with a neural network controller and disturbances. Based on an estimate of the contraction rate of over-approximated intervals, the algorithm chooses when and where to partition. Then, by leveraging a decoupling of the neural network verification step and reachability partitioning layers, the algorithm can provide accuracy improvements for little computational cost. This approach is applicable with any sufficiently accurate open-loop interval-valued reachability estimation technique and any method for bounding the input-output behavior of a neural network. Using contraction-based robustness analysis, we provide guarantees of the algorithm's performance with mixed monotone reachability. Finally, we demonstrate the algorithm's performance through several numerical simulations and compare it with existing methods in the literature. In particular, we report a sizable improvement in the accuracy of reachable set estimation in a fraction of the runtime as compared to state-of-the-art methods.

While monotone operator theory is often studied on Hilbert spaces, many interesting problems in machine learning and optimization arise naturally in finite-dimensional vector spaces endowed with non-Euclidean norms, such as diagonally-weighted $\ell_{1}$ or $\ell_{\infty}$ norms. This paper provides a natural generalization of monotone operator theory to finite-dimensional non-Euclidean spaces. The key tools are weak pairings and logarithmic norms. We show that the resolvent and reflected resolvent operators of non-Euclidean monotone mappings exhibit similar properties to their counterparts in Hilbert spaces. Furthermore, classical iterative methods and splitting methods for finding zeros of monotone operators are shown to converge in the non-Euclidean case. We apply our theory to equilibrium computation and Lipschitz constant estimation of recurrent neural networks, obtaining novel iterations and tighter upper bounds via forward-backward splitting., Comment: arXiv admin note: text overlap with arXiv:2204.01877

This paper proposes a computationally efficient framework, based on interval analysis, for rigorous verification of nonlinear continuous-time dynamical systems with neural network controllers. Given a neural network, we use an existing verification algorithm to construct inclusion functions for its input-output behavior. Inspired by mixed monotone theory, we embed the closed-loop dynamics into a larger system using an inclusion function of the neural network and a decomposition function of the open-loop system. This embedding provides a scalable approach for safety analysis of the neural control loop while preserving the nonlinear structure of the system. We show that one can efficiently compute hyper-rectangular over-approximations of the reachable sets using a single trajectory of the embedding system. We design an algorithm to leverage this computational advantage through partitioning strategies, improving our reachable set estimates while balancing its runtime with tunable parameters. We demonstrate the performance of this algorithm through two case studies. First, we demonstrate this method's strength in complex nonlinear environments. Then, we show that our approach matches the performance of the state-of-the art verification algorithm for linear discretized systems., Comment: Extended L4DC version with proofs

In this note, we study monotone dynamical systems with respect to polyhedral cones. Using the half-space representation and the vertex representation, we propose three equivalent conditions to certify monotonicity of a dynamical system with respect to a polyhedral cone. We then introduce the notion of gauge norm associated with a cone and provide closed-from formulas for computing gauge norms associated with polyhedral cones. A key feature of gauge norms is that contractivity of monotone systems with respect to them can be efficiently characterized using simple inequalities. This result generalizes the well-known criteria for Hurwitzness of Metzler matrices and provides a scalable approach to search for Lyapunov functions of monotone systems with respect to polyhedral cones. Finally, we study the applications of our results in transient stability of dynamic flow networks and in scalable control design with safety guarantees.

This paper proposes a theoretical and computational framework for training and robustness verification of implicit neural networks based upon non-Euclidean contraction theory. The basic idea is to cast the robustness analysis of a neural network as a reachability problem and use (i) the $\ell_{\infty}$-norm input-output Lipschitz constant and (ii) the tight inclusion function of the network to over-approximate its reachable sets. First, for a given implicit neural network, we use $\ell_{\infty}$-matrix measures to propose sufficient conditions for its well-posedness, design an iterative algorithm to compute its fixed points, and provide upper bounds for its $\ell_\infty$-norm input-output Lipschitz constant. Second, we introduce a related embedded network and show that the embedded network can be used to provide an $\ell_\infty$-norm box over-approximation of the reachable sets of the original network. Moreover, we use the embedded network to design an iterative algorithm for computing the upper bounds of the original system's tight inclusion function. Third, we use the upper bounds of the Lipschitz constants and the upper bounds of the tight inclusion functions to design two algorithms for the training and robustness verification of implicit neural networks. Finally, we apply our algorithms to train implicit neural networks on the MNIST dataset and compare the robustness of our models with the models trained via existing approaches in the literature., Comment: arXiv admin note: text overlap with arXiv:2112.05310

In a Nature article, Scheffer et al. presented a novel data-driven framework to predict critical transitions in complex systems. These transitions, which may stem from failures, degradation, or adversarial actions, have been attributed to bifurcations in the nonlinear dynamics. Their approach was built upon the phenomenon of critical slowing down, i.e., slow recovery in response to small perturbations near bifurcations. We extend their approach to detect and localize critical transitions in nonlinear networks. By introducing the notion of network critical slowing down, the objective of this paper is to detect that the network is undergoing a bifurcation only by analyzing its signatures from measurement data. We focus on two classes of widely-used nonlinear networks: (1) Kuramoto model for the synchronization of coupled oscillators and (2) attraction-repulsion dynamics in swarms, each of which presents a specific type of bifurcation. Based on the phenomenon of critical slowing down, we study the asymptotic behavior of the perturbed system away and close to the bifurcation and leverage this fact to develop a deterministic method to detect and identify critical transitions in nonlinear networks. Furthermore, we study the state covariance matrix subject to a stochastic noise process away and close to the bifurcation and use it to develop a stochastic framework for detecting critical transitions. Our simulation results show the strengths and limitations of the methods.

We provide a novel transcription of monotone operator theory to the non-Euclidean finite-dimensional spaces $\ell_1$ and $\ell_{\infty}$. We first establish properties of mappings which are monotone with respect to the non-Euclidean norms $\ell_1$ or $\ell_{\infty}$. In analogy with their Euclidean counterparts, mappings which are monotone with respect to a non-Euclidean norm are amenable to numerous algorithms for computing their zeros. We demonstrate that several classic iterative methods for computing zeros of monotone operators are directly applicable in the non-Euclidean framework. We present a case-study in the equilibrium computation of recurrent neural networks and demonstrate that casting the computation as a suitable operator splitting problem improves convergence rates.

We use interval reachability analysis to obtain robustness guarantees for implicit neural networks (INNs). INNs are a class of implicit learning models that use implicit equations as layers and have been shown to exhibit several notable benefits over traditional deep neural networks. We first establish that tight inclusion functions of neural networks, which provide the tightest rectangular over-approximation of an input-output map, lead to sharper robustness guarantees than the well-studied robustness measures of local Lipschitz constants. Like Lipschitz constants, tight inclusions functions are computationally challenging to obtain, and we thus propose using mixed monotonicity and contraction theory to obtain computationally efficient estimates of tight inclusion functions for INNs. We show that our approach performs at least as well as, and generally better than, applying state-of-the-art interval bound propagation methods to INNs. We design a novel optimization problem for training robust INNs and we provide empirical evidence that suitably-trained INNs can be more robust than comparably-trained feedforward networks.

In this paper, we study robustness of input metering policies in dynamic flow networks in the presence of transient disturbances and attacks. We consider a compartmental model for dynamic flow networks with a First-In-First-Out (FIFO) routing rule as found in, e.g., transportation networks. We model the effect of the transient disturbance as an abrupt change to the state of the network and use the notion of the region of attraction to measure the resilience of the network to these changes. For constant and periodic input metering, we introduce the notion of monotone-invariant points to establish inner-estimates for the regions of attraction of free-flow equilibrium points and free-flow periodic orbits using monotone systems theory. These results are applicable to, e.g., networks with cycles, which have not been considered in prior literature on dynamic flow networks with FIFO routing. Finally, we propose two approaches for finding suitable monotone-invariant points in the flow networks with FIFO rules.

The analysis of dissipatively coupled oscillators is challenging and highly relevant in power grids. Standard mathematical methods are not applicable, due to the lack of network symmetry induced by dissipative couplings. Here we demonstrate a close correspondence between stable synchronous states in dissipatively coupled oscillators, and the {winding partition} of their state space, a geometric notion induced by the network topology. Leveraging this winding partition, we accompany this article with an algorithms to compute all synchronous solutions of complex networks of dissipatively coupled oscillators. These geometric and computational tools allow us to identify anomalous behaviors of lossy networked systems. Counterintuitively, we show that loop flows and dissipation can increase the system's transfer capacity, and that dissipation can promote multistability. We apply our geometric framework to compute power flows on the IEEE RTS-96 test system, where we identify two high voltage solutions with distinct loop flows., Comment: Main text: 14 pages, 5 figures. Supplementary information: 6 pages, 2 figures

Given a flow network with variable suppliers and fixed consumers, the minimax flow problem consists in minimizing the maximum flow between nodes, subject to flow conservation and capacity constraints. We solve this problem over acyclic graphs in a distributed manner by showing that it can be recast as a consensus problem between the maximum downstream flows, which we define here for the first time. Additionally, we present a distributed algorithm to estimate these quantities. Finally, exploiting our theoretical results, we design an online distributed controller to prevent overcurrent in microgrids consisting of loads and droop-controlled inverters. Our results are validated numerically on the CIGRE benchmark microgrid.

Implicit neural networks are a general class of learning models that replace the layers in traditional feedforward models with implicit algebraic equations. Compared to traditional learning models, implicit networks offer competitive performance and reduced memory consumption. However, they can remain brittle with respect to input adversarial perturbations. This paper proposes a theoretical and computational framework for robustness verification of implicit neural networks; our framework blends together mixed monotone systems theory and contraction theory. First, given an implicit neural network, we introduce a related embedded network and show that, given an $\ell_\infty$-norm box constraint on the input, the embedded network provides an $\ell_\infty$-norm box overapproximation for the output of the given network. Second, using $\ell_{\infty}$-matrix measures, we propose sufficient conditions for well-posedness of both the original and embedded system and design an iterative algorithm to compute the $\ell_{\infty}$-norm box robustness margins for reachability and classification problems. Third, of independent value, we propose a novel relative classifier variable that leads to tighter bounds on the certified adversarial robustness in classification problems. Finally, we perform numerical simulations on a Non-Euclidean Monotone Operator Network (NEMON) trained on the MNIST dataset. In these simulations, we compare the accuracy and run time of our mixed monotone contractive approach with the existing robustness verification approaches in the literature for estimating the certified adversarial robustness.

The design of fixed point algorithms is at the heart of monotone operator theory, convex analysis, and of many modern optimization problems arising in machine learning and control. This tutorial reviews recent advances in understanding the relationship between Demidovich conditions, one-sided Lipschitz conditions, and contractivity theorems. We review the standard contraction theory on Euclidean spaces as well as little-known results for Riemannian manifolds. Special emphasis is placed on the setting of non-Euclidean norms and the recently introduced weak pairings for the $\ell_1$ and $\ell_\infty$ norms. We highlight recent results on explicit and implicit fixed point schemes for non-Euclidean contracting systems., Comment: Paper in the invited tutorial session "Contraction Theory for Machine Learning" at 60th IEEE Conference on Decision and Control, 2021

Implicit neural networks, a.k.a., deep equilibrium networks, are a class of implicit-depth learning models where function evaluation is performed by solving a fixed point equation. They generalize classic feedforward models and are equivalent to infinite-depth weight-tied feedforward networks. While implicit models show improved accuracy and significant reduction in memory consumption, they can suffer from ill-posedness and convergence instability. This paper provides a new framework, which we call Non-Euclidean Monotone Operator Network (NEMON), to design well-posed and robust implicit neural networks based upon contraction theory for the non-Euclidean norm $\ell_{\infty}$. Our framework includes (i) a novel condition for well-posedness based on one-sided Lipschitz constants, (ii) an average iteration for computing fixed-points, and (iii) explicit estimates on input-output Lipschitz constants. Additionally, we design a training problem with the well-posedness condition and the average iteration as constraints and, to achieve robust models, with the input-output Lipschitz constant as a regularizer. Our $\ell_{\infty}$ well-posedness condition leads to a larger polytopic training search space than existing conditions and our average iteration enjoys accelerated convergence. Finally, we evaluate our framework in image classification through the MNIST and the CIFAR-10 datasets. Our numerical results demonstrate improved accuracy and robustness of the implicit models with smaller input-output Lipschitz bounds. Code is available at https://github.com/davydovalexander/Non-Euclidean_Mon_Op_Net.

In this note we study contractivity of monotone systems and exponential convergence of positive systems using non-Euclidean norms. We first introduce the notion of conic matrix measure as a framework to study stability of monotone and positive systems. We study properties of the conic matrix measures and investigate their connection with weak pairings and standard matrix measures. Using conic matrix measures and weak pairings, we characterize contractivity and incremental stability of monotone systems with respect to non-Euclidean norms. Moreover, we use conic matrix measures to provide sufficient conditions for exponential convergence of positive systems to their equilibria. We show that our framework leads to novel results on (i) the contractivity of excitatory Hopfield neural networks, and (ii) the stability of interconnected systems using non-monotone positive comparison systems.

We study necessary and sufficient conditions for contraction and incremental stability of dynamical systems with respect to non-Euclidean norms. First, we introduce weak pairings as a framework to study contractivity with respect to arbitrary norms, and characterize their properties. We introduce and study the sign and max pairings for the $\ell_1$ and $\ell_\infty$ norms, respectively. Using weak pairings, we establish five equivalent characterizations for contraction, including the one-sided Lipschitz condition for the vector field as well as matrix measure and Demidovich conditions for the corresponding Jacobian. Third, we extend our contraction framework in two directions: we prove equivalences for contraction of continuous vector fields and we formalize the weaker notion of equilibrium contraction, which ensures exponential convergence to an equilibrium. Finally, as an application, we provide (i) incremental input-to-state stability and finite input-state gain properties for contracting systems, and (ii) a general theorem about the Lipschitz interconnection of contracting systems, whereby the Hurwitzness of a gain matrix implies the contractivity of the interconnected system.

Contraction theory for dynamical systems on Euclidean spaces is well-established. For contractive (resp. semi-contractive) systems, the distance (resp. semi-distance) between any two trajectories decreases exponentially fast. For partially contractive systems, each trajectory converges exponentially fast to an invariant subspace. In this note, we develop contraction theory on Hilbert spaces. First, we provide a novel integral condition for contractivity, and for time-invariant systems, we establish the existence of a unique globally exponentially stable equilibrium. Second, we introduce the notions of partial and semi-contraction and we provide various sufficient conditions for time-varying and time-invariant systems. Finally, we apply the theory on a classic reaction-diffusion system.

We develop two generalizations of contraction theory, namely, semi-contraction and weak-contraction theory. First, using the notion of semi-norm, we propose a geometric framework for semi-contraction theory. We introduce matrix semi-measures and characterize their properties. We show that the spectral abscissa of a matrix is the infimum over weighted semi-measures. For dynamical systems, we use the semi-measure of their Jacobian to characterize the contractivity properties of their trajectories. Second, for weakly contracting systems, we prove a dichotomy for the asymptotic behavior of their trajectories and novel sufficient conditions for convergence to an equilibrium. Third, we show that every trajectory of a doubly-contracting system, i.e., a system that is both weakly and semi-contracting, converges to an equilibrium point. Finally, we apply our results to various important network systems including affine averaging and affine flow systems, continuous-time distributed primal-dual algorithms, and networks of diffusively-coupled dynamical systems. For diffusively-coupled systems, the semi-contraction theory leads to a sufficient condition for synchronization that is sharper, in general, than previously-known tests.

Many tasks regarding the monitoring, management, and design of communication networks rely on knowledge of the routing topology. However, the standard approach to topology mapping--namely, active probing with traceroutes--relies on cooperation from increasingly non-cooperative routers, leading to missing information. Network tomography, which uses end-to-end measurements of additive link metrics (like delays or log packet loss rates) across monitor paths, is a possible remedy. Network tomography does not require that routers cooperate with traceroute probes, and it has already been used to infer the structure of multicast trees. This paper goes a step further. We provide a tomographic method to infer the underlying routing topology of an arbitrary set of monitor paths using the joint distribution of end-to-end measurements, without making any assumptions on routing behavior. Our approach, called the M\"obius Inference Algorithm (MIA), uses cumulants of this distribution to quantify high-order interactions among monitor paths, and it applies M\"obius inversion to "disentangle" these interactions. In addition to MIA, we provide a more practical variant called Sparse M\"obius Inference, which uses various sparsity heuristics to reduce the number and order of cumulants required to be estimated. We show the viability of our approach using synthetic case studies based on real-world ISP topologies.

In this note, we provide an overarching analysis of primal-dual dynamics associated to linear equality-constrained optimization problems using contraction analysis. For the well-known standard version of the problem: we establish convergence under convexity and the contracting rate under strong convexity. Then, for a canonical distributed optimization problem, we use partial contractivity to establish global exponential convergence of its primal-dual dynamics. As an application, we propose a new distributed solver for the least-squares problem with the same convergence guarantees. Finally, for time-varying versions of both centralized and distributed primal-dual dynamics, we exploit their contractive nature to establish bounds on their tracking error. To support our analyses, we introduce novel results on contraction theory.

Due to the rise of distributed energy resources, the control of networks of grid-forming inverters is now a pressing issue for power system operation. Droop control is a popular control strategy in the literature for frequency control of these inverters. In this paper, we analyze transient stability in droop-controlled inverter networks that are subject to multiple operating constraints. Using a physically-meaningful Lyapunov-like function, we provide two sets of criteria (one mathematical and one computational) to certify that a post-fault trajectory achieves frequency synchronization while respecting operating constraints. We show how to obtain less-conservative transient stability conditions by incorporating information from loop flows, i.e., net flows of active power around cycles in the network. Finally, we use these conditions to quantify the scale of parameter disturbances to which the network is robust. We illustrate our results with numerical case studies of the IEEE 24-bus system.

This paper studies the graph-theoretic conditions for stability of positive monotone systems. Using concepts from input-to-state stability and network small-gain theory, we first establish necessary and sufficient conditions for the stability of linear positive systems described by Metzler matrices. Specifically, we derive two sets of stability conditions based on two forms of input-to-state stability gains for Metzler systems, namely max-interconnection gains and sum-interconnection gains. Based on the max-interconnection gains, we show that the cyclic small-gain theorem becomes necessary and sufficient for the stability of Metzler systems; based on the sum-interconnection gains, we obtain novel graph-theoretic conditions for the stability of Metzler systems. All these conditions highlight the role of cycles in the interconnection graph and unveil how the structural properties of the graph affect stability. Finally, we extend our results to the nonlinear monotone system and obtain similar sufficient conditions for global asymptotic stability.

This paper examines small-signal stability of electrical networks composed dominantly of three-phase grid-following inverters. We show that the mere existence of a high-voltage power flow solution does not necessarily imply small-signal stability; this motivates us to develop a framework for stability analysis that systematically acknowledges inverter dynamics. We identify a suitable time-scale decomposition for the inverter dynamics, and using singular perturbation theory, obtain an analytic sufficient condition to verify small-signal stability. Compared to the alternative of performing an eigenvalue analysis of the full-order network dynamics, our analytic sufficient condition reduces computational complexity and yields insights on the role of network topology and constitution as well as inverter-filter and control parameters on small-signal stability. Numerical simulations for a radial network validate the approach and illustrate the efficiency of our analytic conditions for designing and monitoring grid-tied inverter networks.

Networks with phase-valued nodal variables are central in modeling several important societal and physical systems, including power grids, biological systems, and coupled oscillator networks. One of the distinctive features of phase-valued networks is the existence of multiple operating conditions corresponding to critical points of an energy function or feasible flows of a balance equation. For networks with phase-valued states, it is not yet fully understood how many operating conditions exist, how to characterize them, and how to compute them efficiently. A deeper understanding of feasible operating conditions, including their dependence upon network structures, may lead to more reliable and efficient network systems. This paper introduces flow and elastic network problems on the $n$-torus and provides a rigorous and comprehensive framework for their study. Based on a monotonicity assumption, this framework localizes the solutions, bounds their number, and leads to an algorithm to compute them. Our analysis is based on a novel winding partition of the $n$-torus into winding cells, induced by Kirchhoff's angle law for undirected graphs. The winding partition has several useful properties, including notably that, each winding cell contains at most one solution. The proposed algorithm is based on a novel contraction mapping and is guaranteed to compute all solutions. Finally, we apply our results to numerically study the active power flow equations in several test cases and estimate power capacity and congestion of a power network.

Synchronization in networks of coupled oscillators is a widely studied topic with extensive scientific and engineering applications. In this paper, we study the frequency synchronization problem for networks of Kuramoto oscillators with arbitrary topology and heterogeneous edge weights. We propose a novel equivalent transcription for the equilibrium synchronization equation. Using this transcription, we develop a power series expansion to compute the synchronized solution of the Kuramoto model as well as a sufficient condition for the strong convergence of this series expansion. Truncating the power series provides (i) an efficient approximation scheme for computing the synchronized solution, and (ii) a simple-to-check, statistically-correct hierarchy of increasingly accurate synchronization tests. This hierarchy of tests provides a theoretical foundation for and generalizes the best-known approximate synchronization test in the literature. Our numerical experiments illustrate the accuracy and the computational efficiency of the truncated series approximation compared to existing iterative methods and existing synchronization tests.

Synchronization in the networks of coupled oscillators is a widely studied topic in different areas. It is well-known that synchronization occurs if the connectivity of the network dominates heterogeneity of the oscillators. Despite extensive study on this topic, the quest for sharp closed-form synchronization tests is still in vain. In this paper, we present an algorithm for finding the Taylor expansion of the inverse Kuramoto map. We show that this Taylor series can be used to obtain a hierarchy of increasingly accurate approximate tests with low computational complexity. These approximate tests are then used to estimate the threshold of synchronization as well as the position of the synchronization manifold of the network.

Synchronization in coupled oscillators networks is a remarkable phenomenon of relevance in numerous fields. For Kuramoto oscillators the loss of synchronization is determined by a trade-off between coupling strength and oscillator heterogeneity. Despite extensive prior work, the existing sufficient conditions for synchronization are either very conservative or heuristic and approximate. Using a novel cutset projection operator, we propose a new family of sufficient synchronization conditions; these conditions rigorously identify the correct functional form of the trade-off between coupling strength and oscillator heterogeneity. To overcome the need to solve a nonconvex optimization problem, we then provide two explicit bounding methods, thereby obtaining (i) the best-known sufficient condition for unweighted graphs based on the 2-norm, and (ii) the first-known generally-applicable sufficient condition based on the $\infty$-norm. We conclude with a comparative study of our novel $\infty$-norm condition for specific topologies and IEEE test cases; for most IEEE test cases our new sufficient condition is one to two orders of magnitude more accurate than previous rigorous tests.

In this paper, we study small-time local controllability of real analytic control-affine systems under small perturbations of their vector fields. Consider a real analytic control system $\mathcal{X}$ which is small-time locally controllable and whose reachable sets shrink with the polynomial rate of order $N$ with respect to time. We will prove a general theorem which states that any real analytic control-affine system whose vector fields are perturbations of the vector fields of $\mathcal{X}$ with polynomials of order higher than $N$ is again small-time locally controllable. In particular, we show that this result connects two long-standing open conjectures about small-time local controllability of systems., Comment: 22 pages

In this paper, we consider time-varying real analytic vector fields as curves on the space of real analytic vector fields. Using a suitable topology on the space of real analytic vector fields, we study and characterize different properties of time-varying real analytic vector fields. We study holomorphic extensions of time-varying real analytic vector fields and show that under suitable integrability conditions, a time-varying real analytic vector field on a manifold can be extended to a time-varying holomorphic vector field on a neighbourhood of that manifold. Moreover, we develop an operator setting, where the nonlinear differential equation governing the flow of a time-varying real analytic vector field can be considered as a linear differential equation on an infinite dimensional locally convex vector space. Using the holomorphic extension results, we show that the integrability of the time-varying vector field ensures the convergence of the sequence of Picard iterations for this linear differential equation. This gives us a series representation for the flow of an integrable time-varying real analytic vector field. We also define the exponential map between integrable time-varying real analytic vector fields and their flows. Using the holomorphic extensions of time-varying real analytic vector fields, we show that the exponential map is sequentially continuous.

Just as an explicit parameterisation of system dynamics by state, i.e., a choice of coordinates, can impede the identification of general structure, so it is too with an explicit parameterisation of system dynamics by control. However, such explicit and fixed parameterisation by control is commonplace in control theory, leading to definitions, methodologies, and results that depend in unexpected ways on control parameterisation. In this paper a framework is presented for modelling systems in geometric control theory in a manner that does not make any choice of parameterisation by control; the systems are called "tautological control systems." For the framework to be coherent, it relies in a fundamental way on topologies for spaces of vector fields. As such, classes of systems are considered possessing a variety of degrees of regularity: finitely differentiable; Lipschitz; smooth; real analytic. In each case, explicit geometric seminorms are provided for the topologies of spaces of vector fields that enable straightforward descriptions of time-varying vector fields and control systems. As part of the development, theorems are proved for regular (including real analytic) dependence on initial conditions of flows of vector fields depending measurably on time. Classes of "ordinary" control systems are characterised that interact with the regularity under consideration in a comprehensive way. In this framework, for example, the statement that "a smooth or real analytic control-affine system is a smooth or real analytic control system" becomes a theorem. Correspondences between ordinary control systems and tautological control systems are carefully examined, and trajectory correspondence between the two classes is proved for control-affine systems and for systems with general control dependence when the control set is compact., Comment: 203 pages, 182 references