Minimal half-spaces and external representation of tropical polyhedra

(1)

DOI 10.1007/s10801-010-0246-4

Minimal half-spaces and external representation of tropical polyhedra

Stéphane Gaubert·Ricardo D. Katz

Received: 11 August 2009 / Accepted: 1 July 2010 / Published online: 30 July 2010

Abstract We give a characterization of the minimal tropical half-spaces containing a given tropical polyhedron, from which we derive a counter-example showing that the number of such minimal half-spaces can be infinite, contradicting some statements which appeared in the tropical literature, and disproving a conjecture of F. Block and J. Yu. We also establish an analogue of the Minkowski–Weyl theorem, showing that a tropical polyhedron can be equivalently represented internally (in terms of extreme points and rays) or externally (in terms of half-spaces containing it). A canonical external representation of a polyhedron turns out to be provided by the extreme elements of its tropical polar. We characterize these extreme elements, showing in particular that they are determined by support vectors.

Keywords Max-plus semiring·Max-plus convexity·Tropical convexity· Polyhedra·Polytopes·Minkowski–Weyl theorem·Supporting half-spaces

1 Introduction

Max-plus or tropical convexity has been developed by several researchers under different names, with various motivations. It goes back at least to the work of Zim-

The first author was partially supported by the Arpege programme of the French National Agency of Research (ANR), project “ASOPT”, number ANR-08-SEGI-005 and by the Digiteo project DIM08

“PASO” number 3389.

S. Gaubert (

⁾

INRIA and Centre de Mathématiques Appliquées (CMAP), École Polytechnique, 91128 Palaiseau Cedex, France

e-mail:Stephane.Gaubert@inria.fr

R.D. Katz (

⁾

CONICET, Instituto de Matemática “Beppo Levi”, Universidad Nacional de Rosario, Avenida Pellegrini 250, 2000 Rosario, Argentina

e-mail:rkatz@fceia.unr.edu.ar

(2)

mermann [35]. It was studied by Litvinov, Maslov, and Shpiz [29], in relation to problems of calculus of variations, and by Cohen, Gaubert, and Quadrat [12,13], motivated by discrete event system problems (max-plus polyhedra represent invariant spaces of max-plus linear dynamical systems [11]). Some of this work was pursued with Singer (see [14]), with motivations from generalized convexity [32]. The work of Briec and Horvath [7] is also in the setting of generalized convexity. Develin and Sturmfels [16] pointed out some remarkable relations with tropical geometry, and developed a new approach, thinking of tropical polyhedra as polyhedral complexes in the usual sense. This was the starting point of several works of the same authors, of Joswig [26] and of Block and Yu [6]. Some of the previously mentioned researchers, and some other ones, including Allamigeon, Butkoviˇc, Goubault, Katz, Nitica, Meu- nier, Sergeev, Schneider, have recently made a number of works in the field, we refer the reader to [3,5,10,19–22,27,28,30] for a representative set of contributions.

A closed convex set can be represented classically in two different ways, either internally, in terms of extreme elements (extreme points and rays) and lineality space, or externally, as the intersection of (closed) half-spaces.

The max-plus or tropical analogue of the external representation, esspecially in the case of polyhedra, is the main object of this paper.

The existence of an external representation relies on separation arguments. In the max-plus setting, several separations theorems have been obtained, with various degrees of generality and precision, by Zimmermann [35], by Samborski˘ı and Shpiz [31], by Cohen, Gaubert, and Quadrat [12,13] with a further refinement in a work with Singer [14], and by Develin and Sturmfels [16]. In particular, the results of [12–14] yield a simple geometric construction of the separating half-space, showing the analogy with the Hilbert space case. This geometric approach was extended to the case of the separation of several convex sets by Gaubert and Sergeev [24], using a cyclic projection method. Briec and Horvath derived a separation theorem for two convex sets using a different approach [8].

The existence of an internal representation relies on Krein–Milman type theorems.

Results of this kind were established by Butkoviˇc, Schneider, and Sergeev [10] and by the authors [20], who also studied in [21] the analogue of the polar of a convex set, which consists of the set of inequalities satisfied by its elements.

Polyhedra are usually defined by the condition that they have a finite external or internal representation, the equivalence of both conditions being the classical Minkowski–Weyl theorem.

In the max-plus setting, a first result of this nature was established by Gaubert in [18, Chap. III, Theorem 1.2.2], who showed that a finitely generated max-plus cone can be characterized by finitely many max-plus linear inequalities. One element of the proof is an argument showing that the set of solutions of a system of max- plus linear equations is finitely generated, an observation which was already made by Butkoviˇc and Hegedus [9]. Some accounts in English of the result of [18] appeared in [2,19,23].

To address the same issue, Joswig [26] introduced the very interesting notion of minimal half-spaces (tropical half-spaces that are minimal for inclusion among the ones containing a given tropical polytope), he stated that the apex of such a tropical half-space is a vertex of the classical polyhedral complex arising from the polytope, and deduced that there are only finitely many such minimal half-spaces. This

(3)

statement was refined by a conjecture of Block and Yu, characterizing the minimal half-spaces, in the generic case [6, Conj. 14].

The finiteness of the number of minimal half-spaces is an appealing property, which is geometrically quite obvious in dimension 2. It came to us as a surprise that it does not hold in higher dimensions. We give here a counter-example (Example2 below), contradicting the finiteness of the number of minimal half-spaces containing a tropical polyhedron (Corollary 3.4 of [26]) and disproving Conjecture 14 of [6].

The analysis of the present counter-example is based on a general characterization of the minimal half-spaces, Theorem4below, the main result of this paper, which gives some answer to the question at the origin of the conjecture of Block and Yu.

In a preliminary section, we establish an analogue of the Minkowski–Weyl theorem (Theorem2), showing that a tropical polyhedron can be equivalently described either as the sum of the convex hull of finitely many points and of the cone generated by finitely many vectors, or as the intersection of finitely many half-spaces (there is no tropical analogue of the lineality space). The proof is based on the idea of [18]

(Theorem1below), which is combined with the results of [20].

In the final section, we characterize the extreme elements of the polar of a tropical polyhedral cone. The set of extreme elements of this polar has the property that any inequality satisfied by all the elements of the cone is a max-plus linear combination of the inequalities represented by these extreme elements, and it is the unique minimal set with this property (up to a scaling). In particular, these extreme elements provide a finite representation of the original polyhedron as the intersection of half-spaces.

Theorem5 below characterizes these extreme elements, showing in particular that each of them is determined by support vectors.

2 The tropical Minkowski–Weyl theorem

Let us first recall some basic definitions. The max-plus semiring, Rmax, is the set R∪ {−∞} equipped with the addition (a, b)→max(a, b) and the multiplication (a, b)→a+b. To emphasize the semiring structure, we writea⊕b:=max(a, b), ab:=a+b,0:= −∞and1:=0. The term “tropical” is now used essentially as a synonym of max-plus. The semiring operations are extended in the natural way to matrices over the max-plus semiring:(A⊕B)_ij:=A_ij⊕B_ij,(AB)_ij:=

kA_ikB_kj and(λA)ij :=λAij for all i, j, where A, B are matrices of compatible sizes and λ∈Rmax. We denote by e^k ∈Rⁿ_maxthe k-th unit vector, i.e. the vector defined by:

(e^k)_k:=1and(e^k)_h:=0ifh=k.

We considerRmaxequipped with the usual topology (resp. order), which can be defined by the metric:d(a, b):= |exp(a)−exp(b)|. The setRⁿmaxis equipped with the product topology (resp. order). Note that the semiring operations are continuous with respect to this topology.

A subsetV of Rⁿmax is said to be a max-plus or tropical cone if it is stable by max-plus linear combinations, meaning that

λu⊕μv∈V (1)

for allu, v∈V andλ, μ∈Rmax. Note that, in the max-plus setting, positivity con- straints are implicit because any scalarλ∈Rmaxsatisfiesλ≥0. As a consequence,

(4)

max-plus cones turn out to share many properties with classical convex cones. This analogy leads us to define max-plus convex subsetsC ofRⁿmaxby requiring them to be stable by max-plus convex combinations, meaning thatλu⊕μv∈C holds for all u, v∈C andλ, μ∈Rmaxsuch thatλ⊕μ=1. We denote by cone(X)the smallest cone containing a subsetX ofRⁿmax, and by co(X)the smallest convex set containing it. Therefore, cone(X)(resp. co(X)) is the set of all max-plus linear (resp.

convex) combinations of finitely many elements ofX. A coneV is said to be finitely generated if there exists a finite setX such thatV =cone(X), which equivalently means thatV = {Cw|w∈R^tmax}for some matrixC∈Rⁿmax^×^t.

A half-space ofRⁿ_maxis a set of the form H =

x∈Rⁿmax

1≤i≤n

a_ix_i≤

1≤j≤n

b_jx_j

,

wherea, b∈Rⁿmax, and an affine half-space ofRⁿmaxis a set of the form H =

x∈Rⁿmax

1≤i≤n

a_ix_i

⊕c≤

1≤j≤n

b_jx_j

⊕d

,

wherea, b∈Rⁿmaxandc, d∈Rmax. With the classical notation, the latter set can be written as

H = x∈Rⁿ_max|max

1max≤i≤nai+xi, c

≤max

1max≤j≤nbj+xj, d

. Note that half-spaces are max-plus cones.

Classical polyhedra can be defined either as a finite intersection of affine half- spaces, or in terms of finite sets of vertices and rays, i.e. as the Minkowski sum of a polytope and a finitely generated cone. Here we adopt the first approach and define a max-plus or tropical polyhedron as the intersection of finitely many affine half- spaces. We warn the reader that our notion of polyhedra is more general than the one used in [16] (the latter reference deals with max-plus cones having a finite generating family consisting of vectors with finite entries).

The following “conic” form of the Minkowski–Weyl theorem is equivalent to a result established in [18], showing that a finitely generated max-plus cone is characterized by finitely many max-plus linear equalities. This result was reproduced (but without its proof) in the surveys [2,19,23]. For the convenience of the reader, we include the proof here. The “if” part is equivalent to the existence of a finite set of generators of a system of max-plus linear equations, which was first shown in [9].

There has recently been progress on these issues, leading to a faster algorithm, see [3,4].

Theorem 1 (Compare with [18, Chap. III, Theorem 1.2.2] and [23, Theorem 9]) A max-plus cone is finitely generated if, and only if, it is the intersection of finitely many half-spaces.

Proof LetV ⊂Rⁿ_maxbe an intersection of phalf-spaces. We next prove thatV is finitely generated by induction onp.

(5)

Whenp=1, asV = {x∈Rⁿmax|

1≤i≤na_ix_i ≤

1≤j≤nb_jx_j} =

1≤j≤nVj, where

Vj:=

x∈Rⁿmaxa_ix_i≤b_jx_j, ∀i=1, . . . , n ,

to prove thatV is finitely generated it suffices to show that the conesVjare all finitely generated. Ifbj=0andaj≤bj, then it can be checked thatVj=cone(Xj), where Xj:= {bjeⁱ⊕aie^j|i=1, . . . , n}. Ifbj=0oraj> bj, thenVj=cone(Xj), where Xj:= {eⁱ|a_i=0}.

Assume now that the intersection ofphalf-spaces is finitely generated and let V :=

x∈RⁿmaxAx≤Bx

∩

x∈Rⁿmaxax≤bx ,

where A, B ∈ R^pmax^×ⁿ and a, b∈R¹max^×ⁿ, be an intersection of p +1 half-spaces.

Then, we know that there exists a matrix C ∈Rⁿmax^×^t, for some t ∈N, such that {x ∈Rⁿ_max|Ax≤Bx} = {Cw|w∈R^t_max}. AsH := {w∈R^t_max|aCw≤bCw} is a half-space, there exists another matrix D∈R^t×r_max, for somer ∈N, such that H = {Du|u∈R^rmax}. Therefore,V = {Cw|aCw≤bCw} = {CDu|u∈R^rmax}is finitely generated.

Conversely, let V = {Cw|w∈R^tmax}, where C ∈Rⁿmax^×^t, be a finitely generated cone. Then, as finitely generated cones are closed (see [10, Cor. 27] or [20, Lemma 2.20]), it follows from the separation theorem for closed cones of [14,31, 35] thatV is the intersection of the half-spaces ofRⁿ_maxin which it is contained. Note that a half-space{x∈Rⁿmax|ax≤bx}containsV if, and only if, the row vectorsa andbsatisfyaC≤bC. Since{(a, b)∈R¹max^×²ⁿ|aC≤bC}is a finite intersection of half-spaces, we know by the first part of the proof that there exist matricesAandB such that(a, b)satisfiesaC≤bCif, and only if,(a, b)is a max-plus linear combination of the rows of the matrix(A, B). Therefore,V = {x∈Rⁿmax|Ax≤Bx}, i.e.

V is an intersection of finitely many half-spaces.

Recall that the recession cone [20] of a max-plus convex set C consists of the vectorsufor which there exists a vectorx∈Csuch thatx⊕λu∈C for allλ∈Rmax. This property is known to be independent of the choice ofx∈C as soon as C is closed.

Given a max-plus coneV ⊂Rⁿ_max, a non-zero vectorv∈V is said to be an extreme vector ofV if the following property is satisfied

v=u⊕w, u, w∈V ⇒v=uorv=w.

The set of scalar multiples ofvis an extreme ray ofV. Given a max-plus convex set C⊂Rⁿmax, a vectorv∈C is said to be an extreme point ofC if

v=λu⊕μw, u, w∈C, λ, μ∈Rmax, λ⊕μ=1⇒v=uorv=w.

As a corollary of Theorem1we obtain a max-plus analogue of the Minkowski–

Weyl theorem, the first part of which was announced in [19]. A picture illustrating the decomposition can be found in [19,20].

(6)

Theorem 2 (Tropical Minkowski–Weyl Theorem) The max-plus polyhedra are pre- cisely the sets of the form

co(Z)⊕cone(Y),

whereZ,Y are finite sets. The set cone(Y)in such a representation is unique, it coincides with the recession cone of the polyhedron. Any minimal setY in such a representation can be obtained by selecting precisely one non-zero vector in each extreme ray of the recession cone of the polyhedron. The minimal setZ in such a representation consists of the extreme points of the polyhedron.

Here,⊕denotes the max-plus Minkowski sum of two subsets, which is defined as the set of max-plus sums of a vector of the first set and a vector of the second one.

Proof LetC ⊂Rⁿ_maxbe a max-plus polyhedron. Then, there exist matricesA, Band column vectorsc, d such thatC = {x ∈Rⁿ_max|Ax ⊕c≤Bx⊕d}. Consider the max-plus cone

V :=

x λ

∈Rⁿ⁺_max¹Ax⊕cλ≤Bx⊕dλ

.

SinceV is an intersection of finitely many half-spaces, by Theorem1it follows that V =cone(X), for some finite subsetX ofRⁿmax⁺¹. Note that we can assume, without loss of generality, that

X = z

1

∈Rⁿmax⁺¹z∈Z

∪ y

0

∈Rⁿmax⁺¹y∈Y

(2) for some finite subsetsZ,Y ofRⁿmax. Therefore, we have

x∈C ⇐⇒

x 1

∈V ⇐⇒

x 1

=

⎛

⎝

z∈Z

λz

z 1

⎞⎠⊕

⎛

⎝

y∈Y

λy

y 0

⎞⎠

⇐⇒ x=

z∈Z

λ_zz

⊕

y∈Y

λ_yy

,

z∈Z

λ_z=1

⇐⇒ x∈co(Z)⊕cone(Y), which shows thatC =co(Z)⊕cone(Y).

Conversely, letC =co(Z)⊕cone(Y), whereZ,Y are finite subsets ofRⁿmax. Note thatxbelongs toC if, and only if,_x

1

belongs toV :=cone(X), whereX is the finite subset ofRⁿmax⁺¹defined in (2). SinceV is a finitely generated cone, we know by Theorem1that there exist matricesA, B and column vectorsc, d such thatV = {_x

λ

∈Rⁿmax⁺¹|Ax⊕cλ≤Bx⊕dλ}. Therefore,C = {x∈Rⁿmax|Ax⊕c≤Bx⊕d}, i.e.C is a max-plus polyhedron.

Now letC =co(Z)⊕cone(Y)be a max-plus polyhedron. From the definition of recession cones, it readily follows that cone(Y)is contained in the recession cone ofC. Assume thatuis a vector in the recession cone ofC. By the first part of the

(7)

proof, if we defineV :=cone(X), where X is the finite subset ofRⁿmax⁺¹ defined in (2), then there exist matricesA, B and column vectorsc, d such thatV = {_x

λ

∈ Rⁿ_max⁺¹|Ax⊕cλ≤Bx⊕dλ}andC = {x∈Rⁿ_max|Ax⊕c≤Bx⊕d}. Sinceuis in the recession cone ofC, there existsx∈C such thatx⊕λu∈C for allλ∈Rmax. This means thatA(x⊕λu)⊕c≤B(x⊕λu)⊕d for allλ∈Rmax, so we conclude thatAu≤Bu. Therefore,_u

0

∈V =cone(X), which implies thatu∈cone(Y)by the definition ofX. In consequence, cone(Y)is equal to the recession cone ofC.

Assume thatzis an extreme point ofC. We next show that necessarilyz∈Z. To this end, by the definition of extreme points, it suffices to show thatz∈co(Z). To the contrary, assume thatz=x⊕u, wherex∈co(Z),u∈cone(Y)andx_i< u_ifor somei∈ {1, . . . , n}. Then, given any non-zero scalarλ <1, we havez=(x⊕λu)⊕ λ(x⊕(−λ)u), which contradicts the fact thatzis an extreme point of C because x⊕λuandx⊕(−λ)uare two elements ofC different fromz. Therefore, any extreme point ofC must belong toZ.

Now lety be an extreme vector of the recession cone ofC. Since the recession cone ofC is equal to cone(Y), by the definition of extreme vectors, it follows that a non-zero scalar multiple ofymust belong toY.

Finally, sinceC is closed because it is a finite intersection of closed sets, from Theorem 3.3 of [20] it follows that any minimal setY in the representation C = co(Z)⊕cone(Y)can be obtained by selecting precisely one non-zero vector in each extreme ray of the recession cone ofC, and a minimal setZ in this representation is

given by the extreme points ofC.

3 The partially ordered set of half-spaces

In this section we prove the existence of minimal half-spaces with respect to a max- plus coneV. With this aim, it is convenient to start with the following lemma which shows that any half-spaceH ofRⁿmaxcan be written as

H =

x∈Rⁿmax

i∈I

a_ix_i≤

j∈J

a_jx_j

,

whereI andJ are disjoint subsets of{1, . . . , n}anda_k∈Rfor allk∈I∪J. Hence- forth, all the half-spaces we consider will be written in this way.

Lemma 1 Leta, b, c, d∈Rmax. Then,

{x∈Rmax|ax⊕c≤bx⊕d} = {x∈Rmax|ax⊕c≤d} ifa > b, and

{x∈Rmax|ax⊕c≤bx⊕d} = {x∈Rmax|c≤bx⊕d} ifa≤b.

(8)

Proof We only prove the casea > bbecause the other one is straightforward.

Assume thatax⊕c≤bx⊕d. Ifx=0, necessarilyc≤dand thusax⊕c=c≤d. Ifx=0, then, asax⊕c≥ax > bxandax⊕c≤bx⊕d, it follows thatax⊕c≤d. Conversely, assume thatax⊕c≤d. Then, we haveax⊕c≤d≤bx⊕d. Givenv∈RⁿmaxandV ⊂Rⁿmax, the supports ofvandV are respectively defined by

suppv:= {k|v_k=0} and suppV :=

v∈V

suppv.

We shall say that a max-plus coneV ⊂Rⁿmaxhas full support if suppV = {1, . . . , n}.

For any non-zero scalarλ∈Rmax, we defineλ⁻:= −λ, and we extend this notation to vectors ofRⁿmaxwith only finite entries, so thatx⁻represents the vector with entries

−xi fori∈ {1, . . . , n}. Lemma 2 Let

H :=

x∈Rⁿmax

i∈I

aixi≤

j∈J

ajxj

and

H:=

x∈Rⁿ_max

i∈I

b_ix_i≤

j∈J

b_jx_j

be two half-spaces. Then, whenI = ∅,H⊂H if, and only if,I⊂I,J⊂J and b_j(b_i)⁻≤a_j(a_i)⁻for alli∈I andj∈J.

Proof (⇒)Assume thatI ⊂I. Pick any i∈I \I. Then, eⁱ ∈H and eⁱ ∈/H, which contradicts the fact thatH⊂H. Therefore,I⊂I.

Now assume thatJ⊂J. Pick anyj∈J\J andi∈I⊂I, and define the vector x∈Rⁿmaxby

xk:=

b_k⁻ ifk∈ {i, j},

0 otherwise. (3)

Then,x∈Handx /∈H, which is a contradiction. Therefore,J⊂J.

Finally, since the vectorx defined in (3) belongs toH for anyi∈I ⊂I and j∈J, it follows that it also belongs toH and thusa_i(b_i)⁻≤a_j(b_j)⁻. Therefore, bj(bi)⁻≤aj(ai)⁻for alli∈I andj∈J.

(⇐)Since

x∈H⇒b_ix_i≤

j∈J

b_jx_j, ∀i∈I⇒b_ix_i≤

j∈J

b_jx_j,∀i∈I

⇒x_i≤

j∈J

b_j(b_i)⁻x_j, ∀i∈I⇒x_i≤

j∈J

a_j(a_i)⁻x_j, ∀i∈I

⇒aixi≤

j∈J

ajxj, ∀i∈I⇒aixi≤

j∈J

ajxj, ∀i∈I⇒x∈H,

it follows thatH⊂H.

(9)

Lemma 3 LetV ⊂Rⁿmax be a max-plus cone with full support and{Hr}r∈N be a decreasing sequence of half-spaces such that V ⊂Hr for all r∈N. Then, there exists a half-spaceH such thatH =

r∈NHr. Proof Assume that

Hr=

x∈Rⁿmax

i∈Ir

a_i^rx_i≤

j∈Jr

a^r_jx_j

,

where for allr∈N,Ir andJr are disjoint subsets of{1, . . . , n}anda^r_k∈Rfor all k∈I_r∪J_r. By Lemma2we may assume, without loss of generality, that there exist I, J⊂ {1, . . . , n}such thatI_r=I andJ_r =J for allr∈N. IfI= ∅, we haveHr= Rⁿmaxfor allr∈N, so in this case the result is obvious. We next consider the case I= ∅. Note that in this case we also haveJ= ∅, becauseV ⊂Hr for allr∈Nand suppV = {1, . . . , n}.

We may also assume, without loss of generality, that

j∈Ja^r_j=1for allr∈N.

Then, since suppV = {1, . . . , n}and

i∈Ia_i^rx_i ≤

j∈Ja^r_jx_j forr∈Nandx∈V, it follows that the sequence{a_i^r}r∈Nis bounded from above for alli∈I. Therefore, we may assume, taking sub-sequences if necessary, that there existsai∈Rmaxsuch that limr→∞a^r_i =ai fori∈I.

We claim thatai=0for alli∈I. To the contrary, assume thatah=0for some h∈I. Since by Lemma2we havea_j^r(a_h^r)⁻≤a_j¹(a_h¹)⁻for allj ∈J andr∈N, this implies that limr→∞a_j^r =0for allj∈J, which contradicts the fact thatJ= ∅and

j∈Ja_j^r=1for allr∈N. This proves our claim.

Since

j∈Ja_j^r =1 for all r∈N, the sequence {a_j^r}r∈N is also bounded from above for allj ∈J. Then, taking sub-sequences if necessary, we may assume that there existsa_j ∈Rmaxsuch that limr→∞a^r_j=a_j for all j ∈J. If we defineJ:=

{j∈J|a_j=0}and H :=

x∈Rⁿmax

i∈I

a_ix_i≤

j∈J

a_jx_j

,

then it follows thatH =

r∈NHr. Indeed, ifx∈

r∈NHr, we have

i∈I

aixi= lim

r→∞

i∈I

a_i^rxi

≤ lim

r→∞

j∈J

a^r_jxj

=

j∈J

ajxj,

and thus x ∈ H. Therefore,

r∈NHr ⊂ H. Conversely, since J ⊂ J and aj(ai)⁻≤a_j^r(a_i^r)⁻ for all i∈I, j ∈J and r ∈N, by Lemma 2 it follows that H ⊂Hr for allr∈N. Therefore, we also haveH ⊂

r∈NHr.

Remark 1 Lemma3 does not hold if V does not have full support. For instance, consider

V =

x∈R³maxx₂=0, x₁≤x₃

(10)

and the decreasing sequence of half-spaces Hr=

x∈R³maxx₁⊕rx₂≤x₃ , wherer∈N. Then,

r∈NHr=V, butV is not a half-space ofR³max.

Theorem 3 LetV ⊂Rⁿmaxbe a max-plus cone with full support. IfV is contained in the half-spaceH, then there exists a half-spaceHsuch thatV ⊂H⊂H and His minimal for inclusion with respect to this property.

Proof By Zorn’s Lemma it suffices to show that for any chain {Hα}α∈Δ of half- spaces which satisfiesV ⊂Hα ⊂H for allα∈Δ, there exists a half-spaceH such thatH=

α∈ΔHα.

According to Lemma2, we may assume that Hα=

x∈Rⁿ_max

i∈I

a_i^αx_i≤

j∈J

a_j^αx_j

for allα∈Δ, where I andJ are disjoint subsets of {1, . . . , n}anda^α_k ∈Rfor all k∈I∪J. Again, ifI= ∅the previous assertion is trivial, so assumeI= ∅. Consider any sequence{α_r}r∈N⊂Δsuch that the sequence{a_j^α^r(a_i^α^r)⁻}r∈Nis decreasing and

rlim→∞a^α_j^r a_i^α^r₋

= inf

α∈Δa_j^α a^α_i₋

, (4)

for alli∈I andj ∈J. Then, by Lemma3there exists a half-spaceH such that H=

r∈NHα_r. Since (4) is satisfied, by Lemma 2, for any α∈Δthere exists r∈Nsuch thatHα_r ⊂Hα. Therefore, we haveH=

α∈ΔHα.

As a consequence of Theorem3 and the separation theorem for closed cones of [14,31,35], it follows that any closed coneV with full support can be expressed as the intersection of a family of minimal half-spaces with respect toV. WhenV is finitely generated, by Theorem1we conclude that it is possible to select a finite number of minimal half-spaces with respect toV such that their intersection is equal toV. However, like in the classical case, even in the finitely generated case, the number of minimal half-spaces with respect toV need not be finite, as it is shown in the next section.

4 Characterization of minimal half-spaces

Throughout this section,V ⊂Rⁿ_maxwill represent a fixed max-plus cone generated by the vectors v^r ∈Rⁿ_max, where r=1, . . . , p. For the sake of simplicity, in this section we shall assume that all the vectors we consider have only finite entries. We next recall basic definitions and properties related to the natural cell decomposition ofRⁿmaxinduced by the generators ofV. We refer the reader to [16] for a complete presentation, but we warn that the results of [16] are in the setting of the min-plus

(11)

semiringRmin:=(R∪ {+∞},min,+), which is however equivalent to the setting considered here.

We define the type of a vectorx∈Rⁿ_maxrelative to the generatorsv^r as then-tuple type(x)=(S1(x), . . . , Sn(x))of subsetsSj(x)⊂ {1, . . . , p}defined as follows:

S_j(x):=

r|v_j^r(x_j)⁻=

1≤k≤n

v_k^r(x_k)⁻

. (5)

Note thatv^r_j(x_j)⁻<

1≤k≤nv_k^r(x_k)⁻ ifr /∈S_j(x)and that any r∈ {1, . . . , p}belongs to someS_j(x).

Given ann-tupleS=(S₁, . . . , S_n)of subsets of{1, . . . , p}, consider like in [16]

the setXSof all the vectors whose type containsS, i.e.

XS:=

x∈RⁿmaxSj⊂Sj(x), ∀j=1, . . . , n

. (6)

Lemma 10 of [16] shows that the setsX_S are closed convex polyhedra (both in the max-plus and usual sense) which are given by

X_S=

x∈Rⁿmaxx_jv_i^r≤x_iv_j^r, ∀i, j∈ {1, . . . , n}withr∈S_j .

The natural cell decomposition ofRⁿ_maxinduced by the generators of V is the col- lection of convex polyhedraXS, whereSranges over all the possible types. This cell decomposition has in particular the property thatV is the union of its bounded cells, where a cell is said to be bounded if it is bounded in the(n−1)-dimensional max-plus or tropical projective spaceRⁿ/(1, . . . ,1)R(see [16] for details).

Given a cellX_S, if we define the undirected graphG_Swith set of nodes{1, . . . , n} and an edge connecting the nodesiandj if and only ifS_i∩S_j= ∅, then by Proposi- tion 17 of [16] the dimension ofX_Sis given by the number of connected components ofG_S (in [16] the dimension ofX_S is one less the one considered here because it refers to the projective space). Any non-zero vector in a cell of dimension one, which is therefore of the form{λx|λ∈Rmax}for some x∈Rⁿ, is called a vertex of the natural cell decomposition.

Example 1 Consider the max-plus coneV ⊂R³max generated by the vectors:v¹= (1,2,3)^T,v²=(2,4,6)^T andv³=(3,6,9)^T. This cone is represented on the left- hand side of Fig. 1 by the bounded dark gray region together with the two line segments joining the pointsv¹ andv³ to it. On the same figure we show the type of a vector, for each cell X_S contained in V. For instance, the type of the vectora =(0,1,3)^T is S=type(a)=({1},{1,2},{2,3}). Then, since the graph G_S has only one connected component,a is a vertex. If we takeb=(0,1,2.5)^T, then S=type(b)=({1},{1},{2,3})so that in this case the cellXSis two-dimensional. In Fig.1this cell is represented by the line segment which connects the pointsv¹anda.

The natural cell decomposition ofR³maxinduced by the generators ofV has six vertices, fifteen two-dimensional cells (six of them bounded) and ten three-dimensional cells (only one of them bounded, which is represented by the bounded dark gray region labeled by the typeS=({1},{2},{3})on the left-hand side of Fig.1).

(12)

Fig. 1 Illustration of the combinatorial types (left) and of the natural cell decomposition ofR³maxinduced by the generators of a max-plus cone (right), as defined by Develin and Sturmfels [16]

A simple geometric construction of the natural cell decomposition ofRⁿ_max induced by the generators ofV can be obtained if we consider the min-plus hyperplanes whose apices are the generators ofV. Givena∈Rⁿ_max, the min-plus hyperplane with apexa⁻is the set of vectorsx∈Rⁿ_maxsuch that the minimum min1≤i≤nai+xi is attained at least twice (we refer the reader to [26] for details on hyperplanes and their relation with half-spaces). By Proposition 16 of [16], the cell decomposition induced by the generators ofV is the common refinement of the fans defined by thepmin- plus hyperplanes whose apices are the vectorsv^r, forr=1, . . . , p. In the case of our example, these min-plus hyperplanes are represented on the right-hand side of Fig.1, where it can be seen thatV is the union of the bounded cells.

Assume that

H =

x∈Rⁿmax

i∈I

a_ix_i≤

j∈J

a_jx_j

is a minimal half-space with respect to V. Then, we necessarily have I ∪J = {1, . . . , n}. Indeed, ifh /∈I ∪J, defininga_h=min1≤r≤p{

j∈Ja_jv_j^r(v^r_h)⁻}, it follows that the half-space

H=

x∈Rⁿmaxa_hx_h⊕

i∈I

a_ix_i

≤

j∈J

a_jx_j

containsV because it contains its generators, which by Lemma2contradicts the minimality ofH. For this reason, in this section we shall assume thatI∪J= {1, . . . , n} since we are interested in studying minimal half-spaces, and like in [26] we shall call the vectora⁻∈H ⊂Rⁿmaxthe apex ofH.

(13)

The following lemma gives a necessary and sufficient condition forV to be contained in a half-space in terms of the type of its apex.

Lemma 4 The max-plus coneV is contained in the half-space H =

x∈Rⁿ_max

i∈I

aixi≤

j∈J

ajxj

with apexa⁻if, and only if,

j∈JSj(a⁻)= {1, . . . , p}.

Proof Assume that

j∈JSj(a⁻)= {1, . . . , p}. Then, there existsr∈ {1, . . . , p}such thatr /∈S_j(a⁻)for allj ∈J, and soa_jv^r_j<

1≤k≤na_kv^r_k for allj∈J. Therefore, we have

j∈J

a_jv^r_j<

1≤k≤n

a_kv^r_k=

i∈I

a_iv_i^r,

which means thatv^r does not belong toH and soV is not contained inH. This shows the “only if” part of the lemma.

Now assume that

j∈JS_j(a⁻)= {1, . . . , p}. Then, for eachr∈ {1, . . . , p}there existsj∈J such thatr∈Sj(a⁻), which means thatajv_j^r =

1≤k≤nakv^r_k. There- fore, we have

i∈I

aiv_i^r≤

1≤k≤n

akv^r_k=

j∈J

ajv_j^r.

Since this holds for allr∈ {1, . . . , p}, it follows thatH contains the generators of V, and thusV is contained inH. This proves the “if” part of the lemma.

Now we can characterize the minimality of a half-space with respect toV in terms of the type of its apex.

Theorem 4 The half-space H =

x∈Rⁿ_max

i∈I

a_ix_i≤

j∈J

a_jx_j

with apex a⁻ is minimal with respect to the max-plus cone V if, and only if, the following conditions are satisfied:

(i) For eachi∈I there existsj∈J such thatS_i(a⁻)∩S_j(a⁻)= ∅, (ii) For eachj ∈Jthere existsi∈I such thatS_i(a⁻)∩S_j(a⁻)⊂

k∈J\{j}S_k(a⁻), (iii)

j∈JS_j(a⁻)= {1, . . . , p}.

Proof IfH is minimal with respect toV, for eachi∈I there existsr∈ {1, . . . , p} such that a_iv_i^r =

j∈Ja_jv_j^r because otherwise there would exist δ > 0 such thatδa_iv_i^r⊕(

h∈I\{i}a_hv_h^r)≤

j∈Ja_jv^r_j for allr∈ {1, . . . , p}, contradicting by Lemma2the minimality ofH. Therefore, for eachi∈I there existr∈ {1, . . . , p}

(14)

andj ∈J such thata_iv^r_i =a_jv_j^r ≥a_kv^r_k for allk, which implies thatr∈S_i(a⁻)∩ S_j(a⁻)and soS_i(a⁻)∩S_j(a⁻)= ∅.

Analogously, if H is minimal with respect to V, for each j ∈J there exists r∈ {1, . . . , p}such that

i∈Ia_iv_i^r=a_jv_j^r>

k∈J\{j}a_kv^r_k. Otherwise, there would existδ <0 such that

i∈Ia_iv^r_i ≤δa_jv_j^r ⊕(

k∈J\{j}a_kv^r_k)for all r∈ {1, . . . , p}, which by Lemma 2 contradicts the minimality of H. Therefore, for each j ∈J there existr∈ {1, . . . , n}andi∈I such thataiv_i^r =ajv_j^r ≥akv_k^r for all k, where the inequality is strict fork∈J \ {j}, which implies thatr∈S_i(a⁻)∩S_j(a⁻)but r /∈

k∈J\{j}S_k(a⁻).

Finally, since any minimal half-space with respect toV contains in particularV, it follows that

j∈JSj(a⁻)= {1, . . . , p}by Lemma4. This completes the proof of the “only if” part of the theorem.

Now assume that the three conditions of the theorem are satisfied. By Lemma4, Condition (iii) implies thatV is contained inH. Let

H=

x∈Rⁿ_max

i∈I

b_ix_i≤

j∈J

b_jx_j

be a minimal half-space with respect toV contained in H, which we know exists by Theorem 3. Then, since H⊂H , by Lemma 2 we haveI ⊂I,J⊂J and b_j(b_i)⁻≤a_j(a_i)⁻for alli∈I andj∈J.

We first show thatI=I, and thusJ=J. To the contrary, assume thatI =I and leth∈I\I⊂J. Then, by Condition (ii), there existl∈I andr∈ {1, . . . , p} such thata_lv_l^r=a_hv^r_h> a_kv^r_kfor allk∈J\ {h}. Therefore, sinceb_j(b_i)⁻≤a_j(a_i)⁻ for alli∈I andj∈J, we have

v_l^r>

k∈J\{h}

a_k(a_l)⁻v_k^r≥

k∈J

a_k(a_l)⁻v_k^r≥

k∈J

b_k(b_l)⁻v^r_k

and so

i∈I

biv_i^r≥

i∈I

biv^r_i ≥blv_l^r>

k∈J

bkv_k^r ,

contradicting the fact thatv^r ∈V ⊂H. Therefore, we conclude thatI =I and J=J.

Note that by Conditions (i) and (ii), it follows thatSk(a⁻)= ∅for allk. This implies, by the covering theorem of Vorobyev [33, Theorem 2.6] and Zimmermann [34, Chap. 3] (see [1] for a complete recent discussion, including generalizations; see also Corollary 12 and Theorem 15 of [16]), that the apexa⁻ ofH belongs to V. Therefore, sinceV ⊂H, we have

i∈Ib_i(a_i)⁻≤

j∈Jb_j(a_j)⁻. Without loss of generality, we may assume that

i∈Ib_i(a_i)⁻≤

j∈Jb_j(a_j)⁻=1. Then, since bj(aj)⁻≤bi(ai)⁻for alli∈I andj ∈J, we must havebi(ai)⁻=1, i.e.ai=bi, for alli∈I.

Now assume thata =b. Then, there exists j ∈J such that b_j < a_j (note that b_k≤a_k for allk∈J because

k∈Jb_k(a_k)⁻=1), and by Condition (ii) there exist