Nonexpansive Piecewise Constant Hybrid Systems are Conservative

Arsalan Sharifnassab, John N. Tsitsiklis, S. Jamaloddin GolestaniarXiv 2019 · arXiv

Abstract This paper establishes a fundamental link between stability and conservativeness in hybrid dynamical systems. We prove that any well-formed, nonexpansive system with a finite number of constant drift regions is necessarily a gradient flow of a piecewise linear convex potential function. This equivalence demonstrates that the absence of "drift apart" behavior in finite-partition systems forces a rigid combinatorial structure that precludes rotational or non-conservative dynamics.

Introduction

In fields like communication networks, manufacturing, and inventory management, systems are frequently modeled using polyhedral hybrid systems. In these models, the state space is partitioned into different regions (polyhedra), and within each region, the system moves at a constant "drift" velocity. A classic example is the Max-Weight algorithm used in data centers to schedule jobs based on queue lengths.

Researchers typically evaluate two key properties in these systems:

  1. Nonexpansiveness: If two identical systems start at different points, the distance between them should never increase over time. This is a strong indicator of stability and robustness.
  2. Conservativeness: The system acts like a ball rolling down a hill, following the negative gradient of a potential function. Conservative systems are easier to analyze because they possess an inherent "energy" they minimize.
A state space partition with constant drift vectors $\mu_i$, illustrating a typical polyhedral hybrid system.

Previously, these two properties were considered independent. For instance, a clock hand moving at a constant speed is nonexpansive (the distance between points on the hand is constant) but not conservative (it does not converge to a minimum). This paper investigates whether, for systems with piecewise constant drifts, nonexpansiveness actually necessitates conservativeness.

Theoretical Framework

The authors employ tools from convex analysis and geometry to establish their result through a series of constructive proofs:

  • Weight Assignment: Weights are defined for the boundaries between adjacent regions based on the difference in their drift vectors.
  • Path Integration: By analyzing "fine paths" through the state space and leveraging the nonexpansive property, the authors prove a "Local Conservation of Weights."
  • Curl-Free Dynamics: The total weight around any closed loop (cycle) in the state space is shown to be zero. In traditional calculus, this "curl-free" condition is the requirement for a vector field to possess a potential function.
  • Potential Construction: Using these weights, the authors explicitly construct a piecewise linear convex function $\Phi(x)$ and prove that the system’s trajectories are identical to the negative subgradient flow of this function.

Key Insights and Ideas

  • The Power of Finiteness: A central insight is that the combination of a finite number of regions and the nonexpansive property forces a rigid combinatorial structure. This structure prevents "swirling" behavior (like the clock hand example) and necessitates a gradient flow.
  • Implicit Geometry: Even without assuming polyhedral regions initially, the requirements of nonexpansiveness and well-formedness force the regions to adopt a polyhedral geometry.
  • Sensitivity Bounds: Because these systems are proven to be conservative (specifically FPCS systems), they inherit powerful sensitivity properties. Small external perturbations have a bounded effect on the total state over time.

Main Results

The primary contribution of this work is Theorem 2.8, which establishes a three-way equivalence. For a well-formed nonexpansive system, the following classifications are essentially identical:

  1. Finite-Partition System
  2. Polyhedral Hybrid System
  3. Finitely Piecewise Constant Subgradient (FPCS) System

The authors demonstrate that even if a system is defined with complex initial parameters, if it is nonexpansive and possesses a finite number of drift vectors, there exists a "hidden" potential function that perfectly describes its trajectories.

Conclusion and Future Work

While this paper provides a robust theoretical foundation, several avenues for future research remain:

  • Infinite Regions: Investigating if the result holds for a countably infinite number of regions.
  • Variable Drift: Determining if systems with non-constant gradient-field drifts within regions remain globally conservative.
  • State Space Constraints: The current proof assumes operation across $\mathbb{R}^n$; the authors conjecture the result holds for restricted convex subsets.
  • Approximation Limits: While smooth systems can be approximated by hybrid systems, these approximations do not always preserve nonexpansiveness, meaning the conservative result may not automatically extend to all smooth systems.

Summary updated

Abstract

Consider a partition of $R^n$ into finitely many polyhedral regions $D_i$ and associated drift vectors $μ_i\in R^n$. We study ``hybrid'' dynamical systems whose trajectories have a constant drift, $\dot x=μ_i$, whenever $x$ is in the interior of the $i$th region $D_i$, and behave consistently on the boundary between different regions. Our main result asserts that if such a system is nonexpansive (i.e., if the Euclidean distance between any pair of trajectories is a nonincreasing function of time), then the system must be conservative, i.e., its trajectories are the same as the trajectories of the negative subgradient flow associated with a potential function. Furthermore, this potential function is necessarily convex, and is linear on each of the regions $D_i$. We actually establish a more general version of this result, by making seemingly weaker assumptions on the dynamical system of interest.
BibTeX
@misc{sharifnassab2019nonexpansive,
  author = {Arsalan Sharifnassab and Arsalan Sharif-Nassab and John N. Tsitsiklis and S. Jamaloddin Golestani},
  title = {{Nonexpansive Piecewise Constant Hybrid Systems are Conservative}},
  year = {2019},
  eprint = {1905.12361},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1905.12361},
}
Figure