SUFFICIENT CONDITION OF MAX-PLUS ELLIPSOIDAL

INVARIANT SET AND COMPUTATION OF FEEDBACK CONTROL

OF DISCRETE EVENT SYSTEMS

Mourad Ahmane and Laurent Truffet

Institut de Recherche en Communications et Cybern

´

etique de Nantes

IRCCyN, UMR-CNRS 6597,

´

Ecole Centrale Nantes

Max-plus algebra, geometric approach, set invariance, residuation.

Abstract:

Haar’s Lemma (1918) provides the algebraic characterization of the inclusion of polyhedral sets. This Lemma

has been involved many times in automatic control of linear dynamical systems when the constraint domains

(state and/or control) are polyhedrons. More recently, this Lemma has been used to characterize stochastic

comparison w.r.t linear orderings of Markov chains with different state spaces. Stochastic comparison is

involved in the simplification of complex stochastic systems in order to control the approximation error made.

In this paper we study the positive invariance of a max-plus ellipsoid by a max-plus linear dynamical system.

We remark that positive invariance of max-plus ellipsoid is a particular case of polyhedron inclusion and we

use Haar’s Lemma to derive sufficient condition for the positive invariance. As an application we propose a

net, 1989) where it is called extended Farkas’Lemma.

Let ≤

n

denotes the component-wise order on R

n

(i.e.

x ≤

n

y ⇐⇒ ∀i, x

i

≤ y

m

m

∃H ∈ R

m

m

communication protocols (TCP), computer networks,

dynamic programming, transportation networks (see

e.g. (Baccelli and al., 1992)) is now almost classical.

The geometric approach for the control of DES is one

of the main topics of research already mentioned by

(Cohen and al.,1999) which has not yet been so de-

veloped than in linear algebra.

positive invariance has been mainly developed by

(Wonham, 1985) in the case of vectorial subspaces

subject and references therein). It is known at least

since (Kalman and al., 1960) that stability in the sense

of Lyapuonv of classical linear systems has links with

the existence of a positively invariant ellipsoid

T

have explored and characterized other kind of posi-

tively invariant sets.

In (Ahmane and al., 2004) it has been shown that

the algebraic characterization of the inclusion of two

polyhedral sets provided by Haar’s Lemma is the fun-

damental notion for the characterization of the posi-

tive invariance of discrete-time Markov chains in par-

ticular and linear systems in general. This idea is

adapted here in the context of the control of Dis-

crete Event Systems (DES) using the properties of A-

with d ∈ N, x(n) is the state vector at time instant

n and A ∈ S

is the state matrix. The vectorial

equation (2) means that

the transpose operator and

with

with αa denotes the usual multiplication α × a.

In linear algebra, E(P, w, α) coincides with the notion

of ellipsoid.

The main results of this paper are as follows. First,

Using Haar’s Lemma (see Result 1), we obtain suffi-

cient condition under which the following assertion is

(resp.

) denotes the supremum w.r.t ≤ (resp. );

, ) is residuated iff f is

For any set S, (S, ⊕, ⊗, ε, e) is a semiring if (S, ⊕, ε)

is a commutative monoid, (S, ⊗, e) is a monoid, ⊗

(S, ⊗, e) is a commutative monoid, then the idempo-

tent semiring (S, ⊕, ⊗, ε, e) is said commutative.

(S, ⊕, ⊗, ε, e) is a an idempotent semifield

if (S, ⊕, ⊗, ε, e) is an idempotent semiring and

(S\{ε}, ⊗, e) is a group, i.e. (S\{ε}, ⊗, e) is a

monoid such that all its elements are invertible

(∀a ∈ S\{ε}, ∃a

: a ⊗ a

Also if (S\{ε}, ⊗, e) is a commutative monoid,

then the idempotent semifield (S, ⊕, ⊗, ε, e) is said

∀x, y ∈ S

⊕ y

, ∀s ∈ S, (s ⊗ x)

s ⊗ x

tiplication ⊗ are naturally extended to matrices with

compatible dimension. Any n × p matrix A is asso-

ciated with a (⊕, ⊗)-linear map A : S

. The

ring or an idempotent semifield, then (S, ⊕, ε) is an

idempotent monoid, which can be equiped with the

natural order relation ≤ defined by:

plete as a naturally ordered set and if the respec-

tive left and right multiplications, λ

: S → S,

pletion of an idempotent semifield. Let us note that

if a ∈ S is invertible then: a\b = a

We have by convention the following identities:

We suppose besides that (for a discussion to this topic,

see e.g. ((Baccelli and al., 1992, p. 163-164)):

By definition of / (idem for \) and properties of ⊤, ε

and of [7] we have for all a ∈ S:

vectors with compatible dimensions assuming that all

the elements of these matrices and vectors are in a

complete set S:

invariance (cf. Theorem 2). (Truffet, 2004) treated

necessary and sufficient conditions for the positive in-

variance of the max-plus ellipsoidal set previously de-

fined in the case where α = 1. As an application we

show that this sufficient characterization for the pos-

itive invariance of such sets allow us to determine a

max-plus linear state feedback control law ( F to be

determined).

Let us consider the following linear system (d, ⊗, A)

over a complete idempotent semiring (S, ⊕, ⊗, ε, e)

≤ A

(A ⊗ x)

E(P, w, α) defined by (10) is positively invariant

if there exists a d

× d

-matrix H such that the fol-

lowing conditions hold:

2

≤

with (b

senotes the canonical basis of R

P(Q, p) ⊆ P(Q, q),

where, by definition,

P(Q, ·) = {x ∈ R

|Qx ≤ ·}.

The matrix Q is defined by (18), and the d

dimensional vectors p and q are respectively de-

fined by:

∀i, j = 1, . . . , d.

Using Haar’s Lemma (cf. Result 1), with in our

case Φ = Ψ = Q in assertion (1), we obtain the

conditions (a), (b) and (c), and the proof is now

achieved. 

• α is a positive real number (α ∈ R

Remark 1 In the case where α is a non-negative

real number, the sufficient condition of Theorem 1

is also necessary because :

∀x ∈ S

⊗x

with A ∈ S

, B ∈ S

determined ( Any F is called a feedback) such that

the following assertion to be true:

plying an adequate control u that this state will remain

within the set E(P, w, α) at time instant n.

will then introduce the concept of the (A ⊕ B ⊗ F )-

invariance of the set E(P, w, α). For more details, see

such that the set E(P, w, α) is (A ⊕ B ⊗ F )-

invariant. In the following theorem, we give a suffi-

cient condition for the (A ⊕ B ⊗ F )-invariance of the

set E(P, w, α).

Theorem 2 Let us assume that the set E(P, w, α) is

not empty. The set E(P, w, α) is (A ⊕ B ⊗ F )-

invariant if there exists a d

× d

-matrix H such that

the following conditions hold:

where (b

lutions in g of the system of inequalities (27). This,

can be done by using the Γ-algorithm (Castillo and

al., 1999) pp. 161-162.

Step III:

The final step is to find all possible feedback F such

that:

where A, B are given matrices. The matrix G ∈ S

Example 1 Let us consider the following linear sys-

tem given over a complete idempotent semiring

(S, ⊕, ⊗, ε, e) = (R ∪ {−∞, +∞}, max, +, −∞, 0):

x(0) ∈ S

x(n) = A ⊗ x(n − 1) ⊕

Using (30):

Using (27):

The set of all solutions in g is:

and then by (29):

If the matrix A of the system satisfied the condition

A ≤ G, we can compute the matrix F using residua-

tion theory, then the equation (31) for example admits

the solution