Separability of Lyapunov Functions for Contractive Monotone Systems

arXiv:1609.06258v1 [cs.SY] 20 Sep 2016

Samuel Coogan

Abstract— We consider constructing Lyapunov functions for
systems that are both monotone and contractive with respect
to a weighted one norm or infinity norm. This class of systems
admits separable Lyapunov functions that are either the sum or
the maximum of a collection of functions of a single argument.
In either case, two classes of separable Lyapunov functions
exist: the first class is separable along the system’s state, and
the second class is separable along components of the system’s
vector field. The latter case is advantageous for many practically
motivated systems for which it is difficult to measure the
system’s state but easier to measure the system’s velocity or
rate of change. We provide several examples to demonstrate
our results.

I. I NTRODUCTION
A dynamical system is monotone if it maintains a partial
ordering of states along trajectories of the system [1], [2],
[3]. Monotone systems exhibit structure and ordered behavior
that leads to techniques for analysis and control, e.g., [4],
[5], [6]. Examples of monotone systems include certain
biological networks [7] and transportation networks [8], [9],
[10], and monotone systems theory has been applied to largescale analysis and distributed control [11], [12].
A dynamical system is contractive if the distance between
states along any pair of trajectories is exponentially decreasing [13], [14], [15], [16]. When an equilibrium exists, contraction implies global convergence and a Lyapunov function
is given by the distance to the equilibrium. The magnitude of
the vector field provides an alternative Lyapunov function.
Certain classes of monotone systems have been shown to
be also contractive with respect to non-Euclidean norms. For
example, [17], [18], [19] study a model for gene translation
which is monotone and contractive with respect to a weighted
ℓ1 norm. A closely related result is obtained for transportation flow networks in [20], [21]. In [20], a Lyapunov function
defined as the magnitude of the vector field is used, while a
Lyapunov function based on the distance of the state to the
equilibrium is used in [21].
In this paper, we study monotone systems that are contractive with respect to a weighted ℓ1 norm or ℓ∞ norm.
We first provide sufficient conditions establishing contraction
for monotone systems in terms of strict negativity of scaled
row or column sums of the Jacobian matrix for the system.
These conditions follow naturally from sufficient conditions
for monotonicity and for contraction. Next, we derive sumseparable and max-separable Lyapunov functions based on
the contraction metric. In particular, we introduce the notion
of Lyapunov functions that are separable along components
of the vector field. This is especially relevant for certain
S. Coogan is with the Electrical Engineering Department, University of
California, Los Angeles. scoogan@ucla.edu.

classes of systems such as multiagent control systems or
flow networks where it is often more practical to measure
velocity or flow rather than position or state. Additionally, we
present results of independent interest for proving asymptotic
stability and obtaining Lyapunov functions of systems that
are nonexpansive with respect to a particular vector norm,
i.e., the distance between states along any pair of trajectories
does not increase. Finally, we draw connections between our
results and related results, particularly small-gain theorems
for interconnected, nonlinear systems.
For linear monotone systems, also called positive systems,
scalable stability verification is possible by appealing to linear Lyapunov functions or scaled componentwise-maximum
Lyapunov functions [11]. We extend stability verification
results from [11] to nonlinear monotone systems by appealing to contraction theory. Separable Lyapunov functions
for nonlinear monotone systems are also studied in [12],
however, a contraction theoretic approach is not considered.
We also introduce a novel notion of flow separable Lyapunov
functions not considered in [12].
This paper is organized as follows. Section II establishes
notation and Section III provides the problem setup. Section
IV reviews contraction theory and provides a novel approach
for establishing asymptotic stability for nonexpansive systems. Section V provides the main results, and illustrative
examples are considered in Section VI. We provide discussion in Section VII and concluding remarks in Section VIII.
II. N OTATION
n×n

A matrix A ∈ R
is Metzler if all of its off diagonal
components are nonnegative. All inequalities are interpreted
elementwise. The vector of all ones is denoted by 1. For
scalar functions of one variable, we denote derivative with
the prime notation ′ . The ℓ1 and ℓ∞ norms P
are denote by
n
| · |1 and | · |∞ respectively, that is, |x|1 = i=1 |xi | and
n
|x|∞ = maxi=1,...,n |xi | for x ∈ R .
III. P ROBLEM S ETUP
We consider the nonlinear autonomous dynamical system
ẋ = f (x)

(1)

for x ∈ X ⊆ Rn and continuously differentiable f (·).
Let fi (x) indicate the ith component of f and denote the
Jacobian as J(x) = ∂f
∂x (x).
Denote by φ(t, x0 ) the solution to (1) at time t when the
system is initialized with state x0 at time 0. We assume that
(1) is forward complete and X is forward invariant for (1),
thus φ(t, x0 ) ∈ X for all t ≥ 0 and all x0 ∈ X . In this paper,
we consider X = Rn or X = Rn≥0 := {x ∈ Rn | x ≥ 0}.

Consider a forward invariant set K ⊂ X with x∗ ∈ K
an equilibrium for (1) for which the domain of attraction
includes K. Let V : K → R≥0 be a Lyapunov function for
(1) on K that establishes asymptotic stability of x∗ , that is:
V (x) is continuous and V (x) = 0 for x ∈ K if and only
if x = x∗ ; V (x) is radially unbounded; and V (φ(t, x0 )) is
a nonincreasing function of t and limt→∞ V (φ(t, x0 )) = 0
for all x0 ∈ K. In this paper, we consider non-differentiable
Lyapunov functions, for which standard Lyapunov theory can
be extended using generalized derivatives [12].
The Lyapunov function V (x) is state sum-separable if
V (x) =

n
X

Vi (xi )

(2)

i=1

for a collection of functions Vi . It is state max-separable if
V (x) = max Vi (xi ).

(3)

i=1,...,n

Lyapunov functions decomposable as (2) or (3) are considered in [12]. In this paper, we also consider Lyapunov
functions that are separable based on the dynamics of (1). If
n
X
Wi (fi (x)), or
(4)
V (x) =
i=1

V (x) = max Wi (fi (x))

(5)

i=1,...,n

for some collection of functions Wi , we say that V is,
respectively, flow sum-separable and flow max-separable.
Except in Section IV, we assume (1) is monotone:
Definition 1. The system (1) is monotone if the dynamics
maintain a partial order on solutions, that is,
x0 ≤ y0 =⇒ φ(t, x0 ) ≤ φ(t, y0 ) ∀t ≥ 0.

(6)

In this paper, monotonicity is defined with respect to
the positive orthant, although it is common to consider
monotonicity with respect to other cones [4].
Proposition 1 ([3, Ch. 3.1]). The system (1) is monotone if
and only if the Jacobian J(x) is Metzler for all x ∈ X .
IV. I NFINITESIMAL C ONTRACTION
We now review infinitesimal contraction for autonomous
dynamical systems. We again consider the system given in
(1) but momentarily disregard the assumption that the system
is monotone. Let | · | be a vector norm on Rn and let k · k be
its induced matrix norm on Rn×n . The corresponding matrix
measure of the matrix A ∈ Rn×n is defined as
kI + hAk − 1
µ(A) := lim+
.
(7)
h
h→0
Proposition 2. Let K ⊆ X be convex and forward-invariant.
If, for some c ∈ R,
µ(J(x)) ≤ c

∀x ∈ K,

(8)

then for any two solutions x(t) = φ(t, x0 ) and y(t) =
φ(t, y0 ) for x0 , y0 ∈ K it holds that, for all t ≥ 0,
|x(t) − y(t)| ≤ ect |x0 − y0 |,
|f (x(t))| ≤ ect |f (x0 )|.

and

(9)
(10)

Proof. A proof for condition (9) is found in [15] where it
is assumed that c < 0 although the proof holds without this
assumption.
Considering (10), let V (x) , |f (x)|. V (x(t)) is then
absolutely continuous as a function of t and therefore
V (x(t + h)) − V (x(t))
h
for almost all t. Furthermore,
|f (x(t + h))| − |f (x) + hf˙(x)|
lim
+
h
h→0
f (x(t + h)) − f (x)
≤ lim
− f˙(x)
h
h→0+
=0
V̇ (x(t)) , lim

h→0+

(11)

(12)
(13)
(14)

where we use the definition of f˙(x) and the fact |x|−|y| ≤
|x − y|. Since also f˙(x) = J(x)f (x), we combine (11)–(14)
and obtain
|f (x) + hJ(x)f (x)| − |f (x)|
(15)
V̇ (x(t)) = lim
h
h→0+
kI + hJ(x)k · |f (x)| − |f (x)|
(16)
≤ lim+
h
h→0
kI + hJ(x)k − 1
= lim+
|f (x)|
(17)
h
h→0
= µ(J(x))V (x).
(18)
By hypothesis, we then have V̇ (x) ≤ cV (x), and (10)
follows by integration.
It is also possible to obtain (10) using Coppel’s inequality;
see, e.g., [22, Section 2.5, Theorem 3] for a statement and
proof of the inequality.
Definition 2. The system (1) is infinitesimally contracting on
K with respect to the norm | · | if (8) holds for some c < 0.
If the system is infinitesimally contracting, then |f (x)|
decays to zero at an exponential rate by (10), and therefore each trajectory converges to a finite equilibrium. Since
(9) precludes the existence of more than one equilibrium,
we conclude that there exists a unique equilibrium, it is
asymptotically stable, and the domain of attraction includes
K. Moreover, Proposition 2 provides two possible Lyapunov
functions defined in terms of the norm | · |. Namely, if x∗ is
the unique equilibrium, then V (x) = |x − x∗ | and V (x) =
|f (x)| are both Lyapunov functions for (1).
For P
the ℓ1 norm with induced matrix norm kAk1 =
maxj i |Aij |, the induced matrix measure is given by


P
(19)
µ1 (A) = maxj Ajj + i6=j |Aij |
for any A ∈ Rn×n . Likewise, for
P the ℓ∞ norm with induced
matrix norm is kAk∞ = maxi j |Aij |, the induced matrix
measure is given by


P
µ∞ (A) = maxi Aii + j6=i |Aij | .
(20)

See, e.g., [23, Section II.8, Theorem 24], for a derivation
of the induced matrix measures for common vector norms.

The matrix measures given in (19) and (20) provide the
connection to sum-separable and max-separable Lyapunov
functions which are the focus of this paper.
We are particularly interested in vector norms and matrix
measures that arise from a scaling of another norm. Let | · |∗
be some particular vector norm and let µ∗ (·) be its induced
matrix measure. If P ∈ Rn×n is nonsingular, then we define
a new vector norm by |x|∗,P := |P x|∗ for which the induced
matrix measure satisfies
µ∗,P (A) = µ∗ (P AP −1 ).

(21)

hypotheses of the proposition, we have that V (x) is therefore
a Lyapunov function.
Note that a sequence V i (x) arising from a sequence of
weighted contraction metrics, i.e., V i (x) = |Pi (x − x∗ )| or
V i (x) = |Pi f (x)| for Pi converging to some nonsingular P ,
satisfies the conditions of Proposition 3.
V. C ONTRACTIVE M ONOTONE S YSTEMS
In the remainder of this paper, we assume (1) is monotone.
For A Metzler, since Aij ≥ 0 for all i 6= j,
Pn
(23)
µ1 (A) = maxj=1,...,n i=1 Aij ,
Pn
(24)
µ∞ (A) = maxi=1,...,n j=1 Aij ,

When P = diag(v) for some v ∈ Rn , we use the notation
| · |∗,v and µ∗,v (·) instead, where diag(v) denotes the n × n
matrix with v on the diagonal and zeros elsewhere.
For some classes of systems, it is only possible to establish
µ(J(x)) ≤ 0 for all x ∈ K. In this case, (8)–(9) implies a
nonexpansion property. Furthermore, it may still be possible
to demonstrate asymptotic stability of an equilibrium using
contraction theory.

that is, µ1 (A) is the largest column sum of A and µ∞ (A)
is the largest row sum of A. The following proposition is
easily verified from the identity (21).

Theorem 1. Let K ⊆ X be convex and forward-invariant
and let x∗ ∈ K be an equilibrium of (1). If

Likewise, for w ∈ Rn with w > 0,

µ(J(x)) ≤ 0 ∀x ∈ K

and

µ(J(x∗ )) < 0

(22)

then x∗ is asymptotically stable, the domain of attraction
includes K, and V (x) = |x − x∗ | and V (x) = |f (x)| are
Lyapunov functions.
Theorem 1 is closely related to existing results in the
literature, although we believe the generality provided by
Theorem 1 and the further generalization to periodically
time-varying systems in the appendix, for which we prove
convergence to a unique periodic trajectory, is novel. In
particular, [9, Lemma 6] provides a similar result for µ(·)
restricted to the matrix measure induced by the ℓ1 norm under the assumption that (1) is monotone. A similar technique
is applied to periodic trajectories of a class of monotone flow
networks in [24, Proposition 2], but a general formulation is
not presented.
We conclude with a final technical result that will be
useful for constructing Lyapunov functions as the limit of
a sequence of contraction metrics.
Proposition 3. Let K ⊆ X be forward-invariant and let
x∗ ∈ K be an asymptotically stable equilibrium of (1) for
which the domain of attraction includes K. Suppose there
exists a sequence of Lyapunov functions V i : K → R≥0
for (1) on K that converges locally uniformly to V (x) :=
limi→∞ V i (x). If V (x) is radially unbounded and V (x) = 0
if and only if x = x∗ , then V (x) is also a Lyapunov function
for (1).
Proof. Consider some x0 ∈ K. Asymptotic stability
of x∗ implies there exists a bounded set Ω for which
φ(t, x0 ) ∈ Ω ⊆ K for all t ≥ 0. For i =
1, . . . , n, we have V i (φ(t, x0 )) is nonincreasing in t and
limt→∞ V i (φ(t, x0 )) = 0. Local uniform convergence establishes V (x) is continuous, V (φ(t, x0 )) is nonincreasing
in t, and limt→∞ V (φ(t, x0 )) = 0. Under the additional

Proposition 4. For A Metzler and v ∈ Rn with v > 0,
µ1,v (A) < c

if and only if v T A < cv T .

µ∞,w† (A) < c

if and only if Aw < cw

(25)

(26)

†

where w := (1/w1 , 1/w2 , . . . , 1/wn ).
Propositions 1 and 4 lead to the following theorems.
Theorem 2. Let (1) be a monotone system. If there exists
v > 0, c < 0, and convex, forward invariant K ⊆ X such
that
v T J(x) ≤ c1T

∀x ∈ K,

(27)

then there exists an asymptotically stable equilibrium x∗ ∈
K and the domain of attraction includes K. Furthermore,
either of the following are Lyapunov functions on K:
n
X
vi |xi − x∗i |,
(28)
V (x) =
i=1

V (x) =

n
X

vi |fi (x)|.

(29)

i=1

Proof. Suppose (27) holds. There exists some c̃ < 0 such
that v T J(x) ≤ c̃v for all x ∈ K, in particular, we take
c̃ ∈ [c/|v|∞ , 0). From (25), it follows that µ1,v (J(x)) ≤ c̃.
The theorem follows from Proposition 2.
Theorem 3. Let (1) be a monotone system. If there exists
w > 0, c < 0, and convex, forward invariant K ⊆ X such
that
J(x)w ≤ c1

∀x ∈ K,

(30)

then there exists an asymptotically stable equilibrium x∗ ∈
K and the domain of attraction includes K. Furthermore,
either of the following are Lyapunov functions on K:


1
|xi − x∗i | ,
(31)
V (x) = max
i=1,...,n wi


1
V (x) = max
|fi (x)| .
(32)
i=1,...,n wi

Note that Theorem 2 and Theorem 3 lead to global asymptotic stability when K = X . Moreover, Theorems 2 and 3
can be considered nonlinear extensions of known stability
verification results for linear monotone (that is, positive)
systems. In particular, conditions (27) and (30) recover the
stability conditions (1.2) and (1.3) of [11, Proposition 1]
when J(x) is replaced with the static matrix A as detailed
in Example 1 below.

evolving on X = R2≥0 where γ : R≥0 → R≥0 is strictly
increasing and satisfies γ(0) = 0, γ̄ := limσ→∞ γ(σ) < 1,
1
and γ ′ (σ) ≤ (1+σ)
2 . Consider the change of coordinates
(η1 , η2 ) = (log(1 + x1 ), x2 ) so that

Definition 3. The system (1) is contractive monotone if it is
monotone and infinitesimally contracting.

η̇1 ≤ −β(eη1 − 1) + η2

The hypotheses of Theorem 2 and Theorem 3 imply
that the system is contractive monotone. We now specialize
Theorem 1 to monotone systems.
Corollary 1. Let (1) be a monotone system with equilibrium
x∗ . If there exists v > 0 and convex, forward invariant K ⊆
X such that
v T J(x) ≤ 0 ∀x ∈ K

and v T J(x∗ ) < 0,

(33)

then x∗ is asymptotically stable, the domain of attraction
includes K, and (28)–(29) are Lyapunov functions.
Corollary 2. Let (1) be a monotone system with equilibrium
x∗ . If there exists w > 0 and convex, forward invariant K ⊆
X such that
J(x)w ≤ 0 ∀x ∈ K

∗

and J(x )w < 0,

(34)

∗

η̇1 =

1
(−x1 + x1 x2 )
1 + x1

(39)

where we substitute (x1 , x2 ) = (eη1 − 1, η2 ). Then
(40)

where β(σ) = σ/(1 + σ). Introduce the comparison system
ξ˙1 = −β(eξ1 − 1) + ξ2
ξ˙2 = −2ξ2 − ξ22 + γ(eξ1 − 1)2

(41)
(42)

evolving on R2≥0 . The comparison principle (see, e.g., [12])
ensures that asymptotic stability of the origin for the comparison system (41)–(42) implies asymptotic stability of the
origin of the (η1 , η2 ) system, which in turn establishes
asymptotic stability of the origin for (37)–(38). The Jacobian
of (41)–(42) is given by


1
−eξ1 β ′ (eξ1 − 1)
(43)
J(ξ) =
2eξ1 γ(eξ1 − 1)γ ′ (eξ1 − 1) −2 − 2ξ2
1
where β ′ (σ) = (1+σ)
2 . Let v = (2γ̄ +ǫ, 1) where ǫ is chosen
small enough so that c1 := (2γ̄ + ǫ − 2) < 0. It follows that

then x is asymptotically stable, the domain of attraction
includes K, and (31)–(32) are Lyapunov functions.

v T J(ξ) ≤ (−ǫe−ξ1 , c1 ) ≤ 0 ∀ξ

VI. E XAMPLES
We now present several examples. First, we recover a wellknown condition for stability of monotone linear systems,
also called positive linear systems.

and v T J(0) < 0. Applying Corollary 1, the origin of
(37)–(38) and (41)–(42) is globally asymptotically stable.
Furthermore, we have the following state and flow sumseparable Lyapunov functions for the comparison system
(41)–(42):

Example 1 (Linear systems). Consider ẋ = Ax for A
Metzler. Theorems 2 and 3 imply that if one of the following
conditions holds, then the system is globally asymptotically
stable:
There exists v > 0 such that v T A < 0,

or

(35)

There exists w > 0 such that Aw < 0.
(36)
Pn
If
i=1 vi |xi | and V (x) =
Pn(35) holds then V (x) =
i=1 vi |(Ax)i | are Lyapunov functions, and if (36)
holds then V (x) = maxi {|xi |/wi } and V (x) =
maxi {|(Ax)i |/wi } are Lyapunov functions where (Ax)i
denotes the ith element of Ax.

In fact, it is well known that A is Hurwitz if and only
if either (and therefore, both) of the two conditions (35)
and (36) hold, as established in, e.g., [11, Proposition 1],
and the corresponding state separable Lyapunov functions of
Example 1 are also derived in [11].
The following example is inspired by [12, Example 3].
Example 2 (Comparison system). Consider the system
ẋ1 = −x1 + x1 x2

(37)

ẋ2 = −2x2 − x22 + γ(x1 )2

(38)

(44)

V (ξ) = (2γ̄ + ǫ)ξ1 + ξ2

(45)

V (ξ) = (2γ̄ + ǫ)|ξ̇1 | + |ξ˙2 |.

(46)

Above, we understand ξ˙1 and ξ˙2 to be shorthand for the
equalities expressed in (41)–(42).

Example 3 (Multiagent system). Consider the following
system evolving on X = R3 :
ẋ1 = −α1 (x1 ) + ρ1 (x3 − x1 )
ẋ2 = ρ2 (x1 − x2 ) + ρ3 (x3 − x2 )

(47)
(48)

ẋ3 = ρ4 (x2 − x3 )

(49)

where we assume α1 : R → R is strictly increasing and
satisfies α(0) = 0 and α′1 (σ) ≥ c0 for some c0 > 0 for all
σ, and each ρi : R → R is strictly increasing and satisfies
ρi (0) = 0. Furthermore, for i = 1, 3, ρ′i (σ) ≤ ci for some
ci > 0 for all σ, and for i = 2, 4, ρ′i (σ) ≥ ci for some ci > 0
for all σ.
For example, x1 , x2 , and x3 may be the position of three
vehicles, for which the dynamics (47)–(49) are a rendezvous
protocol whereby agent 1 moves towards agent 3 at a rate
dependent on the distance x3 − x1 as determined by ρ1 , etc.

Additionally, agent 1 navigates towards the origin according
to −α1 (x1 ). Computing the Jacobian, we obtain
J(x) =
 ′

−α (x1 ) − ρ′1 (z31 )
0
ρ′1 (z31 )

ρ′2 (z12 )
−ρ′2 (z12 ) − ρ′3 (z32 ) ρ′3 (z32 ) 
0
ρ′4 (z23 )
−ρ′4 (z23 )
(50)
where zij := xi − xj . Let w = (1, 1 + ǫ1 , 1 + ǫ1 + ǫ2 )T where
ǫ1 > 0 and ǫ2 > 0 are chosen to satisfy
c0 > (ǫ1 + ǫ2 )c1

and ǫ1 c2 > ǫ2 c3 .

(51)

We then have J(x)w ≤ c1 for all x for c = max{(ǫ1 +
ǫ2 )c1 − c0 , ǫ2 c3 − ǫ1 c2 , −ǫ2 c4 } < 0. Thus, the origin of
(47)–(49) is globally asymptotically stable by Theorem 3.
Furthermore,
V (x) = max{|x1 |, (1 + ǫ1 )−1 |x2 |, (1 + ǫ1 + ǫ2 )−1 |x3 |},
(52)
V (x) = max{|ẋ1 |, (1 + ǫ1 )−1 |ẋ2 |, (1 + ǫ1 + ǫ2 )−1 |ẋ3 |}
(53)
are state and flow max-seperable Lyapunov functions where
we interpret ẋi as shorthand for the equalities expressed in
(47)–(49). Since we can take ǫ1 and ǫ2 arbitrarily small satisfying (51), using Proposition 3 we have also the following
choices for Lyapunov functions:
V (x) = max{|x1 |, |x2 |, |x3 |},
V (x) = max{|ẋ1 |, |ẋ2 |, |ẋ3 |}.

(54)
(55)

The flow max-separable Lyapunov functions (53) and (55)
are particularly useful for multiagent vehicular networks
where it often easier to measure each agent’s velocity rather
than absolute position.

In Example 3, choosing w = 1, we have J(x)w ≤ 0,
however this is not enough to establish asymptotic stability
using Theorem 3. Informally, choosing w as in the example distributes the extra negativity of −α′ (x1 ) among the
columns of J(x). Nonetheless, Proposition 3 implies that
choosing w = 1 indeed leads to a valid Lyapunov function.
The above example generalizes to systems with many
agents interacting via arbitrary directed graphs, as does
the principle of distributing extra negativity along diagonal
entries of the Jacobian as discussed in Section VII.
Example 4 (Traffic flow). A model of traffic flow along a
freeway with no onramps is obtained by spatially partitioning
the freeway into n segments such that traffic flows from
segment i to i + 1, xi ∈ [0, x̄i ] is the density of vehicles
occupying link i, and x̄i is the capacity of link i. A fraction
βi ∈ (0, 1] of the flow out of link i enters link i + 1. The
remaining 1 − βi fraction is assumed to exit the network
via, e.g., unmodeled offramps. Associated with each link is
a continuously differentiable demand function Di : [0, x̄i ] →
R≥0 that is strictly increasing and satisfies Di (0) = 0, and
a continuously differentiable supply function Si : [0, x̄i ] →
R≥0 that is strictly decreasing and satisfies Si (x̄i ) = 0. Flow

from segment to segment is restricted by upstream demand
and downstream supply, and the change in density of a link
is governed by mass conservation:
ẋ1 = min{δ1 , S1 (x1 )} −
ẋi = gi−1 (xi−1 , xi ) −

1
g1 (x1 , x2 )
β1

1
gi (xi , xi+1 ),
βi

(56)
i = 2, . . . , n − 1
(57)
(58)

ẋn = gn−1 (xn−1 , xn ) − Dn (xn )
for some δ1 > 0 where, for i = 1, . . . , n − 1,

gi (xi , xi+1 ) = min{βi Di (xi ), Si+1 (xi+1 )}.
(59)
Qi−1
−1
Let δi , δ1 j=1 βj for i = 2, . . . , n. If d−1
i (δi ) < si (δi )
∗
for all i, then δ1 is said to be feasible and xi := d−1
i (δi )
constitutes the unique equilibrium.
Let ∂i denote differentiation with respect to the ith compo∂g
(x) for a function g(x). The
nent of x, that is, ∂i g(x) := ∂x
i
dynamics (56)–(58) define a system ẋ = f (x) for which f
is continuous but only piecewise differentiable. Nonetheless,
the results developed above apply for this case, and, in the
sequel, we interpret statements involving derivatives to hold
wherever the derivative exists.
Notice that ∂i gi (xi , xi+1 ) ≥ 0 and ∂i+1 gi (xi , xi+1 ) ≤ 0.
Define g0 (x1 ) := min{δ1 , S1 (x1 )}. The Jacobian, where it
exists, is given by (60) on the following page. Let
T
ṽ = 1, β1−1 , (β1 β2 )−1 , . . . , (β1 β2 · · · βn−1 )−1 . (61)
Then ṽ T J(x) ≤ 0 for all x. Moreover, there exists ǫ =
(ǫ1 , ǫ2 , . . . , ǫn−1 , 0) with ǫi > ǫi+1 for each i such that v :=
ṽ + ǫ satisfies
v T J(x) ≤ 0
T

∀x

(62)

∗

v J(x ) < 0.

(63)

Such a vector ǫ is constructed using a technique similar
to that used in Example 3. In particular, the sum of the
nth column of diag(ṽ)J(x) is strictly negative because
−∂n Dn (xn ) < 0, and this excess negativity is used to
construct v such that (62)–(63) holds. A particular choice
of ǫ such that (62)–(63) holds depends on bounds on the
derivative of the demand functions Di , but it is possible to
choose ǫ arbitrarily small. Corollary 1 establishes asymptotic
stability, and Proposition 3 gives the following sum-separable
Lyapunov functions:


i−1
n
Y
X
|xi |
βj  ,
(64)
V (x) =
j=1

i=1

V (x) =

n
X
i=1



|ẋi |

i−1
Y

j=1



βj  ,

(65)

where we interpret ẋi according to (56)–(58).
In traffic networks, it is often easier to measure traffic flow
rather than traffic density. Thus, (65) is a practical Lyapunov
function indicating that the (weighted) total absolute net flow
throughout the network decreases over time.



∂1 g0 − β11 ∂1 g1

∂1 g1


0
J(x) = 

..

.
0

− β11 ∂2 g1
∂2 g1 − β12 ∂2 g2
∂2 g2

0
− β12 ∂3 g2
∂3 g2 − β13 ∂3 g3

0
0
− β13 ∂4 g3

···
···
..

0

···

In [10], a result similar to that of Example 4 is derived
for possibly infeasible input flow and traffic flow network
topologies where merging junctions with multiple incoming
links are allowed. The proof considers a flow sum-separable
Lyapunov function similar to (65) and appeals to LaSalle’s
invariance principle rather than Proposition 3.
VII. D ISCUSSION
We first highlight the connection of the above results
to small-gain conditions for interconnections of nonlinear
systems. Consider N interconnected systems with dynamics
ẋi = fi (x1 , . . . , xN ) for xi ∈ Rni and suppose they satisfy
an input-to-state stability (ISS) condition [25] whereby there
exists ISS Lyapunov functions Vi [26] satisfying
X
∂Vi
(xi )fi (x) ≤ −αi (Vi (xi )) +
γij (Vj (xj ))
(66)
∂xi
i6=j

where each αi and γij is a K∞ function. We obtain a
monotone comparison system
X
ν̇ = g(ν),
gi (ν) = −αi (νi ) +
γij (νj )
(67)
j6=i

Rn≥0

evolving on
for which asymptotic stability of the origin
implies asymptotic stability of the original system [27]. For
N = 2, it is noted in [28] that if γ12 (σ) = κ1 α2 (σ)
and γ21 (σ) = κ2 α1 (σ) for κ1 > 0, κ2 > 0 such that
κ1 κ2 < 1, then v1 V1 (x1 ) + v2 V (x2 ) is a Lyapunov function
for the original system for any v = (v1 v2 )T > 0 satisfying
v1 κ1 < v2 < v1 /κ2 . Indeed, for such a choice, we see that
∂g
(ν) ≤ 0, and if additionally α′i (0) > 0 for i = 1, 2,
v T ∂ν
∂g
then v T ∂ν
(0) < 0 so that Corollary 1 provides a contraction
theoretic interpretation of this result.
Alternatively, in [27], [29], it is shown that if there exists a
function ρ : R≥0 → Rn≥0 with each component ρi belonging
to class1 K∞ such that g(ρ(r)) < 0 for all r > 0, then the
origin is asymptotically stable and V (ν) := maxi {ρi−1 (νi )}
is a Lyapunov function. If condition (34) of Corollary 2
holds for the comparison system for some w, we may choose
ρ(r) = rw. Indeed, we have
Z 1
∂g
g(rw) =
(σrw)rw dσ < 0 ∀r > 0.
(68)
∂ν
0
For this case, V (ν) = maxi {ρ−1
i (νi )} = maxi {νi /wi },
recovering (31).
Next, we comment on the relationship between Theorem 1
as well as Proposition 3 and a generalization of contraction
1 A continuous function α : R
≥0 → R≥0 is of class K∞ if it is strictly
increasing, α(0) = 0, and limr→∞ α(r) = ∞.

0

.
∂n−1 gn−1


0

0


0


..

.
∂n gn−1 − ∂n Dn (xn )

(60)

theory recently developed in [30], [31] where exponential
contraction between any two trajectories is required only
after an arbitrarily small amount of time, an arbitrarily small
overshoot, or both. In [31, Corollary 1], it is shown that if
a system is contractive with respect to a sequence of norms
convergent to some norm, then the system is generalized
contracting with respect to that norm, a result analogous to
Proposition 3. In [31], conditions on the sign structure of
the Jacobian are obtained that ensure the existence of such a
sequence of weighted ℓ1 or ℓ∞ norms. These conditions are
a generalization of the technique in Example 3 and Example
4 above where small ǫ is used to distribute excess negativity.
Furthermore, it is shown in [17], [18] that a ribosome flow
model for gene translation is monotone and nonexpansive
with respect to a weighted ℓ1 norm, and additionally is
contracting on a subset of its domain. Entrainment of solutions is proved by first showing that all trajectories reach the
region of exponential contraction. Theorem 4 in the appendix
provides a different approach for studying entrainment by
observing that the distance to the periodic trajectory strictly
decreases in each period due to a neighborhood of contraction along the periodic trajectory. Theorem 1 provides an
analogous result for stability analysis of an equilibrium.
Finally, we note that Metzler matrices with nonpositive
column sums have also been called compartmental [32]. It
has been shown that if the Jacobian matrix is compartmental
for all x, then V (x) = |f (x)| is a decreasing function along
trajectories of (1) [32], [33]; we recover this observation by
considering the Lyapunov function implied by (10) with c =
0 and | · | taken to be the standard ℓ1 norm.
VIII. C ONCLUSIONS
We have investigated monotone systems that are also
contracting with respect to a weighted ℓ1 norm or ℓ∞ norm.
In the case of the ℓ1 (respectively, ℓ∞ ) norm, we provided
a condition on the weighted column (respectively, row)
sums of the Jacobian matrix for ensuring contraction. These
conditions lead to either sum-separable or max-separable
Lyapunov functions. In particular, we introduce a class of
separable Lyapunov functions that depend on the value of
the vector field along trajectories of the system. These
flow separable Lyapunov functions are especially relevant
in applications where it is easier to measure the derivative
of the system’s state rather than measure the state directly.
Paralleling observations made in [11], verifying (27) and
(30) requires checking nonpositivity of a collection of n
functions. For polynomial or rational vector fields, this
is done efficiently using sum-of-squares (SOS) techniques

[34]. Future work will consider scalable verification and
synthesis methods for contractive monotone systems using
SOS techniques.
IX. ACKNOWLEDGEMENTS
The author thanks Murat Arcak for providing valuable
feedback on an early draft of this paper.
A PPENDIX
To prove Theorem 1, we prove a more general result for
which Theorem 1 is a special case. Consider
ẋ = f (t, x)

(69)

for x ∈ X . We assume that f (t, x) is periodic in t with period
T . We further assume f (t, x) is differentiable in x and that
f (t, x) and the Jacobian J(t, x) , ∂f
∂x (t, x) are continuous
in (t, x).
Theorem 4. Let K ⊆ X be convex and forward-invariant
and suppose γ(t) be a periodic trajectory of (69) with period
T . If
µ(J(t, x)) ≤ 0

∀t ≥ 0, ∀x ∈ K

(70)

∗

and there exists t such that
µ(J(t∗ , γ(t∗ ))) < 0,

(71)

then for all trajectories x(t) = φ(t, x0 ), x0 ∈ K we have
lim |x(t) − γ(t)| = 0.

t→∞

(72)

Proof. Without loss of generality, assume t∗ = 0. Condition
(71) and continuity of J(t, x) imply there exists ǫ > 0, c > 0,
and 0 < τ ≤ T such that
µ(J(t, y)) ≤ −c

∀t ∈ [0, τ ], ∀y ∈ Bǫ (γ(t))

(73)

where Bǫ (y) = {z : |z − y| ≤ ǫ} denotes the closed ball of
radius ǫ centered at y ∈ Rn . Define the mapping
P (ξ) = φ(T, ξ)

(74)

and observe that P k (ξ) = φ(kT, ξ). Let γ ∗ = γ(0) and note
that γ ∗ is a fixed point of P . Consider a point ξ ∈ Bǫ (γ ∗ ).
Let x(t) = φ(t, ξ) and note that |P (ξ)−γ ∗ | = |x(T )−γ(T )|.
By (70), we have |x(T ) − γ(T )| ≤ |x(τ ) − γ(τ )| and, by
(73), we have [15]
|x(τ ) − γ(τ )| ≤ e−cτ |x(0) − γ(0)|.

(75)

Now consider ξ ∈ K such that |ξ − γ ∗ | > ǫ and again
let x(t) = φ(t, ξ). Let σ(r) = rξ + (1 − r)γ ∗ be the
parameterized line segment connecting γ ∗ and ξ, and let rǫ
be such that |σ(rǫ ) − γ ∗ | = ǫ. Note that |ξ − γ ∗ | = |ξ −
σ(rǫ )|+|σ(rǫ )−γ ∗ |. Let s(t) = φ(t, σ(rǫ )). By (70), we have
|x(T ) − s(T )| ≤ |x(0) − s(0)| = |ξ − σ(rǫ )| = |ξ − γ ∗ | − ǫ.
Furthermore, by the same argument as in the preceding case,
we have |s(T ) − γ(T )| ≤ e−cτ |σ(rǫ ) − γ ∗ | = e−cτ ǫ, and
thus by the triangle inequality,
|P (ξ) − γ ∗ | ≤ |x(T ) − s(T )| + |s(T ) − γ(T )|
∗

≤ |ξ − γ | − (1 − e
= |ξ − γ ∗ | − δ

−cτ

)ǫ

(76)
(77)
(78)

where δ := (1 − e−cτ )ǫ > 0. Then
(
|ξ − γ ∗ | − δ if |ξ − γ ∗ | > ǫ
∗
|P (ξ) − γ | ≤
e−cτ |ξ − γ ∗ | if |ξ − γ ∗ | ≤ ǫ.

(79)

It follows that for all ξ, |P k (ξ) − γ ∗ | ≤ ǫ for some finite
k (in particular, for any k ≥ |ξ − γ ∗ |/δ). The theorem then
follows from the second condition of (79).
Theorem 1 follows by taking γ(t) ≡ x∗ and arbitrary
T > 0, and we may take τ = T in the proof.
R EFERENCES
[1] M. W. Hirsch, “Differential equations and convergence almost everywhere in strongly monotone semiflows,” Contemporary Mathematics,
vol. 17, pp. 267–285, 1983.
[2] M. W. Hirsch, “Systems of differential equations that are competitive
or cooperative II: Convergence almost everywhere,” SIAM Journal on
Mathematical Analysis, vol. 16, no. 3, pp. 423–439, 1985.
[3] H. L. Smith, Monotone dynamical systems: An introduction to the theory of competitive and cooperative systems. American Mathematical
Society, 1995.
[4] D. Angeli and E. Sontag, “Monotone control systems,” IEEE Transactions on Automatic Control, vol. 48, no. 10, pp. 1684–1698, 2003.
[5] D. Angeli and E. Sontag, “Interconnections of monotone systems
with steady-state characteristics,” in Optimal control, stabilization and
nonsmooth analysis, pp. 135–154, Springer, 2004.
[6] S. Coogan and M. Arcak, “Efficient finite abstraction of mixed monotone systems,” in Proceedings of the 18th International Conference on
Hybrid Systems: Computation and Control, pp. 58–67, 2015.
[7] E. D. Sontag, “Monotone and near-monotone biochemical networks,”
Systems and Synthetic Biology, vol. 1, no. 2, pp. 59–87, 2007.
[8] G. Gomes, R. Horowitz, A. A. Kurzhanskiy, P. Varaiya, and J. Kwon,
“Behavior of the cell transmission model and effectiveness of ramp
metering,” Transportation Research Part C: Emerging Technologies,
vol. 16, no. 4, pp. 485–513, 2008.
[9] E. Lovisari, G. Como, and K. Savla, “Stability of monotone dynamical
flow networks,” in Proceedings of the 53rd Conference on Decision
and Control, pp. 2384–2389, 2014.
[10] S. Coogan and M. Arcak, “A compartmental model for traffic networks
and its dynamical behavior,” IEEE Transactions on Automatic Control,
vol. 60, no. 10, pp. 2698–2703, 2015.
[11] A. Rantzer, “Scalable control of positive systems,” European Journal
of Control, vol. 24, pp. 72–80, 2015.
[12] G. Dirr, H. Ito, A. Rantzer, and B. Rüffer, “Separable Lyapunov functions for monotone systems: constructions and limitations,” Discrete
Contin. Dyn. Syst. Ser. B, 2015.
[13] A. Pavlov, A. Pogromsky, N. van de Wouw, and H. Nijmeijer,
“Convergent dynamics, a tribute to Boris Pavlovich Demidovich,”
Systems & Control Letters, vol. 52, no. 3, pp. 257–261, 2004.
[14] W. Lohmiller and J.-J. E. Slotine, “On contraction analysis for nonlinear systems,” Automatica, vol. 34, no. 6, pp. 683–696, 1998.
[15] E. D. Sontag, “Contractive systems with inputs,” in Perspectives
in Mathematical System Theory, Control, and Signal Processing,
pp. 217–228, Springer, 2010.
[16] F. Forni and R. Sepulchre, “A differential Lyapunov framework
for contraction analysis,” IEEE Transactions on Automatic Control,
vol. 59, pp. 614–628, March 2014.
[17] M. Margaliot and T. Tuller, “Stability analysis of the ribosome
flow model,” IEEE/ACM Transactions on Computational Biology and
Bioinformatics (TCBB), vol. 9, no. 5, pp. 1545–1552, 2012.
[18] M. Margaliot, E. D. Sontag, and T. Tuller, “Entrainment to periodic
initiation and transition rates in a computational model for gene
translation,” PloS one, vol. 9, no. 5, p. e96039, 2014.
[19] A. Raveh, M. Margaliot, E. D. Sontag, and T. Tuller, “A model for
competition for ribosomes in the cell,” Journal of The Royal Society
Interface, vol. 13, no. 116, p. 20151062, 2016.
[20] S. Coogan and M. Arcak, “Dynamical properties of a compartmental
model for traffic networks,” in Proceedings of the 2014 American
Control Conference, pp. 2511–2516, 2014.

[21] G. Como, E. Lovisari, and K. Savla, “Throughput optimality and overload behavior of dynamical flow networks under monotone distributed
routing,” IEEE Transactions on Control of Network Systems, vol. 2,
pp. 57–67, March 2015.
[22] M.Vidyasagar, Nonlinear System Analysis. Society for Industrial and
Applied Mathematics, 2002.
[23] C. Desoer and M. Vidyasagar, Feedback systems: Input-output properties. Society for Industrial and Applied Mathematics, 2008.
[24] E. Lovisari, G. Como, A. Rantzer, and K. Savla, “Stability analysis
and control synthesis for dynamical transportation networks,” arXiv
preprint arXiv:1410.5956, 2014.
[25] E. Sontag, “Smooth stabilization implies coprime factorization,” IEEE
Transactions on Automatic Control, vol. 34, pp. 435–443, April 1989.
[26] E. D. Sontag and Y. Wang, “On characterizations of the input-to-state
stability property,” Systems & Control Letters, vol. 24, no. 5, pp. 351–
359, 1995.
[27] B. S. Rüffer, C. M. Kellett, and S. R. Weller, “Connection between
cooperative positive systems and integral input-to-state stability of
large-scale systems,” Automatica, vol. 46, no. 6, pp. 1019–1027, 2010.
[28] Z.-P. Jiang, I. M. Mareels, and Y. Wang, “A Lyapunov formulation
of the nonlinear small-gain theorem for interconnected ISS systems,”
Automatica, vol. 32, no. 8, pp. 1211 – 1215, 1996.
[29] S. N. Dashkovskiy, B. S. Rüffer, and F. R. Wirth, “Small gain theorems
for large scale systems and construction of ISS Lyapunov functions,”
SIAM Journal on Control and Optimization, vol. 48, no. 6, pp. 4089–
4118, 2010.
[30] E. D. Sontag, M. Margaliot, and T. Tuller, “On three generalizations
of contraction,” in IEEE 53rd Annual Conference on Decision and
Control (CDC), pp. 1539–1544, 2014.
[31] M. Margaliot, E. D. Sontag, and T. Tuller, “Contraction after small
transients,” Automatica, vol. 67, pp. 178–184, 2016.
[32] J. A. Jacquez and C. P. Simon, “Qualitative theory of compartmental
systems,” SIAM Review, vol. 35, no. 1, pp. 43–79, 1993.
[33] H. Maeda, S. Kodama, and Y. Ohta, “Asymptotic behavior of nonlinear
compartmental systems: nonoscillation and stability,” IEEE Transactions on Circuits and Systems, vol. 25, no. 6, pp. 372–378, 1978.
[34] P. Parrilo, Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization. PhD thesis, California
Institute of Technology, 2000.

