V.1. Polyèdres convexes fermés
(plutôt que cône-conv {v 1 , . . . , v k }). Le passage d’une description à l’autre se fait
par polarité : si K est un cône convexe fermé polyédrique de R n , son cône polaire
K
◦ := {s ∈ R
n
| |s, d 0 pour tout d ∈ K}
est encore un cône convexe fermé polyédrique de R n ; de cette manière :
K
◦ = cône {a 1 , . . . , a m } lorsque K est décrit comme en (5.5) ;
(5.7)
K ◦ = {x ∈ R n | |v i , x 0 pour tout i = 1, . . . , k}
lorsque K est décrit comme en (5.6) .
(5.8)
Ce que dit (5.7) est le lemme de Minkowski-Farkas (sa première forme du
moins) :
{x ∈ R n | |a i , x 0 pour i = 1, . . . , m} est contenu dans
{x ∈ R n | |b, x 0}
(5.9)
si et seulement si
b ∈ cône {a 1 , . . . , a m } .
(5.10)
Le plus petit sous-espace affine de R n contenant un polyèdre convexe fermé C
de R n s’appelle le sous-espace affine engendré par C ; on appelle dimension de C
(et on note dim C) la dimension de ce sous-espace affine engendré. L’intérieur de
C dans le sous-espace affine engendré par C est ce qu’on appelle l’intérieur relatif
de C ; il est noté ir C (ou int r C).
Le caractère borné ou non d’un polyèdre convexe fermé de R n est mesuré par
le cône asymptote (ou asymptotique) de C ; il s’agit de
C ∞ := {d ∈ R
n
| x 0 + td ∈ C pour tout t 0} .
(5.11)
Cet ensemble, qui se trouve être indépendant du x 0 choisi dans C, est un
cône convexe fermé polyédrique de R n ; il est réduit à {0} si et seulement si
C est borné. Dans l’exemple d’une description de C comme en (5.2) , C ∞ est
{x ∈ R n | Ax 0} .
Il y a une manière de décrire un polyèdre convexe fermé C de R n , complémentaire de celle donnée en (5.2), faisant apparaître la partie bornée et la partie non
bornée de C :
C = C 0 + C ∞ ,
(5.12)
où C 0 est un polyèdre convexe compact. On peut même poursuivre la décomposition en faisant C ∞ = K + L, où K est un cône convexe fermé polyédrique saillant
(i.e. K ∩ (−K) = {0}) et L un sous-espace vectoriel de R n .
167
(plutôt que cône-conv {v 1 , . . . , v k }). Le passage d’une description à l’autre se fait
par polarité : si K est un cône convexe fermé polyédrique de R n , son cône polaire
K
◦ := {s ∈ R
n
| |s, d 0 pour tout d ∈ K}
est encore un cône convexe fermé polyédrique de R n ; de cette manière :
K
◦ = cône {a 1 , . . . , a m } lorsque K est décrit comme en (5.5) ;
(5.7)
K ◦ = {x ∈ R n | |v i , x 0 pour tout i = 1, . . . , k}
lorsque K est décrit comme en (5.6) .
(5.8)
Ce que dit (5.7) est le lemme de Minkowski-Farkas (sa première forme du
moins) :
{x ∈ R n | |a i , x 0 pour i = 1, . . . , m} est contenu dans
{x ∈ R n | |b, x 0}
(5.9)
si et seulement si
b ∈ cône {a 1 , . . . , a m } .
(5.10)
Le plus petit sous-espace affine de R n contenant un polyèdre convexe fermé C
de R n s’appelle le sous-espace affine engendré par C ; on appelle dimension de C
(et on note dim C) la dimension de ce sous-espace affine engendré. L’intérieur de
C dans le sous-espace affine engendré par C est ce qu’on appelle l’intérieur relatif
de C ; il est noté ir C (ou int r C).
Le caractère borné ou non d’un polyèdre convexe fermé de R n est mesuré par
le cône asymptote (ou asymptotique) de C ; il s’agit de
C ∞ := {d ∈ R
n
| x 0 + td ∈ C pour tout t 0} .
(5.11)
Cet ensemble, qui se trouve être indépendant du x 0 choisi dans C, est un
cône convexe fermé polyédrique de R n ; il est réduit à {0} si et seulement si
C est borné. Dans l’exemple d’une description de C comme en (5.2) , C ∞ est
{x ∈ R n | Ax 0} .
Il y a une manière de décrire un polyèdre convexe fermé C de R n , complémentaire de celle donnée en (5.2), faisant apparaître la partie bornée et la partie non
bornée de C :
C = C 0 + C ∞ ,
(5.12)
où C 0 est un polyèdre convexe compact. On peut même poursuivre la décomposition en faisant C ∞ = K + L, où K est un cône convexe fermé polyédrique saillant
(i.e. K ∩ (−K) = {0}) et L un sous-espace vectoriel de R n .
167