ANALYSE CONVEXE

Dr Adama COULIBALY
UFR de Mathématiques et Informatique,
Université de Cocody, 22 BP 582 Abidjan 22, Côte d’Ivoire.

20 mars 2012
2
Table des matières

1 Ensembles convexes 5
1.1 Sous espaces affines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Ensembles convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.2 Propriétés algébriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.3 Propriétés topologiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3 Enveloppes convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 Points extrêmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2 Projection et Séparation 17
2.1 Projection sur un convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Séparation de deux ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3 Cônes convexes 27
3.1 Généralités sur les cônes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Cônes asymptotes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3 Cônes polaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.4 Cônes polyédriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.5 Cônes tangents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.6 Cônes normaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

4 Fonctions convexes 49
4.1 Fonctions convexes d’une variable réelle . . . . . . . . . . . . . . . . . . . . . . . . 49
4.2 Fonctions convexes à plusieurs variables . . . . . . . . . . . . . . . . . . . . . . . . 51
4.2.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.2.2 Opération sur les fonctions convexes . . . . . . . . . . . . . . . . . . . . . 55
4.2.3 Quelques fonctions convexes particulières . . . . . . . . . . . . . . . . . . . 58
4.2.4 Caractérisation des fonctions convexes différentiables . . . . . . . . . . . . 60

5 Notions sur la convexité généralisée 65

5.1 Fonctions quasi convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.2 Fonctions pseudoconvexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

3
4 TABLE DES MATIÈRES
Chapitre 1

Ensembles convexes

Le cadre général de ce cours est un espace vectoriel réel de dimension n. On peut donc sans
perdre de généralités considérer l’espace vectoriel réel Rn .

1.1 Sous espaces affines

Définition 1.1.1 On appelle combinaison linéaire affine de xi : i = 1, · · · , k des points de Rn ,
P P
toute combinaison linéaire x = ki=1 λi xi , avec λi ∈ R ∀ i = 1, · · · , k et ki=1 λi = 1.

Définition 1.1.2 Etant donné M ⊂ Rn , M 6= ∅, on dit que M est un sous espace affine (ou une
variété) de Rn , si M est stable par combinaison linéaire affine. C’est-à-dire :

∀ x y ∈ M, ∀α ∈ R, (1 − α)x + αy ∈ M.

Proposition 1.1.1 Pour un sous ensemble non vide de Rn , les conditions suivantes sont équivalentes :
1) M est un sous espace affine de Rn
2) Il existe un sous espace vectoriel V unique de Rn tel que :

∀a ∈ M, M = a + V = {a + v : v ∈ V }.

(Tout translaté de V par un élément de M est un élément de M .

Preuve : Supposons que M est un sous espace affine de Rn et soit x ∈ M . Posons V = M − a =
{x − a : x ∈ M }.
i) 0 ∈ V
ii) ∀ α ∈ R, ∀ x − a ∈ V, α(x − a) = [(1 − α)a + αx] − a ∈ V
iii) ∀ x − a, y − a ∈ V, (x − a) + (y − a) = 2[( 21 x + 21 y) − a] ∈ V
Donc V est un sous espace vectoriel et M = a + V .
Il reste à montrer que V ne depend pas de a.
Supposons que b ∈ M , W un sous espace vectoriel tel que M = b + W .
0 ∈ W = M − b = a − b + V . On a alors −(a − b) ∈ V et donc (a − b) ∈ V . Par suite
W =a−b+V ⊂V.
De même on montre que V ⊂ W . D’où V = W .
Soit b ∈ M
b + V = a + (b − a) + V ⊂ a + V + V ⊂ a + V
a + V = b + (a − b) + V = b + [−(b − a)] + V ⊂ b + V + V ⊂ b + V
Donc b + V = a + V = M . ¤

5
6 CHAPITRE 1. ENSEMBLES CONVEXES

Définition 1.1.3 Soit M un sous espace affine de Rn . Le sous espace vectoriel V vérifiant :
∀ a ∈ M, M = a + V est appelé la direction de M . La dimension de V est la dimension de M .

Exemple 1.1.1 a) Soit a ∈ Rn et d un élément non nul de Rn . D = a + Rd est la droite affine

de Rn passant par a et de vecteur directeur d.

b) Soit f un endomorphisme de Rn et (a, b) ∈ Rn2 tel que f (a) = b. M = {x ∈ Rn : f (x) = b}

est le sous espace affine de Rn passant a et de direction V = ker f .

On montre facilement que

Proposition 1.1.2 M est un sous espace affine si et seulement si M contient toute combinaison
linéaire affine de toute famille finie de ses points.

Proposition 1.1.3 Si {Mi }i∈I est une famille de sous espaces affines d’intersection non vide,
alors ∩i∈I Mi est un sous espace affine.

Preuve : Prendre a ∈ ∩i∈I Mi . Les éléments Ei = Mi − a sont alors des sous espaces vectoriels et
donc M = ∩i∈I Mi aussi qui n’est rien d’autre que ∩i∈I Mi − a. ¤
Etant donné S ⊂ Rn , on considère l’ensemble des sous espaces affines contenant S. Cet ensemble
est non vide car il contient Rn .

Définition 1.1.4 Etant donné S ⊂ Rn , on appelle sous espace affine engendré par S, l’intersec-
tion de tous les sous espaces affines contenant S. C’est le plus petit sous espace affine contenant
S. On le note aff(S).

En dimension finie, comme c’est le cas ici, un sous espace affine est toujours fermé ce qui n’est
pas toujours le cas en dimension infinie.

Définition 1.1.5 Etant donné S ⊂ Rn , on appelle dimension de S la dimension de aff(S).

( 1.1.4 Soit ∅ 6= S ⊂ R , a ∈ S. On a P
n
Proposition )
p
α = 1,
aff(S) = x ∈ Rn : ∃p ∈ N∗ , ∃(αi , xi ) ∈ (R × S)p : Ppi=1
i
i
i=1 i x = x
α
ou encore( )
Pp p ∈ N, xi ∈ S, λi ∈ R, ∀i = 1, · · · , p,
aff(S) = x = a + i=1 λi (xi − a) : Pp .
i=1 λi = 1

Proposition 1.1.5 S1 ⊂ S2 =⇒ aff(S1 ) ⊂ aff(S2 )

Définition 1.1.6 Un hyperplan est un sous espace affine de codimension 1.

H est un hyperplan ⇐⇒ H = a + V et codimV = 1.

En dimension finie n comme c’est le cas ici,

codimV = 1 ⇐⇒ dim V = n − 1
1.1. SOUS ESPACES AFFINES 7

Proposition 1.1.6 ∅ 6= H ⊂ Rn
Les conditions suivantes sont équivalentes
i) H est un hyperplan
ii) Il existe ϕ : Rn −→ R linéaire non nulle et α ∈ R tels que

H = {x ∈ Rn : ϕ(x) = α}.

Preuve : Supposons i) et soit V la direction de H et a ∈ H.

a) Supposons a ∈ V :
Alors H = a + V = V . Comme V est de codimension 1, ∃ x0 ∈ Rn \ V tel que Rn = V ⊕ Rx0 .
Soit ϕ définie par :
Rn = V ⊕ Rx0 −→ R
ϕ:
x = v + λx0 7−→ λ
ϕ est linéaire non nulle et on a
{x ∈ Rn : ϕ(x) = 0} = H.
b) Supposons a ∈
/V :
Donc R = V ⊕ Ra. Considérons l’application
n

Rn = V ⊕ Ra −→ R
ϕ:
x = v + λa 7−→ λ

L’application ϕ est linéaire non nulle et

{x ∈ Rn : ϕ(x) = 1} = V + a = H.

Réciproquement supposons que

H = {x ∈ Rn : ϕ(x) = α}

où ϕ est une application linéaire non nulle de Rn dans R.

Soit a ∈ H : alors on a ∀x ∈ Rn ,

x ∈ H ⇐⇒ ϕ(x) = ϕ(a)
⇐⇒ x − a ∈ ϕ−1 (0)

Posons V = ϕ−1 (0) c’est donc un sous espace vectoriel de codimension 1 et on a H = a + V .

Alors H est hyperplan. ¤

Dans Rn tout hyperplan divise l’espace en deux demi espaces fermés de frontière cet hyperplan.
Par exemple si H est un hyperplan défini par

H = {x ∈ Rn : ϕ(x) = α}
où ϕ est une application linéaire non nulle de Rn dans R, les demi-espaces fermés sont

{x ∈ Rn : ϕ(x) ≤ α} et {x ∈ Rn : ϕ(x) ≥ α}.

Les ensembles {x ∈ Rn : ϕ(x) < α} et {x ∈ Rn : ϕ(x) α} sont des demi espaces ouverts de
frontière H.
8 CHAPITRE 1. ENSEMBLES CONVEXES

1.2 Ensembles convexes

1.2.1 Définitions
La notion de combinaison linéaire convexe est donnée dans la définition suivante.

Définition 1.2.1 On appelle combinaison linéaire convexe de xi : i = 1, · · · , k, k points de Rn ,

P
tout élément de Rn x = ki=1 λi xi où les coefficients λi sont positifs et de somme 1.

En particulier, une combinaison linéaire convexe de deux points x et y, est tout point z =
(1 − λ)x + λy avec λ ∈ [0, 1]
On a les définitions suivantes

Définition 1.2.2 Soit x, y ∈ Rn ; on appelle segment ”fermé” d’extrémités x et y, l’ensemble

noté [x, y] et défini par :

[x, y] = {z ∈ Rn : z = (1 − λ) x + λy : λ ∈ [0, 1]} .

C’est l’ensemble de toutes les combinaisons linéaires convexes des points x et y.

De façon analogue, on définit :

Définition 1.2.3 On appelle segment ”ouvert” d’extrémités x et y, et on le note ]x, y[, l’ensemble

]x, y[ = {z ∈ Rn : z = (1 − λ) x + λy : λ ∈ ]0, 1[} .

On définit aussi ]x, y] et [x, y[ qui sont appelés segment semi ouvert en x respectivement en y.

]x, y] = {z ∈ Rn : z = (1 − λ) x + λy λ ∈ ]0, 1]} .

[x, y[ = {z ∈ Rn : z = (1 − λ) x + λy λ ∈ [0, 1[} .

Définition 1.2.4 Soit C une partie de Rn . C est convexe si seulement si pour tout x, y ∈ C,
(1 − λ) x + λy ∈ C pour tout λ ∈ [0, 1]. Autrement dit, C est convexe si seulement si C contient
tout segment fermé d’extrémités deux quelconques de ses points.

Exemple 1.2.1 - Dans Rn , les ensembles suivants sont convexes. Rn , l’ensemble vide par conven-
tion, les singletons, les boules, les segments, les sous espaces affines.
- Dans R, les parties convexes sont les intervalles.

On a la proposition :

Proposition 1.2.1 Une partie C de Rn est convexe si seulement si elle contient toute combinaison
linéaire convexe de toute famille finie d’éléments qui lui appartiennent.
1.2. ENSEMBLES CONVEXES 9

Preuve : Si C contient toute combinaison linéaire convexe de familles finies d’éléments qui lui
appartiennent, en particulier, prenant une famille de deux éléments x et y de C, on a [x, y] ⊂ C
et donc C est convexe.
Réciproquement, soit C un ensemble convexe de Rn . Alors C contient toute combinaison linéaire
convexe de deux quelconques de ses éléments. Donc la propriété est vraie pour une famille com-
portant deux éléments. Supposons qu’elle est vraie pour une famille de k − 1 éléments.
Soit © ª
F = x1 , x 2 , · · · , x k
une famille de k élément de C.
Soit
X
k X
k
x= λi x avec λi ≥ 0,
i
λi = 1.
i=1 i=1
On a
X
k X
k−1
x= λi xi = λi xi + λk xk .
i=1 i=1
Soit
X
k−1
λ= λi .
i=1
On a λ ∈ [0, 1].
Si λ = 0 alors λi = 0 pour tout i = 1, · · · , k − 1 et donc λk = 1. Il vient alors que x = λk xk =
xk ∈ C.
Si λ 6= 0, on peut écrire
Xk−1 µ ¶
λi
x=λ xi + λk xk .
i=1
λ
L’élément
k−1 µ
X ¶
λi
y= xi ,
i=1
λ
est une combinaison linéaire convexe de k − 1 éléments de C. C’est donc un élément de C, par
hypothèse de recurrence. Donc x = λy+λk xk . Or λk = 1−λ avec λ ∈ [0, 1]. Donc x est combinaison
linéaire convexe de deux éléments de C. Comme par hypothèse, C est convexe, on a alors x ∈ C.
¤

On a les propriétés suivantes

1.2.2 Propriétés algébriques

On rappelle les notions suivantes.
Définition 1.2.5 Une application f de Rn dans Rm est dite affine si l’une des conditions suivantes
est vérifiée.
i) Pour tout x, y dans Rn et λ ∈ R, on a
f ((1 − λ)x + λy) = (1 − λ)f (x) + λf (y).
ii) Il existe une application linéaire L de Rn dans Rm et un vecteur a dans Rm tels que :
∀ x ∈ Rn , f (x) = L(x) + a.
10 CHAPITRE 1. ENSEMBLES CONVEXES

Les résultats suivants sont immédiats.

Proposition 1.2.2 1) Si C1 et C2 sont convexes alors pour tous α1 et α2 dans R, α1 C1 + α2 C2

est convexe.
2) Toute intersection de parties convexes est convexe.
3) L’union de sous ensembles convexes n’est pas convexe en général, mais l’union croissante de
convexes (famille mboı̂tée) est convexe.
4) Le produit cartésien de deux convexes C ⊂ Rn et C 0 ⊂ Rm est convexe dans Rn × Rm .
5) Inversement, la projection d’un sous ensemble convexe d’un espace produit sur l’un de ses sous
espaces composants est convexe.
6) L’image d’un convexe par une application affine est convexe.
7) L’image réciproque d’un convexe par une application affine est convexe.

On a la proposition suivante

Proposition 1.2.3 Si C est convexe alors pour tout α et β positifs ou nuls, on a

αC + βC = (α + β)C.

Preuve : Comme les scalaires α et β sont positifs ou nuls, le cas où α + β = 0 est trivial
Considérons α et β tels que α + β > 0.
L’inclusion ci-dessous est immédiate :

(α + β)C ⊂ αC + βC.

Montrons à présent que

αC + βC ⊂ (α + β)C.
Soit z ∈ αC + βC. Alors il existe x, y dans C tels que z = αx + βy.
On peut écrire : · ¸
α β
z = (α + β) x+ y .
α+β α+β
On a
α β α β
> 0, > 0, + = 1.
α+β α+β α+β α+β
Comme C est convexe, alors
α β
x+ y ∈ C.
α+β α+β
D’où le résultat ¤

1.2.3 Propriétés topologiques

Notons que pour x ∈ Rn , et ε > 0, B(x, ε) désigne la boule euclidienne fermée de centre x et
de rayon ε.
On remarque qu’on a toujours B(x, ε) = x + εB(0, 1), B(0, 1) étant la boule unité euclidienne
fermée.
On rappelle que
1.2. ENSEMBLES CONVEXES 11

Définition 1.2.6 Étant donné un sous ensemble C de Rn , son adhérence son intérieur et sa
frontière sont respectivement les ensembles :
C = ∩{C + B(0, ε) : ε > 0},
int(C) = {x ∈ Rn : ∃ε > 0, B(x, ε) ⊂ C},
Fr(C) = C \ int(C).

Proposition 1.2.4 Soit C un convexe de Rn . Alors :

1) C est convexe.
2) int(C) est convexe.
3) Si x ∈ int(C) et y ∈ C alors [x, y[ ⊂ int(C).
4) Si int(C) 6= ∅ alors

int(C) = int(C), C = int(C), Fr(C) = Fr(int(C)).

Preuve : 1) Immédiat.
2) Soient x et y deux éléments de int(C), λ ∈ [0, 1] et z = (1 − λ)x + λy. D’après la définition
de int(C), il existe ε1 et ε2 tels que B(x, ε1 ) ⊂ C et B(y, ε2 ) ⊂ C. Donc pour ε = min{ε1 , ε2 }, on
a
B(x, ε) ⊂ C, B(y, ε) ⊂ C.
Comme
B(z, ε) = z + B(0, ε)
= (1 − λ)x + λy + B(0, ε)
= (1 − λ)x + λy + ((1 − λ) + λ)B(0, ε)
= (1 − λ) [x + B(0, ε)] + λ [y + B(0, ε)]
= (1 − λ)B(x, ε) + λB(y, ε)
et
(1 − λ)B(x, ε) + λB(y, ε) ⊂ (1 − λ)C + λC = C,
car C est convexe, on conclut que B(z, ε) ⊂ C. Par suite z ∈ int(C). Donc int(C) est convexe.
3) Soit x ∈ int(C) et y ∈ C. Soit z = (1 − λ)x + λy, λ ∈ [0, 1[. Montrons que z ∈ int(C).
On a pour tout ε > 0,

B(z, ε) = z + B(0, ε)
= (1 − λ)x + λy + B(0, ε)
⊂ (1 − λ)x + λ(C + B(0, ε)) + B(0, ε)
= (1 − λ)x + λCh + (1 + λ)B(0, ε)i
= λC + (1 − λ) x + B(0, (1−λ)
(1+λ)
ε)

Comme x ∈ int(C), il existe ε0 > 0 tel que x + B(0, ε0 ) ⊂ C.

Soit ε0 tel que
(1 + λ)
ε 0 < ε0 .
(1 − λ)
On a alors
B(z, ε0 ) ⊂ λC + (1 − λ) [x + B(0, ε0 )] ⊂ λC + (1 − λ)C = C.
Donc z ∈ int(C).
4) Montrons que int(C) = C.
On sait que int(C) ⊂ C. Donc int(C) ⊂ C.
12 CHAPITRE 1. ENSEMBLES CONVEXES

Soit y ∈ C ; comme int(C) 6= ∅, soit x ∈ int(C).

D’après 3), [x, y[ ⊂ int(C) : par suite y ∈ int(C).
Montrons maintenant que int(C) = int(C).
On a l’inclusion int(C) ⊂ int(C).
Soit x ∈ int(C) et y ∈ int(C) car non vide.
Considérons les points du type z = x + λ(x − y) avec λ > 0. Pour λ0 > 0 suffisamment petit,

z0 = x + λ0 (x − y) ∈ int(C).

Donc z0 ∈ C et [y, z0 [ ⊂ int(C).

1
Or x = 1+λ 0
λ0
z0 + 1+λ 0
y, donc x ∈ [y, z0 [ et par suite x ∈ int(C).
On a par définition

Fr(C) = C \ int(C), Fr(int(C)) = int(C) \ int(C).

Comme C = int(C) on a le résultat. ¤

1.3 Enveloppes convexes

Définition 1.3.1 Soit S une partie de Rn . On appelle enveloppe convexe de S, l’intersection de
tous les convexes contenant S. C’est le plus petit convexe contenant S. On le note conv(S).

On a le résultat suivant.

Proposition 1.3.1 Soit S ⊂ Rn . L’enveloppe convexe de S, est l’ensemble de toutes les combi-
naisons linéaires convexes finies d’éléments de S. Autrement dit on a :
( )
Xk
x i
∈ S, ∀i = 1, · · · , k,
conv(S) = x = λi x i : k ∈ N ∗ , P
i=1
λi ≥ 0, ∀i = 1, · · · , k, ki=1 λi = 1

Preuve :
Posons ( )
X
k
xi ∈ S, ∀i = 1, · · · , k,
C= x= λi xi : k ∈ N ∗ , P
λi ≥ 0, ∀i = 1, · · · , k, ki=1 λi = 1
i=1
n
Soit C un convexe de R contenant S. Donc C contient toute combinaison linéaire convexe de toute
famille finie d’éléments de C. Comme C contient S alors C contient toute combinaison linéaire
convexe de toute famille finie d’éléments de S et donc C contient C. Par suite C est contenu dans
tous les convexes contenant S. On a alors C ⊂ conv(S).
D’autre part, on vérifie facilement que C est convexe et contient S. Et comme conv(S) est le
plus petit convexe contenant S, on a alors conv(S) ⊂ C. D’où l’égalité conv(S) = C. ¤

Proposition 1.3.2 S est convexe si et seulement si conv(S) = S

Preuve : Si S est convexe alors il est le plus petit convexe contenant S. Donc conv(S) = S.
Réciproquement si on a conv(S) = S alors S est convexe. ¤

Proposition 1.3.3 1) conv(conv(S)) = conv(S)

2) Si on a A ⊂ B alors conv(A) ⊂ conv(B)
1.3. ENVELOPPES CONVEXES 13

Preuve : 1) Comme conv(S) est convexe, on a conv(conv(S)) = conv(S).

2) Soit A ⊂ B : le plus petit convexe contenant B contient aussi A donc conv(B) contient
conv(A). ¤

Proposition 1.3.4 Soient A et B deux convexes de Rn . On a

conv(A ∪ B) = ∪λ∈[0,1] (1 − λ)A + λB.

Preuve : Posons C = ∪λ∈[0,1] (1 − λ)A + λB.

Montrons que C est convexe. Soient x, y dans C et α ∈ [0, 1]. Il existe alors λ1 et λ2 dans [0, 1]
tels que x ∈ (1 − λ1 )A + λ1 B et y ∈ (1 − λ2 )A + λ2 B Comme A et B sont convexes on a alors

(1 − α)x + αy ∈ (1 − α)[(1 − λ1 )A + λ1 B] + α[(1 − λ2 )A + λ2 B]

= [(1 − α)(1 − λ1 ) + α(1 − λ2 )]A + [(1 − α)λ1 + αλ2 ]B.

Les coefficients (1 − α)(1 − λ1 ) + α(1 − λ2 ) et (1 − α)λ1 + αλ2 sont positifs et de somme 1,

donc (1 − α)x + αy ∈ C. Par suite C est convexe.
Il est immédiat que C contient A ∪ B. Donc conv(A ∪ B) ⊂ C. En outre tout élément de C
est combinaison linéaire convexe de deux éléments de A ∪ B et donc il appartient à conv(A ∪ B).
D’où l’égalité des ensembles conv(A ∪ B) et de C ¤
Plus généralement on montre que

Proposition 1.3.5 Si k ∈ N∗ , et C1 , · · · , Ck sont des convexes de Rn , alors

( Pk )
X k
αi ≥ 0, ∀i = 1, · · · , k, αi = 1
k i i=1
conv(∪i=1 Ci ) = x = αi x : i .
i=1
x ∈ Ci

A présent rappelons la définition d’une famille de points affinement indépendants.

Définition 1.3.2 Soit x0 , x1 , · · · , xk , k+1 points de Rn . On dit qu’ils sont affinement indépendants
si les vecteurs
x 1 − x0 , x 2 − x0 , · · · , x k − x0
sont linéairement indépendants

Définition 1.3.3 L’enveloppe convexe de k + 1 points affinement indépendants est appelée k-

simplexe.

Lemme 1.3.1 (Caratheodory)

Dans un Rn toute combinaison convexe de m points , m > n+1, peut se ramener à une combinaison
convexe de n + 1 points au plus.

Preuve : Soit
X
m X
m
x= αi xi avec αi ≥ 0 ∀ i = 1, · · · , m, αi = 1.
i=1 i=1

Il suffit de montrer que si m > n + 1, on peut faire décroı̂tre m de 1. Ce fait, utilisé de façon
répétée, prouvera le résultat.
14 CHAPITRE 1. ENSEMBLES CONVEXES

Posons zi = xi −x1 pour i = 2, · · · , m. Ces vecteurs en nombre au moins égal à n+1 ne peuvent
être linéairement independants. Il existe donc une combinaison linéaire nulle, à coefficients βi non
tous nuls, donc
Xm Xm Xm
βi zi = 0 ⇒ βi xi avec βi = 0,
i=2 i=1 i=1

en ayant posé
X
m
β1 = βi .
i=2

On considère alors
µ ¶
βi βi
γ = max et δi = α i − , i = 1, · · · , m.
i=1,··· ,m αi γ

On a γ 6= 0 car les βi ne sont pas tous nuls. On vérifie que

X
m X
m
x= αi x i = δi xi ,
i=1 i=1

et que les δi sont positifs de somme 1 avec au moins un qui est égal à 0. On a donc exprimé x
comme une combinaison convexe de moins de m points. ¤
On en déduit que

Théorème 1.3.1 (Caratheodory)

Dans Rn l’enveloppe convexe d’un sous-ensemble S est égal à l’ensemble des combinaisons convexes
de n + 1 points de S.

On a la propriété topologique suivante :

Proposition 1.3.6 L’enveloppe convexe d’un ouvert est un ouvert.

Preuve : Soit S un ouvert : montrons que int(conv(S)) = conv(S).

Supposons qu’il existe un élément x dans S ∩ Fr(conv(S)). Alors comme S est ouvert, il
existerait un voisinage V de x contenu dans S et donc dans conv(S). Or

x ∈ Fr(conv(S)) = conv(S) \ int(conv(S)).

Ce qui est contradictoire.

Donc S ∩ Fr(conv(S)) = ∅. On a alors S ⊂ int(conv(S)). Comme conv(S) est le plus petit
convexe contenant S, on a conv(S) ⊂ int(conv(S)). On obtient donc conv(S) = int(conv(S)). ¤
Comme le montre l’exemple ci-dessous, l’enveloppe convexe d’un fermé n’est pas en général un
fermé.
Soit
S = {(x, y) ∈ R2 : x ≥ 0, xy ≥ 1} ∪ {(0, 0)}
On a
conv(S) = {(x, y) : x > 0, y > 0} ∪ {(0, 0)}
qui n’est pas un fermé.
1.3. ENVELOPPES CONVEXES 15

Proposition 1.3.7 Soit S ⊂ Rn .

1) Si S est borné alors conv(S) est borné.
2) Si S est compact alors conv(S) est compact.
Preuve :
1) Immédiat
2) On a
X
n+1 X
n+1
conv(S) = {x = λi xi : λi ≥ 0, xi ∈ S, ∀i = 1, · · · , n + 1, λi = 1}.
i=1 i=1

Posons
X
n+1
K = {λ ∈ R n+1
: λi ≥ 0, ∀i = 1, · · · , n + 1, λi = 1}.
i=1
K est compact.
Soit
S n+1 × K −→ Rn
f: P
(x1 , · · · xn+1 ) 7−→ n+1
i=1 λi xi
f est continue et S n+1 × K est compact ce qui implique que f (S n+1 × K) est compact. Or
f (S n+1 × K) = conv(S). D’où la proposition. ¤

Définition 1.3.4 Soit S une partie de Rn , l’enveloppe convexe fermée de S est l’intersection de
tous les convexes fermés contenant S. C’est le plus petit convexe fermé contenant S. On le note
conv(S).

Proposition 1.3.8 1) Si A et B sont deux sous ensembles de Rn avec

A ⊂ B, alors conv(A) ⊂ conv(B).
2) Si S est une partie de Rn , on a :
conv(S) = conv(S) = conv(S).
Preuve : La preuve de 1) est immédiate.
2) L’ensemble des convexes fermés contenant S est égal à l’ensemble des convexes fermés
contenant S. Donc conv(S) = conv(S).
Montrons que
conv(S) = conv(S).
On a
S ⊂ conv(S) ⊂ conv(S).
Or conv(S) est un convexe fermé ; donc,
conv(S) ⊂ conv(S).
D’autre part, on a
conv(S) ⊂ conv(S)
et S ⊂ S : donc
conv(S) ⊂ conv(S) ⊂ conv(S).
On en déduit alors que
conv(S) ⊂ conv(S) = conv(S).
Ce qui donne la deuxième inclusion et donc l’égalité recherchée. ¤
16 CHAPITRE 1. ENSEMBLES CONVEXES

1.4 Points extrêmes

Définition 1.4.1 Soit C un sous ensemble convexe non vide de Rn .
Un point x de C est un point extrême si

∀ (x1 , x2 , α) ∈ C 2 ×]0, 1[, x = (1 − α)x1 + αx2 =⇒ x1 = x2 = x.

i.e. Il n’existe pas deux points y et z de C distincts tels que x ∈]y, z[.
L’ensemble ext(C) des points extrêmes de C est appelé profil de C.

On a la caractérisation suivante

Proposition 1.4.1 Soit C un sous ensemble convexe de Rn . Les propositions suivantes sont
équivalentes.
i) x ∈ ext(C)
ii) C \ {x} est convexe.

Preuve : Soit x ∈ ext(C).

Si
(x1 , x2 , α) ∈ (C \ {x}) × (C \ {x})×]0, 1[
alors
(x1 , x2 , α) ∈ C × C×]0, 1[ et x1 6= x 6= x2 .
Comme C est convexe, on a

(1 − α)x1 + αx2 ∈ C et x1 6= x 6= x2 .

Alors
(1 − α)x1 + αx2 ∈ C \ {x}
et donc C \ {x} est convexe.
Réciproquement, supposons que C \ {x} est convexe et soit

(x1 , x2 , α) ∈ C × C×]0, 1[ avec (1 − α)x1 + αx2 = x.

Donc
(1 − α)x1 + αx2 ∈
/ C \ {x}.
Ce qui implique que :
x1 ∈
/ C \ {x} ou x2 ∈
/ C \ {x}
C’est-à-dire que x1 = x ou x2 = x. Comme (1 − α)x1 + αx2 = x avec α ∈]0, 1[, on a nécessairement
x1 = x = x2 . D’où x ∈ ext(C). ¤
On admettra que

Théorème 1.4.1 Tout convexe compact est l’enveloppe convexe de ses points extrêmes.
Chapitre 2

Projection et Séparation

Dans ce chapitre Rn est muni de sa structure euclidienne.

2.1 Projection sur un convexe

Le théorême ci-dessous est fondamental en optimisation.

Théorème 2.1.1 Soit S un convexe fermé de Rn et x ∈ Rn . Il existe un unique point p(x) ∈ S

dont la distance à x est minimale. C’est-à-dire

kp(x) − xk ≤ ky − xk ∀y ∈ S.

p(x) est appelé projection de x sur S.

Preuve : Soit d = inf y [ky − xk : y ∈ S], B(x, d + 1) la boule fermée de centre x et de rayon d + 1.
Considérons K = S ∩ B(x, d + 1). L’ensemble K est fermé et borné, c’est donc un compact. Alors
l’application y 7→ ky − xk étant continue elle atteint ses bornes sur K. Donc il existe p(x) ∈ K et
donc p(x) ∈ S tel que kp(x) − xk = d. D’où le résultat d’existence. Montrons maintenant l’unicité.
Soient a et b deux points de S tels que

ka − xk = kb − xk = d = inf [ky − xk : y ∈ S] .
y

Comme S est convexe alors 12 a + 21 b ∈ S. Donc

a+b 1 1
d ≤ kx − k = k2x − a − bk = k(x − a) + (x − b)k.
2 2 2
Ce qui implique que
a+b 1
d ≤ kx − k ≤ (kx − ak + kx − bk) = d.
2 2
On en déduit que kx − 2 k = d. Il s’ensuit que kx − a + x − bk = kx − ak + kx − bk c’est-à-dire
a+b

qu’il existe λ ∈ R tel que x − a = λ(x − b). Donc on a |λ| = 1.

Si λ = 1, alors x − a = x − b et donc a = b.
Si λ = −1, alors 2x = a + b donc x = a+b 2
et appartient donc à S. Dans ce cas on a d = 0 et
donc x = a = b.
Dans tous les cas de figure, on a a = b. D’où l’unicité. ¤
Une caractérisation de la projection est donnée ici.

17
18 CHAPITRE 2. PROJECTION ET SÉPARATION

Théorème 2.1.2 La projection p(x) de x sur S un convexe fermé de Rn est l’unique point z de
S satisfaisant la condition
hy − z, x − zi ≤ 0 ∀y ∈ S.
Autrement dit, p(x) est la projection de x sur S si et seulement si

hx − p(x), y − p(x)i ≤ 0 ∀y ∈ S.

Preuve : Soit p(x) la projection sur S un convexe fermé de Rn . Supposons qu’il existe un point
y0 ∈ S tel que hy0 − p(x), x − p(x)i > 0.
Posons
ϕ(t) = kx − [(1 − t)p(x) + ty0 ] k2 , t ∈ R+ .
On a
ϕ(t) = kx − p(x)k2 + 2thx − p(x), p(x) − y0 i + t2 kp(x) − y0 k2
= kx − p(x)k2 + t (2hx − p(x), p(x) − y0 i + tkp(x) − y0 k2 ) .
Comme hx − p(x), p(x) − y0 i < 0, pour t suffisamment petit, on aura ϕ0 (t) < 0 et donc ϕ
est strictement décroissante au voisinage de 0. On aura donc pour t suffisamment petit ϕ(t) <
kx − p(x)k2 .
Or pour t ∈ [0; 1], zt = (1 − t)p(x) + ty0 ∈ S car S est convexe. Soit donc t ∈ [0; 1] suffisamment
petit tel que ϕ(t) < kx − p(x)k2 . Pour un tel t on aura zt ∈ S et kx − zt k2 < kx − p(x)k2 . Ce qui
contredit le fait que p(x) est la projection de x sur S.
Réciproquement supposons que

hy − z; x − zi ≤ 0 ∀y ∈ S.

Montrons que z est la projection de x sur S.

Soit y ∈ S. On a

kx − yk2 = kx − z + z − yk2 = kx − zk2 + 2hx − z; z − yi + ky − zk2 .

Par suite on a kx − yk2 ≥ kx − zk2 , et donc p(x) = z. ¤

L’application projection est lipschitzienne sur Rn .

Proposition 2.1.1 Soit S un convexe fermé non vide de Rn et pour tout x ∈ Rn , p(x) la projection
de x sur S. On a
kp(x) − p(y)k ≤ kx − yk ∀x, y ∈ Rn .

Preuve : Soient x et y fixés dans Rn . Considérons p(x) et p(y) respectivement leurs projections
sur S. On sait d’après la caractérisation de la projection que p(x) est tel que

hz − p(x), x − p(x)i ≤ 0 ∀z ∈ S.
En prenant z = p(y) on obtient

hp(y) − p(x), x − p(x)i ≤ 0. (2.1)

De même en considérant p(y) on a

hz − p(y), y − p(y)i ≤ 0 ∀z ∈ S.
2.2. SÉPARATION DE DEUX ENSEMBLES 19

Pour z = p(x) on a
hp(x) − p(y), y − p(y)i ≤ 0. (2.2)
En additionnant (2.1)et (2.2) on obtient
hp(x) − p(y), y − p(y) + p(x) − xi ≤ 0,
qui est équivalent à
hp(x) − p(y), p(x) − p(y) − (x − y)i ≤ 0,
c’est-à-dire
hp(x) − p(y), p(x) − p(y)i ≤ hp(x) − p(y), x − yi.
On en déduit
kp(x) − p(y)k2 ≤ kp(x) − p(y)kkx − yk.
D’où le résultat. ¤

Corollaire 2.1.1 l’application définie sur Rn qui à tout x ∈ Rn associe sa projection sur S un
convexe fermé est continue.

2.2 Séparation de deux ensembles

Etant donnés a ∈ Rn non nul et α ∈ R, l’hyperplan
Ha,α = {x ∈ Rn : ha; xi = α}
divise l’espace Rn en deux demi-espaces fermés
+
Ha,α = {x ∈ Rn : ha; xi ≥ α}
et
−
Ha,α = {x ∈ Rn : ha; xi ≤ α} .
On définit la notion de séparation de deux ensembles de la façon suivante.

Définition 2.2.1 Soit S1 et S2 deux sous ensembles de Rn . On dit qu’ils sont séparés par l’hy-
−
+
perplan Ha,α si l’un est contenu dans Ha,α et l’autre dans Ha,α . Soit par exemple S1 ⊂ Ha,α
+
et
−
S2 ⊂ Ha,α .

Il existe plusieurs types de séparations

Définition 2.2.2 (Séparation propre)

La séparation des ensembles S1 et S2 est dite propre si en plus S1 ∪ S2 n’est pas contenu dans Ha,α .

Définition 2.2.3 (Séparation stricte)

−
La séparation des ensembles S1 et S2 par Ha,α avec S1 ⊂ Ha,α
+
et S2 ⊂ Ha,α est dite stricte si
¡ + ¢ ¡ − ¢
S1 ⊂ int Ha,α et S2 ⊂ int Ha,α .

Définition 2.2.4 (Séparation forte)

−
La séparation des ensembles S1 et S2 par Ha,α avec S1 ⊂ Ha,α +
et S2 ⊂ Ha,α est dite forte si il
−
existe ε > 0 tel que S1 + B(0; ε) ⊂ Ha,α et S2 + B(0; ε) ⊂ Ha,α , où B(0; ε) désigne la boule fermée
+

de centre 0 et de rayon ε.
20 CHAPITRE 2. PROJECTION ET SÉPARATION

Remarque 2.2.1 D’après les définitions, la séparation forte implique la séparation stricte qui
implique la séparation propre.

On a les caractérisations analytiques suivantes.

Proposition 2.2.1 Deux sous ensembles S1 et S2 de Rn sont séparés par Ha,α avec S1 ⊂ Ha,α
+
et
−
S2 ⊂ Ha,α si et seulement si

inf [ha; xi : x ∈ S1 ] ≥ α ≥ sup [ha; yi : y ∈ S2 ] .

−
Preuve : Supposons que les ensembles S1 et S2 sont séparés par Ha,α avec S1 ⊂ Ha,α
+
et S2 ⊂ Ha,α .
La condition S1 ⊂ Ha,α implique que ha; xi ≥ α pour tout x ∈ S1 . On a donc
+

inf [ha; xi : x ∈ S1 ] ≥ α.
−
De même on a S2 ⊂ Ha,α qui implique que ha; yi ≤ α pour tout y ∈ S2 . Par suite,

sup [ha; yi : y ∈ S2 ] ≤ α.

On obtient donc
inf [ha; xi : x ∈ S1 ] ≥ α ≥ sup [ha; yi : y ∈ S2 ] .
La réciproque est immédiate. ¤

Remarque 2.2.2 On dira donc que deux ensembles S1 et S2 sont séparés s’il existe a ∈ Rn , a 6= 0
et α ∈ R tels que
ha, x1 i ≤ α ≤ ha, x2 i ∀ x1 ∈ S1 et x2 ∈ S2 .

Proposition 2.2.2 Deux sous ensembles S1 et S2 de Rn sont séparés proprement par Ha,α avec
−
S1 ⊂ Ha,α
+
et S2 ⊂ Ha,α si et seulement si on a les conditions suivantes

(i) inf [ha; xi : x ∈ S1 ] ≥ sup [ha; yi : y ∈ S2 ] .

(ii) sup [ha; xi : x ∈ S1 ] > inf [ha; yi : y ∈ S2 ] .

Preuve : Supposons que S1 et S2 de Rn sont séparés proprement par Ha,α avec S1 ⊂ Ha,α
+
et
−
S2 ⊂ Ha,α . On a alors

inf [ha; xi : x ∈ S1 ] ≥ α ≥ sup [ha; yi : y ∈ S2 ] .

Donc

inf [ha; xi : x ∈ S1 ] ≥ sup [ha; yi : y ∈ S2 ] .

Mais comme S1 ∪ S2 n’est pas contenu dans Ha,α , on peut trouver x̄ ∈ S1 tel que ha; x̄i > α ou
ȳ ∈ S2 tel que ha; ȳi < α.
Dans tous les cas on a alors

sup [ha; xi : x ∈ S1 ] > inf [ha; yi : y ∈ S2 ] .

Réciproquement soit α tel que

2.2. SÉPARATION DE DEUX ENSEMBLES 21

inf [ha; xi : x ∈ S1 ] ≥ α ≥ sup [ha; yi : y ∈ S2 ] .

On a pour tout x ∈ S1 , ha; xi ≥ α et pour tout y ∈ S2 , ha; yi ≤ α. Donc l’hyperplan Ha,α sépare
S1 et S2 .
En plus, comme on a

sup [ha; xi : x ∈ S1 ] > inf [ha; yi : y ∈ S2 ] .

on peut trouver x ∈ S1 et y ∈ S2 tels que ha; yi < ha; xi. Donc S1 ∪ S2 n’est pas contenu dans
Ha,α . ¤

Proposition 2.2.3 Deux sous ensembles S1 et S2 de Rn sont séparés strictement par Ha,α avec
−
S1 ⊂ int(Ha,α
+
) et S2 ⊂ int(Ha,α ) si et seulement si ha; xi > α pour tout x ∈ S1 et ha; yi < α pour
tout y ∈ S2 .

La démonstration est immédiate

Proposition 2.2.4 Deux sous ensembles S1 et S2 de Rn sont séparés fortement par Ha,α avec
−
S1 ⊂ Ha,α
+
et S2 ⊂ Ha,α si et seulement si

inf [ha; xi : x ∈ S1 ] > α > sup [ha; yi : y ∈ S2 ] .

Preuve : Par définition de la séparation forte il existe ε > 0 tel que S1 + B(0; ε) ⊂ Ha,α
+
et
−
S2 + B(0; ε) ⊂ Ha,α . On a donc d’une part

ha; xi − ha; zi ≥ α ∀x ∈ S1 , ∀z ∈ B(0; ε).

On peut alors écrire

inf [ha; xi : x ∈ S1 ] + inf [−ha; zi : z ∈ B(0; ε)] ≥ α.

c’est-à-dire
inf [ha; xi : x ∈ S1 ] ≥ α − inf [−ha; zi : z ∈ B(0; ε)]

= α + sup [ha; zi : z ∈ B(0; ε)] > α.

soit
inf [ha; xi : x ∈ S1 ] > α. (2.3)
D’autre part on a
ha; yi + ha; zi ≤ α ∀y ∈ S2 , ∀z ∈ B(0; ε).
On obtient donc
sup [ha; yi : y ∈ S2 ] ≤ α − sup [ha; zi : z ∈ B(0; ε)] < α. (2.4)
En considérant (2.3) et (2.4) on obtient

inf [ha; xi : x ∈ S1 ] > sup [ha; yi : y ∈ S2 ] .

Réciproquement supposons que

inf [ha; xi : x ∈ S1 ] > α > sup [ha; yi : y ∈ S2 ] .

22 CHAPITRE 2. PROJECTION ET SÉPARATION

Soit
ε0 = α − sup [ha; yi : y ∈ S2 ] .
Considérons ε1 > 0 tel que
sup [ha; zi : z ∈ B(0; ε1 )] < ε0 .
Comme
sup [ha; zi : z ∈ B(0; ε1 )] = ε1 kak,
ε0
il suffit de prendre ε1 < kak
. Pour un tel ε1 on a

sup [ha; yi : y ∈ S2 ] + sup [ha; zi : z ∈ B(0; ε1 )] < α.

−
Donc on a S2 + B(0; ε1 ) ⊂ Ha,α .
De façon analogue on montre qu’on a un ε2 tel que S1 + B(0; ε2 ) ⊂ Ha,α
+
. Il suffit de prendre
ε < min{ε1 , ε2 } et on aura
−
S2 + B(0; ε) ⊂ Ha,α , S1 + B(0; ε) ⊂ Ha,α
+
.

D’où le résultat ¤

Remarque 2.2.3 On dira donc que deux ensembles S1 et S2 sont séparés fortement s’il existe
a ∈ Rn , a 6= 0 α1 et α2 dans R tels que

ha, x1 i ≤ α1 < α2 ≤ ha, x2 i ∀ x1 ∈ S1 et x2 ∈ S2 .

On a les résultats de séparation d’un point et d’un ensemble suivants.

Théorème 2.2.1 (Séparation point/convexe fermé)

Soit S un convexe fermé non vide et x̄ ∈
/ S. Alors il existe a ∈ Rn , a 6= 0 tel que

supha; xi < ha; x̄i.

x∈S

C’est-à-dire qu’il existe un hyperplan qui sépare fortement S et x̄.

Preuve : Soit p(x̄) la projection de x̄ sur S et a = x̄ − p(x̄).
Comme x̄ ∈ / S, on a a 6= 0.
D’après la caractérisation de la projection on a

hx̄ − p(x̄); x − p(x̄)i ≤ 0, ∀x ∈ S.

D’où
ha; x − x̄ + x̄ − p(x̄)i ≤ 0.
Ce qui est équivalent à
kak2 − ha; x̄ − xi ≤ 0.
Où encore
ha; xi ≤ ha; x̄i − kak2 .
Comme a 6= 0, on a donc
supha; xi ≤ ha; x̄i − kak2 < ha; x̄i.
x∈S

D’où le résultat. ¤
On a le corollaire suivant
2.2. SÉPARATION DE DEUX ENSEMBLES 23

Corollaire 2.2.1 Tout convexe fermé de Rn est l’intersection de tous les demi-espaces fermés le
contenant.

Preuve : Soit S un convexe fermé de Rn et H l’ensemble de tous les demi-espaces fermés le

contenant.
Soit C l’intersection de tous les demi-espaces fermés contenant S. Montrons que S = C.
Il est immédiat que S ⊂ C.
Réciproquement, soit x̄ ∈ C. Si x̄ ∈ / S, alors d’après le théorème de séparation forte point
convexe fermé, il exite a 6= 0 dans Rn et α ∈ R tels que ha; x̄i > α et ha; xi ≤ α pour tout x ∈ S.
Soit
−
Ha,α = {x ∈ Rn : ha; xi ≤ α} .
− −
C’est un demi-espace fermé contenant S. On a alors C ⊂ Ha,α et x̄ ∈
/ Ha,α . Ce qui contradictoire
car x̄ ∈ C. Donc x̄ ∈ S. D’où l’inclusion C ⊂ S. Par suite on a S = C. ¤
On a les théorèmes suivants.

Théorème 2.2.2 Soit C un convexe non vide de Rn

et x̄ ∈ F r(C). Alors il existe un hyperplan qui supporte C en x̄. C’est-à-dire qu’il existe a 6= 0
dans Rn tel que
ha; x − x̄i ≤ 0 ∀x ∈ C.

Preuve : Comme x̄ ∈ F r(C) alors il existe une suite {xk }, xk ∈

/ C pour tout k avec xk → x̄.
Donc pour tout k il existe ak 6= 0 on peut donc supposer kak k = 1 tel que

hak ; xk i > hak ; xi ∀x ∈ C.

La suite {ak } étant bornée, elle admet donc une sous suite convergente. Soit {akl } cette sous suite
et a, sa limite. On a kak = 1 et donc a 6= 0. On a alors

hakl ; xkl i > hakl ; xi ⇔ hakl ; x − xkl i < 0 ∀x ∈ C.

Par passage à la limite on obtient

ha; x − x̄i ≤ 0 ∀x ∈ C.

Ce qui démontre le théorème ¤

Définition 2.2.5 Considérons X un sous ensemble de Rn de frontière ∂X. L’hyperplan H est un

hyperplan support pour X en x̄ ou qu’il supporte X en x̄ si :
i) X est contenu dans un des deux demi-espaces fermés limités par H
ii) x̄ ∈ H ∩ ∂X.

Définition 2.2.6 L’hyperplan support H est dit propre si X n’est pas entièrement contenu dans
H.

On montre que

Théorème 2.2.3 Soit C un convexe d’intérieur non vide de Rn et x̄ ∈ F r(C). Alors il existe un
hyperplan qui supporte proprement C en x̄.
24 CHAPITRE 2. PROJECTION ET SÉPARATION

Corollaire 2.2.2 Soit C un convexe non vide de Rn et x̄ ∈

/ C. Alors il existe a 6= 0 dans Rn tel
que ha; x − x̄i ≤ 0 ∀x ∈ C.

Preuve : i) Si x̄ ∈ / C, on utilise le théorème de séparation forte point convexe fermé et on a le

résultat.
ii) Si x̄ ∈ Fr(C), on utilise le théorème ci-dessus et on a aussi le résultat. ¤
A présent donnons quelques résultats de séparation de deux ensembles convexes.

Théorème 2.2.4 (Séparation de deux convexes)

Soient C1 et C2 deux convexes non vides et disjoints de Rn . Alors il existe a 6= 0 dans Rn tel que

inf ha; xi ≥ sup ha; yi.

x∈C1 y∈C2

Preuve : Soit C = C2 − C1 . On a C qui est convexe et 0 ∈

/ C. D’après le corollaire ci-dessus, il
existe a 6= 0 dans R tel que
n

ha; y − xi ≤ 0 ∀x ∈ C1 , ∀y ∈ C2 .

On tire alors
inf ha; xi ≥ sup ha; yi.
x∈C1 y∈C2

D’où le résultat ¤

Corollaire 2.2.3 (théorème de séparation propre)

Soient C1 et C2 deux convexes d’intérieurs non vides.
On suppose que int(C1 ) ∩ int(C2 ) = ∅. Alors on peut séparer proprement C1 et C2 . C’est-à-dire
qu’il existe a 6= 0 tel que

inf ha; xi ≥ sup ha; yi et sup ha; xi > inf ha; yi.
x∈C1 y∈C2 x∈C1 y∈C2

Preuve : Soit C = C2 − C1 . Comme les ensembles C1 et C2 sont convexes, C l’est aussi. En outre
on a int(C) = int(C2 ) − int(C1 ).
Comme int(C1 ) ∩ int(C2 ) = ∅ alors 0 ∈ / int(C).
a) Si 0 ∈
/ C alors d’après le théorème de séparation forte point convexe fermé, il existe a 6= 0
tel que £ ¤
sup ha; zi : z ∈ C < 0.
On peut donc écrire :
sup [ha; y − xi : x ∈ C1 , y ∈ C2 ] < 0
⇔ sup [ha; yi : y ∈ C2 ] + sup [−ha; xi : x ∈ C1 ] < 0
⇔ sup [ha; yi : y ∈ C2 ] < − sup [−ha; xi : x ∈ C1 ]
⇔ sup [ha; yi : y ∈ C2 ] < inf [ha; xi : x ∈ C1 ] .

On a donc la séparation forte entre C1 et C2 et donc la séparation propre.

b) Supposons 0 ∈ Fr(C). Comme int(C) 6= ∅ alors il existe un hyperplan qui supporte propre-
ment C en 0.
C’est-à-dire il existe a 6= 0 tel que

sup [ha; zi : z ∈ C] ≤ 0 et inf [ha; zi : z ∈ C] < 0.

2.2. SÉPARATION DE DEUX ENSEMBLES 25

C’est-à-dire

sup [ha; yi : y ∈ C2 ] ≤ inf [ha; xi : x ∈ C1 ]

et
inf [ha; yi : y ∈ C2 ] < sup [ha; xi : x ∈ C1 ] .
D’où le résultat. ¤

Théorème 2.2.5 (séparation forte de deux convexes)

Soit C1 un convexe fermé et C2 un convexe compact. Si C1 et C2 sont disjoints alors on peut les
séparer fortement. C’est-à-dire qu’il existe a 6= 0 dans Rn tel que

inf ha; xi > sup ha; yi.

x∈C1 y∈C2

Preuve : Soit C = C2 − C1 . Il est convexe et 0 ∈ / C. Montrons que C est fermé.

Soit {z } une suite de points de C qui converge vers z.
k

Il existe alors {xk } ⊂ C1 et {y k } ⊂ C2 telles que z k = y k − xk pour tout k ∈ N.

Comme C2 est compact, il est borné. Donc {y k } contient une sous suite convergente. Soit {y kl }
une telle sous suite et y sa limite. Comme C2 est aussi fermé, y ∈ C2 .
On a {z k } qui converge vers z, donc la sous suite {z kl } converge aussi vers z et la sous suite
{xkl = y kl − z kl } converge vers x = y − z. Comme C1 est fermé, x ∈ C1 . Par suite z = y − x ∈ C.
Donc C est fermé.
C est donc un convexe fermé ne contenant pas 0. On peut donc séparer fortement 0 de C. Ce
qui donne le résultat ¤

Remarque 2.2.4 On a le même résultat si on suppose que C1 et C2 sont convexes non vides
disjoints avec C2 − C1 fermé.

Pour démontrer le théorème de Farkas et Minkowski ci-dessous on admet le résultat suivant.

Proposition 2.2.5 Soit A une matrice. Alors l’ensemble

{Ax : x ≥ 0}

est un convexe fermé non vide.

Le théorème de Farkas et Minkowski concerne l’existence d’une solution non négative pour un
système linéaire.

Théorème 2.2.6 (Théorème de Farkas et Minkowski)

Soit A ∈ Mm,n (R) et b ∈ Rm . Une condition nécessaire et suffisante pour que le système

Ax = b, x ≥ 0 (2.5)

ait une solution est que :

∀ u = (u1 , · · · , um ) tel que uA ≥ 0, on ait ub ≥ 0. (2.6)

26 CHAPITRE 2. PROJECTION ET SÉPARATION

Preuve :
• La condition est nécessaire.
Si le système (2.5) a une solution x̄, alors pour tout u tel que uA ≥ 0, ub = uAx̄ ≥ 0. Ce qui
montre que la condition (2.6) est vérifiée.
• La condition est suffisante
Montrons que si (2.5) n’a pas de solution alors (2.6) n’est pas vérifiée.
L’ensemble S = {y : y = Ax, x ≥ 0} est un convexe fermé et le vecteur b est tel que : b ∈ / S.
En vertu du théorème de séparation point convexe fermé, il existe a ∈ R , a 6= 0 et α un scalaire
n

tels que aT b > α et aT y ≤ α ∀ y ∈ S. Puisque 0 ∈ S, on doit avoir α ≥ 0, et par suite aT b > 0.

D’autre part, on doit avoir : aT Ax ≤ α, ∀ x ≥ 0 ce qui implique aT A ≤ 0. En posant u = −aT , on
voit que l’on a mis ainsi en évidence un m− vecteur ligne qui ne vérifie pas (2.6) ¤

Remarque 2.2.5 Le théorème de Farkas et Minkowski admet un certain nombre de variantes qui
toutes, peuvent se ramener très aisemen à l’énoncé précédent.

Proposition 2.2.6 Soit A ∈ Mm,n (R) et b ∈ Rm . Une condition nécessaire et suffisante pour que
le système Ax ≤ b, x ≥ 0 ait une solution est que :

∀ u = (u1 , · · · , um ) ≥ 0 tel que uA ≥ 0, on ait ub ≥ 0.

Proposition 2.2.7 Soit A ∈ Mm,n (R) et b ∈ Rm . Une condition nécessaire et suffisante pour que
le système Ax ≤ b ait une solution est que :

∀ u = (u1 , · · · , um ) ≥ 0 tel que uA = 0, on ait ub ≥ 0.

Chapitre 3

Cônes convexes

Nous nous intéressons ici aux cônes convexes et particulièrement aux cônes polaires, tangents
et normaux. Bien avant nous donnons quelques définitions générales sur les cônes.

3.1 Généralités sur les cônes

Définition 3.1.1 On dit qu’un ensemble A ⊂ Rn est un cône de sommet a ∈ Rn si pour tout
x ∈ A et pour tout λ > 0, a + λ(x − a) ∈ A.

En pratique lorsqu’on parle de cône sans préciser le sommet il s’agit d’un cône de sommet
a = 0. C’est-à-dire un ensemble A tel que pour tout x ∈ A et λ > 0, λx ∈ A.
On remarque que :

Remarque 3.1.1 A est un cône de sommet a si et seulement si A − a est un cône de sommet 0.

Définition 3.1.2 On dit qu’un cône K de sommet l’origine est dit pointé si pour tout x ∈ K,
x 6= 0 alors −x ∈
/ K. C’est-à-dire que K ∩ (−K) = {0}.

Remarque 3.1.2 Un cône pointé est toujours contenu dans un demi-espace fermé.

On a les propriétés suivantes, qui sont faciles à démontrer.

Proposition 3.1.1 1) L’image d’un cône par une application linéaire est un cône.
2) Une combinaison linéaire d’un nombre fini de cônes est un cône.
3) L’intersection d’une famille quelconque de cônes est un cône.
4) La réunion d’une famille quelconque de cônes est un cône.
5) L’enveloppe convexe d’un cône est un cône.
6) L’adhérence d’un cône est un cône.

on a la caractérisation suivante des cônes convexes.

Proposition 3.1.2 Un cône K est convexe si et seulement si K + K ⊂ K.

27
28 CHAPITRE 3. CÔNES CONVEXES

Preuve : Soit K un cône. Supposons que K est convexe.

Soient x et y deux éléments de K. Comme K est convexe alors
(1 − λ)x + λy ∈ K pour tout λ ∈ [0; 1]
donc en particulier pour λ = 21 . Alors 21 x + 12 y ∈ K. Par suite
1 1
x + y = 2( x + y) ∈ K.
2 2
Réciproquement supposons que K + K ⊂ K. Si x et y sont dans K, alors comme K est un
cône, (1 − λ)x et λy appartiennent à K pour tout λ ∈]0; 1[. La condition K + K ⊂ K implique
alors que (1 − λ)x + λy ∈ K. Par suite K est convexe. ¤
On a les propriétés suivantes :

Proposition 3.1.3 1) L’image par une application linéaire d’un cône convexe est un cône convexe.
2) L’intersection de cônes convexes est un cône convexe.
3) Si K est un cône convexe, alors K est un cône convexe.
4) L’enveloppe convexe d’un cône est un cône convexe.

Définition 3.1.3 Soit S ⊂ Rn . On appelle enveloppe conique de S, l’intersection de tous les cônes
contenant S. C’est le plus petit cône qui contient S.
On appelle cône généré ou engendré par S, le cône obtenu en adjoignant l’origine à l’enveloppe
conique de S.

On a les propositions suivantes.

Proposition 3.1.4 Soit S ⊂ Rn , S 6= ∅. Alors

1) L’enveloppe conique de S est égale à ∪ λS = R∗+ S.
λ>0
2) Le cône généré par S est égal à ∪ λS = R+ S.
λ≥0

Proposition 3.1.5 Si S est convexe alors l’enveloppe conique de S et le cône généré par S sont
convexes.

Définition 3.1.4 Soit S ⊂ Rn . On appelle enveloppe conique convexe de S, l’intersection de tous

les cônes convexes contenant S. C’est le plus petit cône convexe qui contient S.
On appelle cône convexe généré ou engendré par S, le cône convexe obtenu en adjoignant
l’origine à l’enveloppe conique convexe de S. On le note cone(S).

Proposition 3.1.6 Soit S ⊂ Rn , S 6= ∅. Alors

1) L’enveloppe conique convexe de S est égale à l’enveloppe conique de conv(S) elle donc égale à
∪ λconv(S) = R∗+ conv(S).
λ>0
2) Le cône convexe généré par S est égal au cône généré par conv(S). On a donc

cone(S) = ∪ λconv(S) = R+ conv(S).

λ≥0

ou encore ( )
xi ∈ S, i = 1, · · · , k, X k
∗
cone(S) = x : ∃k ∈ N , :x= λi xi
λi ≥ 0, i = 1, · · · , k, i=1
3.2. CÔNES ASYMPTOTES 29

Définition 3.1.5 Soit S ⊂ Rn . On appelle cône convexe fermé généré ou engendré par S, l’in-
tersection de tous les cônes convexes fermés contenant S. C’est le plus petit cône convexe fermé
qui contient S. On le note cone(S).

Proposition 3.1.7 On a cone(S) = cone(S).

3.2 Cônes asymptotes

On a le résultat suivant :

Proposition 3.2.1 Soit C un sous ensemble convexe non vide de Rn et a ∈ C. L’ensemble

C∞ (a) = {d ∈ Rn : a + λd ∈ C, ∀ λ ≥ 0}

est un cône convexe.

Preuve : Il est immédiat que pour tout d ∈ C∞ (a) et tout α > 0, on a αd ∈ C∞ (a). Il reste donc
à montrer que
C∞ (a) + C∞ (a) ⊂ C∞ (a).
Soit d, δ ∈ C∞ (a). Considérons λ > 0.
On a
a + 2λd ∈ C et a + 2λδ ∈ C.
Alors comme C est convexe, on a
1 1
a + λ(d + δ) = (a + 2λd) + (a + 2λδ) ∈ C.
2 2
Donc d + δ ∈ C∞ (a). ¤

Exemple 3.2.1 Soit C = {(x, y) : x > 0, y > 0} ∪ {(0, 0)}.

On a
C∞ (0, 0) = {d : d1 > 0, d2 > 0} ∪ {(0, 0)},
et
C∞ (1, 1) = {d : d1 ≥ 0, d2 ≥ 0}.

Remarque 3.2.1 En général pour un sous ensemble convexe C et a 6= b, on a : C∞ (a) 6= C∞ (b).

On définit le cône asymptote

Définition 3.2.1 Soit C un sous ensemble convexe non vide de Rn . On appelle cône asymptote
ou de récession de C, le cône convexe

C∞ = ∩ C∞ (a).
a∈C

Les éléments de C∞ sont appelés directions asymptotes ou de récession de C.

30 CHAPITRE 3. CÔNES CONVEXES

Théorème 3.2.1 Soit C un sous ensemble convexe fermé non vide de Rn . Alors on a pour tout
a, b ∈ C, C∞ (a) = C∞ (b) et C∞ est un cône convexe fermé.

Preuve : Soit d ∈ C∞ (a), montrons que d ∈ C∞ (b). Soit donc λ > 0. Montrons que b + λd ∈ C.
Comme d ∈ C∞ (a) alors pour tout k ∈ N∗ , a + λkd ∈ C.
Comme C est convexe alors
1 1
xk = (a + λkd) + (1 − )b ∈ C.
k k
On a
1 1
xk = a + λd + (1 − )b −→ b + λd.
k k
Comme C est fermé, alors b + λd ∈ C. Par suite d ∈ C∞ (b) et donc C∞ (a) ⊂ C∞ (b).
En échangeant les rôles de a et b, on montre de la même façon que

C∞ (b) ⊂ C∞ (a).

D’où l’égalité.
Montrons à présent que C∞ est fermé.
Soit a ∈ C. On sait que C∞ = C∞ (a). Montrons alors que C∞ (a) est fermé.
Soit d ∈ C∞ (a). Il existe alors {dk } une suite d’éléments de C∞ (a) qui converge vers d.
Soit λ > 0. Comme pour tout k, dk ∈ C∞ (a), alors a + λdk ∈ C. Donc,

lim (a + λdk ) = a + λd ∈ C = C,
k−→+∞

car C est fermé. Donc d ∈ C∞ (a). Par suite C∞ (a) ⊂ C∞ (a). ¤

On montre facilement que

Proposition 3.2.2 Soient C et D deux convexes fermés de Rn avec C ∩ D 6= ∅. On a (C ∩ D)∞ =

C∞ ∩ D∞ .

Théorème 3.2.2 Soit C un convexe fermé non vide de Rn . C est borné si et seulement si C∞ =
{0}.

Preuve : Supposons C borné et d ∈ C∞ . Alors pour tout λ ≥ 0, a + λd ∈ C. Donc nécessairement

d = 0.
Réciproquement supposons par contradiction que C est non borné et montrons alors que C∞ 6=
{0}.
Comme C est non borné alors pour tout k ∈ N il existe xk ∈ C tel que kxk − ak ≥ k.
Soit
k xk − a
d = k .
kx − ak
On a pour tout k, kdk k = 1. Donc la suite {dk } est bornée. Il existe alors une sous suite convergente.
Soit {dkl } une telle sous suite et d sa limite. On a kdk = 1.
Soit λ > 0 et pour tout l, posons

λ
tkl = .
kxkl − ak
3.3. CÔNES POLAIRES 31

On a
lim kxkl − ak = +∞.
l−→+∞

Cela implique qu’il existe l0 tel que pour tout l ≥ l0 , on a tkl ∈]0; 1[.
Soit
akl = a + kxkl − akdkl .
On a akl ∈ C pour tout l. Et comme a ∈ C, on a pour tout l ≥ l0 ,

tkl akl + (1 − tkl )a ∈ C

en tant que combinaison linéaire convexe de deux éléments de C. C’est-à-dire que

a + tkl kxkl − akdkl ∈ C.

Ce qui implique que

lim a + tkl kxkl − akdkl = a + λd ∈ C = C.
l−→+∞

Donc d ∈ C∞ . Comme kdk = 1, alors d 6= 0 et C∞ 6= {0}. ¤

3.3 Cônes polaires

On montre que

Proposition 3.3.1 Si C est un sous ensemble non vide de Rn , l’ensemble

{x∗ ∈ Rn : hx∗ ; xi ≤ 0 ∀x ∈ C}

est un cône.

on définit :

Définition 3.3.1 Soit C un sous ensemble non vide de Rn On appelle cône polaire (ou cône
polaire négatif ) de C l’ensemble

C ◦ = {x∗ ∈ Rn : hx∗ ; xi ≤ 0 ∀x ∈ C}.

Par convention, si C = ∅, C ◦ = Rn .
Les propositions suivantes sont immédiates.

Proposition 3.3.2 Soit C un sous ensemble non vide de Rn alors C ◦ est un cône convexe fermé
contenant 0.

Proposition 3.3.3 Soient C1 et C2 deux sous ensembles non vides de Rn . Si C1 ⊂ C2 , alors

C2◦ ⊂ C1◦ .

On montre aussi
32 CHAPITRE 3. CÔNES CONVEXES

Proposition 3.3.4 Si C est un sous ensemble non vide de Rn alors on a

◦
1) C ◦ = C ,
2) C ⊂ C ◦◦ .

Proposition 3.3.5 Soient K1 et K2 deux cônes non vides de Rn . On a

(K1 + K2 )◦ = K1◦ ∩ K2◦ = (K1 ∪ K2 )◦ .

Preuve : Soit x∗ ∈ (K1 + K2 )◦ . On a donc

hx∗ , c1 + c2 i ≤ 0 ∀c1 ∈ K1 , ∀c2 ∈ K2 .

Comme K1 et K2 sont des cônes alors

∀λ > 0, ∀ c1 ∈ K1 , ∀ c2 ∈ K2 , λc1 + c2 ∈ (K1 + K2 ).

Alors
hx∗ , λc1 + c2 i ≤ 0 ∀λ > 0, ∀ c1 ∈ K1 , ∀ c2 ∈ K2 .
Soit
λhx∗ , c1 i + hx∗ , c2 i ≤ 0 ∀λ > 0, ∀ c1 ∈ K1 , ∀ c2 ∈ K2 .
En faisant tendre λ vers 0, on obtient

hx∗ , c2 i ≤ 0 ∀ c2 ∈ K2 .

C’est-à-dire que x∗ ∈ K2◦ .

De façon analogue, on montre que x∗ ∈ K1◦ . Par suite

x∗ ∈ K1◦ ∩ K2◦ .

D’où l’inclusion
(K1 + K2 )◦ ⊂ K1◦ ∩ K2◦ .
L’autre inclusion
K1◦ ∩ K2◦ ⊂ (K1 + K2 )◦
est immédiate. On a donc
K1◦ ∩ K2◦ = (K1 + K2 )◦ .
A présent montrons que
K1◦ ∩ K2◦ = (K1 ∪ K2 )◦ .
Les ensembles K1 et K2 sont contenus dans K1 ∪ K2 donc

(K1 ∪ K2 )◦ ⊂ K1◦ et (K1 ∪ K2 )◦ ⊂ K2◦ .

On tire alors que

(K1 ∪ K2 )◦ ⊂ K1◦ ∩ K2◦ .
On montre facilement que
K1◦ ∩ K2◦ ⊂ (K1 ∪ K2 )◦ .
Ce qui termine la démonstration. ¤
3.3. CÔNES POLAIRES 33

Théorème 3.3.1 Soit C un sous ensemble non vide de Rn et K le cône engendré par C. On a

C ◦ = (conv(C))◦ = (conv(C))◦ = K ◦ = (cone(C))◦ = (cone(C))◦ .

Preuve :
a) Montrons que C ◦ = (conv(C))◦ .
On a
C ⊂ conv(C),
donc
(conv(C))◦ ⊂ C ◦ .
Réciproquement Psoit x∗ ∈ C ◦ et x ∈ conv(C). Il existe alors k ∈ N, xi ∈ C, λi ≥ 0 pour
i = 1, · · · , k, avec ki=1 λi = 1 tels que

X
k
x= λi xi .
i=1

Donc
X
k
∗
hx , xi = λi hx∗ , xi i.
i=1

Comme x∗ ∈ C ◦ , alors on a pour tout i, hx∗ , xi i ≤ 0.

D’où
X k
λi hx∗ , xi i ≤ 0.
i=1

C’est-à-dire que hx , xi ≤ 0. Donc x ∈ (conv(C))◦ .

∗ ∗

b) On sait que
conv(C) = conv(C).
Ce qui donne immédiatement

(conv(C))◦ = (conv(C))◦ = (conv(C))◦ .

c) Montrons que C ◦ = K ◦ .
On a l’inclusion K ◦ ⊂ C ◦ .
Réciproquement, soit
x∗ ∈ C ◦ et x ∈ K = ∪ λC.
λ≥0

Alors il existe λ ≥ 0 et y ∈ C tels que x = λy. Comme y ∈ C alors hx∗ , yi ≤ 0. Donc

hx∗ , xi = λhx∗ , yi ≤ 0.

Par suite x∗ ∈ K ◦ .
e) Montrons à présent qu’on a
C ◦ = (cone(C))◦ .
On sait que le cône convexe engendré par C est égal au cône engendré par conv(C). Donc d’après
c), on a
(cone(C))◦ = (conv(C))◦ = C ◦ .
f) On a
cone(C) = cone(C).
34 CHAPITRE 3. CÔNES CONVEXES

Donc
(cone(C))◦ = (cone(C))◦ = (cone(C))◦ = C ◦ .
Ce qui termine la démonstration ¤
Cette proposition signifie qu’une partie, son enveloppe convexe, son enveloppe convexe fermée,
le cône qu’elle engendre, le cône convexe qu’elle engendre et le cône convexe fermé qu’elle engendre
ont le même polaire.

Théorème 3.3.2 Soit C un sous ensemble de Rn . Alors C = C ◦◦ si et seulement si C est un

cône convexe fermé.
Preuve : Si C = C ◦◦ , il est immédiat que C, en tant que polaire d’un ensemble est un cône
convexe fermé.
Réciproquement supposons que C est un cône convexe fermé. Montrons qu’on a C = C ◦◦ .
Si C est un cône convexe fermé alors on a C = cone(C). Il revient donc à montrer que
cone(C) = cone(C)◦◦ .
On a une première inclusion
cone(C) ⊂ cone(C)◦◦ .
Soit x ∈ cone(C)◦◦ . Alors
hx∗ , xi ≤ 0 ∀x∗ ∈ cone(C)◦ .
Si x ∈
/ cone(C), d’après le théorème de séparation forte point convexe fermé, il existe a ∈ Rn non
nul tel que
ha, zi < ha, xi ∀z ∈ cone(C).
On a donc
ha, zi ≤ 0 ∀z ∈ cone(C).
Car sinon, on aurait ha, z̄i > 0 pour un z̄ ∈ cone(C) et comme cone(C) est un cône, on λz̄ ∈
cone(C) pour tout λ positif. Donc
ha, λz̄i < ha, xi ∀ λ > 0.
Par passage à la limite on aboutit à une contradiction.
On a alors a ∈ cone(C)◦ , et donc ha, xi ≤ 0.
D’autre part, on a 0 ∈ cone(C). Par conséquent
0 < ha, xi.
Ce qui est en contradiction avec
a ∈ cone(C)◦ et x ∈ cone(C)◦◦ .
Donc x ∈ cone(C). Ce qui donne la seconde inclusion recherchée. ¤
On montre que

Proposition 3.3.6 Si C1 et C2 sont deux cônes, alors

C1◦ + C2◦ = conv(C1◦ ∪ C2◦ ) ⊂ (C1 ∩ C2 )◦ .

Proposition 3.3.7 Si C1 et C2 sont deux cônes convexes fermés d’intersection non vide, alors

(C1 ∩ C2 )◦ = C1◦ + C2◦ = conv(C1◦ ∪ C2◦ ).

3.4. CÔNES POLYÉDRIQUES 35

3.4 Cônes polyédriques

Il existe une famille de cônes beaucoup utilisés en analyse convexe, les cônes engendrés par
un nombre fini de points. On les appelle cônes polyédriques. On considère bien avant la notation
suivante.
Notation : Pour u et v dans Rn , on notera u ≤ v si et seulement si ui ≤ vi pour tout
i = 1, · · · , n.
considérons le résultat suivant.

Proposition 3.4.1 Soit A une matrice. Alors l’ensemble

{Ax : x ≥ 0}

est un cône convexe fermé non vide.

Preuve : Il est immédiat que c’est un cône convexe non vide. Aussi il est fermé d’après la
proposition (2.2.5).
On définit le cône polyédrique comme suit.

Définition 3.4.1 Un sous ensemble C est un cône polyédrique s’il existe une matrice A telle que

C = {Ax : x ≥ 0} .

On montre que

Proposition 3.4.2 Si A ∈ Mn,m (R), alors l’ensemble

© ª
C = x : x ≥ 0, AT x = 0

est un cône polyédrique.

Preuve : Si C = {0}, c’est terminé, car il est évident que C est un cône polyédrique.
Supposons que C 6= {0}. Considérons

S = {x : x ≥ 0, AT x = 0, he, xi = 1}

où e est le vecteur de Rn dont toutes les composantes sont égales à 1. Notons qu’un élément non
nul x appartient à C si et seulement si x/he, xi ∈ S.
Comme C 6= {0} alors S est un polyèdre convexe fermé non vide et borné. Il est donc combi-
naison linéaire convexe d’un nombre fini de points soit {b1 , b2 , · · · , bk }. P
Si x ∈ C alors il existe µ ≥ 0 et y ∈ S tels que x = µy. Donc on peut écrire x = ki=1 λi bi
où λi ≥ 0 pour tout i ∈ {1, · · · , k}. Autrement dit on a C ⊂ {x : x = Bλ, λ ≥ 0} où
B = (b1 , b2 , · · · , bk ). P
Réciproquement soit x tel que x = Bλ où λ ≥ 0. Supposons λ 6= 0. Alors x/ ki=1 λi qui
est une combinaison linéaire convexe de {b1 , b2 , · · · , bk } est dans S. Donc x ∈ C et on obtient
C = {x : x = Bλ, λ ≥ 0} ce qui prouve en effet que C est un cône polyédrique. ¤

Proposition 3.4.3 Si L est un sous espace vectoriel de Rn alors l’ensemble

C = {x : x ≥ 0, x ∈ L}

est un cône polyédrique

36 CHAPITRE 3. CÔNES CONVEXES

Preuve : Considérons L⊥ l’orthogonal de L. C’est un sous espace vectoriel de Rn .

Soit {b1 , b2 , · · · , bm } une de ses bases. On a alors L⊥ = {By, y ∈ Rm } où B = (b1 , b2 , · · · , bm )
est une matrice (n, m).
Soit D = {x : B T x = 0, x ≥ 0}. Si x ∈ C, comme pour tout i ∈ {1, 2, · · · , m}, bi ∈ L⊥ et
x ∈ L alors on a hx, bi i = 0, il vient B T x = 0 et donc x ∈ D.
A présent soit x ∈ D. Considérons y ∈ L⊥ . Puisque B = (b1 , b2 , · · · , bm ) est une base de
L⊥ , alors y = Bz où z ∈ Rm . On a donc hx, yi = hx, Bzi = hB T x, zi = 0 car x ∈ D. Alors
x ∈ L⊥⊥ = L et donc x ∈ C. On a alors C = D et donc c’est un cône polyédrique. ¤

Théorème 3.4.1 Soit C = {x : Bx ≤ 0} où B ∈ Mm,n (R). Alors C est un cône polyédrique.

Preuve : Nous devons montrer que C peut se mettre sous la forme {F z : z ≥ 0} où F est une
n × k matrice. A présent considérons l’ensemble suivant : S = {y : y = Bx, x ∈ Rn }. On a
S = {x ∈ L : x ≥ 0} où L = Im(B). D’après la proposition (3.4.3), S est un cône polyédrique.
Alors on peut écrire S = {Az : z ≥ 0} où A est une m × k1 matrice de colonnes a1 , a2 , · · · , ak1 .
Tous les ai sont dans S il suffit de constater que ai = Bei où ei est le ieme vecteur de la base
canonique de Rk1 . Alors pour tout i, on a bi ≥ 0 et ai = Bxi où xi est dans Rn . Ce qui veut dire
que A = BD où D est la matrice d’ordre (n, k1 ) de colonnes x1 , x2 , · · · , xk1 .
Considérons maintenant le sous espace vectoriel L = {x : Bx = 0}. Il peut être mis sous la
forme L = {Ez : z ≥ 0}, en prenant E la n × k2 matrice dont les colonnes constituent une base
de L.
C est le cône polyédrique représenté par {F z : z ≥ 0} où F = (−D, E) est une matrice n × k
avec k = k1 + k2 . En effet si x ∈ C, on a y = −Bx ≥ 0. Donc y ∈ S et donc y = Az1 pour un
k1 vecteur z1 ≥ 0. Mais alors −Bx = y = BDz1 c’est-à-dire B(x + Dz1 ) = 0. Ce qui signifie que
x + Dz1 ∈ L et alors x + Dz1 = Ez2 pour un k2 vecteur z2 ≥ 0. C’est-à-dire x = −Dz1 + Ez2 = F z
avec z T = (z1T , z2T ) ≥ 0. Donc C ⊂ {F z : z ≥ 0}.
Réciproquement considérons le vecteur F z = −Dz1 + Ez2 avec z1 , z2 ≥ 0. Alors on a

BF z = −BDz1 + BEz2 .

Mais notons que Ez2 ∈ L puisque z2 ≥ 0. Donc on a AEz2 = 0. Aussi notons que BD = A et
donc −BDz1 = −Az1 . Mais Az1 ∈ S et donc Az1 ≥ 0 c’est-à-dire −Az1 ≤ 0. Ce qui prouve que
BF z ≤ 0 et par suite {Ez : z ≥ 0} ⊂ C. Ce qui termine la démonstration ¤

Proposition 3.4.4 Soit

© ª
K = {Ax : x ≥ 0} et C = y : AT y ≤ 0 .

On a K ◦ = C et C ◦ = K.

Preuve : Soit y ∈ C. Alors pour z ∈ K, on a

hy, zi = hy, Axi = hAT y, xi ≤ 0

puisque
AT y ≤ 0 et x ≥ 0.
Donc C ⊂ K ◦ . Montrons à présent que K ◦ ⊂ C. Soit y ∈ K ◦ : alors

hy, Axi ≤ 0 ∀ x ≥ 0.
3.5. CÔNES TANGENTS 37

Ceci implique que AT y ≤ 0 car sinon on aurait

hy, Aj i > 0

pour une colonne Aj de la matrice A. En prenant x tel que sa j ieme composante est strictement
positive et toutes les autres égales à 0 on aura

hy, Axi > 0,

ce qui contredit le fait que y ∈ K ◦ Ce qui montre que K ◦ ⊂ C.

Comme K est un cône convexe fermé, on a K ◦◦ = K et on déduit C ◦ = K ◦◦ = K. ¤

Proposition 3.4.5 Si C est cône polyédrique, on a C = C ◦◦ .

Preuve : Le résultat vient du fait qu’un cône polyédrique est un cône convexe fermé. ¤

Proposition 3.4.6 Si C1 et C2 sont deux cônes polyédriques alors C1 +C2 est un cône polyédrique.

Preuve : Montrons que C1 + C2 est un cône polyédrique. On peut supposer qu’il existe deux
matrices A1 et A2 telles que

C1 = {A1 x : x ≥ 0} et C2 = {A2 y : y ≥ 0} .

On a alors
C1 + C2 = {A1 x + A2 y : x ≥ 0, y ≥ 0} = {Az : z ≥ 0}
avec µ ¶
x
A = (A1 , A2 ) et z = .
y
Donc C1 + C2 est un cône polyédrique. ¤

Proposition 3.4.7 Si C1 et C2 sont des cônes polyédriques, alors C1 ∩C2 est un cône polyédrique.

Proposition 3.4.8 Si C1 et C2 sont des cônes polyédriques, alors C1◦ et C2◦ sont des cônes
polyédriques et
a) (C1 + C2 )◦ = C1◦ ∩ C2◦ ,
b) (C1 ∩ C2 )◦ = C1◦ + C2◦ .

3.5 Cônes tangents

Les cônes tangents interviennent dans les conditions d’optimalité des problèmes d’optimisation.
On définit

Définition 3.5.1 Soit S un sous ensemble non vide de Rn et a ∈ Rn .

Un vecteur d ∈ Rn est dit vecteur tangent à S en a, s’il existe une suite {dk } de Rn tendant
vers d, une suite {λk } de R∗+ tendant vers 0 telles que

a + λk dk ∈ S ∀ k ∈ N.
38 CHAPITRE 3. CÔNES CONVEXES

On montre facilement que

Proposition 3.5.1 L’ensemble des vecteurs tangents à S en a, est un cône.

Preuve : Soit d un vecteur tangent à S en a et λ > 0.

Par définition,
∃ {dk } ⊂ Rn , dk −→ d,
: a + λk dk ∈ S ∀ k ∈ N.
∃ {λk } ⊂ R∗+ , λk −→ 0,
Posons δ k = λdk et µk = λ1 λk . On a

lim δ k = λd, lim µk = 0, µk > 0

k−→+∞ k−→+∞

et
a + µk δ k = a + λk dk ∈ S ∀k ∈ N.
Par suite λd est un vecteur tangent à S en a. ¤

Définition 3.5.2 Soit S un sous ensemble non vide de Rn et a ∈ Rn .

On appelle cône tangent à S en a l’ensemble noté T (S, a) ou TS (a) des vecteurs tangents à S
en a. On a alors
( )
∃ {dk
} ⊂ R n
, d k
−→ d,
T (S, a) = d ∈ Rn : : a + λk dk ∈ S ∀ k ∈ N .
∃ {λk } ⊂ R∗+ , λk −→ 0,

On peut montrer que :

Proposition 3.5.2 Si S est un sous ensemble non vide de Rn et a ∈ Rn ,

T (S, a) ⊂ R∗+ (S − a).

On a les propriétés suivantes :

Proposition 3.5.3 Soit S un sous ensemble de Rn , Alors T (S, a) est un cône fermé.

Preuve : Il reste à montrer que T (S, a) est fermé.

Soit d ∈ T (S, a). Alors

1
∀k > 0, ∃ dk ∈ T (S, a) : kdk − dk ≤ .
2k
Aussi
1 1
dk ∈ T (S, a) ⇒ ∃µk ∈]0, [, ∃δ k ∈ Rn : kδ k − dk k ≤ et a + µk δ k ∈ S.
k 2k
On a alors µk −→ 0.
Comme
1
kδ k − dk ≤ kδ k − dk k + kdk − dk ≤ ,
k
on a aussi δ k −→ d. Il s’ensuit que d ∈ T (S, a) qui est donc fermé. ¤
3.5. CÔNES TANGENTS 39

Proposition 3.5.4 Soit S un sous ensemble non vide de Rn et a ∈ Rn .

1) Si a ∈
/ S alors T (S, a) = ∅.
2) Si a ∈ int(S), alors T (S, a) = Rn .
3) Si a ∈ S alors 0 ∈ T (S, a).
4) Si a est un point isolé de S alors T (S, a) = {0}.

Preuve : 1) Soit a ∈
/ S. S’il existe d ∈ T (S, a), alors il existe

{dk } ⊂ Rn , dk −→ d,

une suite
{λk } ⊂ R∗+ , λk −→ 0
telles que
ak = a + λk dk ∈ S ∀ k ∈ N.
On a
lim ak = a
k→+∞

donc a ∈ S. Ce qui n’est pas. Par suite T (S, a) = ∅.

2) Soit a ∈ int(S). Alors
∃r > 0 tel que B(a, r) ⊂ S.
Soit d ∈ Rn .
Si d = 0, soient λk = 1
k+1
et dk = 0 pour tout k ∈ N. On a

lim λk = 0, lim dk = 0 et a + λk dk = a ∈ S ∀ k ∈ N.
k→+∞ k→+∞

Donc d ∈ T (S, a).

Si d 6= 0, on considère dk = d et λk = r
(k+1)kdk
pour tout k ∈ N et soit

r
ak = a + λk dk = a + d.
(k + 1)kdk

On a pour tout k,
r
kak − ak = ≤r:
k+1
et donc
ak ∈ B(a, r) ⊂ S.
Par conséquent d ∈ T (S, a). Ce qui implique que

Rn ⊂ T (S, a).

Donc
T (S, a) = Rn .

3) On suppose que a ∈ S.
Soit λk une suite strictement positive et tendant vers 0. Comme a ∈ S, pour tout k,

∃ak ∈ S tel que kak − ak ≤ λ2k .

40 CHAPITRE 3. CÔNES CONVEXES

Posons
1 k
dk = (a − a).
λk
On a
kak − ak
kdk k = ≤ λk −→ 0.
λk
Donc dk −→ 0.
On a d’autre part
a + λk dk = a + ak − a = ak ∈ S, ∀ k.
Donc 0 ∈ T (S, a).
4) Soit a un point isolé de S. Cela veut dire qu’il existe r > 0 tel que

B(a, r) ∩ S = {a}.

Si d ∈ T (S, a), avec d 6= 0, alors il existe une suite

{dk } ⊂ Rn , dk −→ d,

une suite
{λk } ⊂ R∗+ , λk −→ 0
telles que
ak = a + λk dk ∈ S ∀ k ∈ N.
On a alors
lim ak = a.
k→+∞

Donc on peut trouver pour k suffisamment grand,

ak ∈ B(a, r) ∩ S

avec ak 6= a. Ce qui est en contradiction avec le fait que

B(a, r) ∩ S = {a}.

Ce qui termine la démonstration ¤

On a encore les propriétés suivantes :

Proposition 3.5.5 Soient A et B deux sous ensembles de Rn .

1) Si A ⊂ B alors T (A, a) ⊂ T (B, a) ;
2) T (A ∩ B, a) ⊂ T (A, a) ∩ T (B, a) ;
3) T (A, a) = T (A ∩ V, a), ∀V ∈ V(a). (V(a) désigne l’ensemble des voisinage du point a) ;
4) T (A, a) = T (A, a) ;
5) T (A ∪ B, a) = T (A, a) ∪ T (B, a) ;

Preuve : Les propositions 1) et 2) sont immédiates.

3) Soit V ∈ V(a). On a A ∩ V ⊂ A. Donc

T (A ∩ V, a) ⊂ T (A, a).
3.5. CÔNES TANGENTS 41

Soit à présent d ∈ T (A, a). Par définition

∃ {dk } ⊂ Rn , dk −→ d,
: a + λk dk ∈ A, ∀ k ∈ N.
∃ {λk } ⊂ R∗+ , λk −→ 0,

On a
lim a + λk dk = a.
k→+∞

Comme V est un voisinage de a,

∃k0 ∈ N : ∀ k ≥ k0 , a + λk dk ∈ A ∩ V.

Considérons
δ k = dk0 +k , et µk = λk0 +k .
On a
{δ k } ⊂ Rn , {µk } ⊂ R∗+ , δ k −→ d, µk −→ 0,
et
a + µk δ k ∈ A ∩ V ∀ k ∈ N.
Donc
d ∈ T (A ∩ V, a).
D’où l’égalité
T (A, a) = T (A ∩ V, a).

4) On a
T (A, a) ⊂ T (A, a)
car A ⊂ A.
Soit d ∈ T (A, a).

∃ {dk } ∈ Rn : kdk − dk ≤ 1
, ∀k >0
2k : a + λk dk ∈ A ∀ k ∈ N∗ .
∃ λk ∈ R∗+ , λk −→ 0,

On sait que
1 1
(A − a) = (A − a).
λk λk
Comme
1 1
a + λk dk ∈ A ⇔ dk ∈ (A − a) = (A − a),
λk λk
alors
1 1
∀k ∃ δ k ∈ (A − a) : kdk − δ k k ≤ .
λk 2k
On a alors
1
kδ k − dk ≤ kδ k − dk k + kdk − dk ≤ .
k
Il s’ensuit que {δ k } converge vers d.
Par construction de la suite {δ k }, on a

a + λk δ k ∈ A ∀ k.

Donc
d ∈ T (A, a).
42 CHAPITRE 3. CÔNES CONVEXES

Par suite
T (A, a) ⊂ T (A, a)
et
T (A, a) = T (A, a).
5) Montrons que
T (A ∪ B, a) = T (A, a) ∪ T (B, a).
On a
A ⊂ A ∪ B et B ⊂ A ∪ B.
Donc
T (A, a) ⊂ T (A ∪ B, a) et T (B, a) ⊂ T (A ∪ B, a).
On obtient alors
T (A, a) ∪ T (B, a) ⊂ T (A ∪ B, a).
Réciproquement, soit d ∈ T (A ∪ B, a). Par définition,

∃ {dk } ⊂ Rn , dk −→ d,
: ak = a + λk dk ∈ A ∪ B, ∀ k ∈ N.
∃ {λk } ⊂ R∗+ , λk −→ 0,

La suite {ak } converge vers a. Elle est donc bornée. Aussi comme {ak } ⊂ A ∪ B, alors un des deux
ensembles A ou B soit A par exemple, contient une infinité des termes. On peut donc extraire de
cette partie une sous suite {akl } convergente. On considère les éléments associés {dkl } et {λkl }. Il
est immédiat que la sous suite {dkl } converge vers d et {λkl } vers 0. En outre on a

a + λkl dkl ∈ A ∀l ∈ N.

Et donc d ∈ T (A, a) ⊂ T (A, a) ∪ T (B, a). Ce qui donne l’inclusion inverse. Et donc on a l’égalité
recherchée. ¤
Dans certains cas le cône tangent est un cône convexe comme le montre la proposition ci-
dessous.

Proposition 3.5.6 Si C est un convexe non vide, de Rn , et a ∈ C alors T (C, a) est un cône
convexe fermé.

Preuve : On sait que T (C, a) est un cône fermé. Il reste à montrer qu’il est convexe. Pour cela il
suffit de montrer que
T (C, a) + T (C, a) ⊂ T (C, a).
Soient d et δ deux éléments de T (C, a).
Par définition, on sait que :

∃ {dk } ⊂ Rn , dk −→ d,
: a + αk dk ∈ C ∀ k ∈ N,
∃ {αk } ⊂ R∗+ , αk −→ 0,

et
∃ {δ k } ⊂ Rn , δ k −→ δ,
: a + βk δ k ∈ C ∀ k ∈ N.
∃ {βk } ⊂ R∗+ , βk −→ 0,
Soit
αk βk
λk = .
αk + βk
3.5. CÔNES TANGENTS 43

On a
λk > 0 ∀k, et λk −→ 0.
En outre on a
αk βk
a + λk (dk + δ k ) = a + (dk + δ k ).
αk + βk
Or
αk βk βk αk
a+ (dk + δ k ) = (a + αk dk ) + (a + βk δ k )
αk + βk αk + βk αk + βk
qui est une combinaison linéaire convexe de deux éléments de C et il appartient donc à C car il
est convexe.
Alors
a + λk (dk + δ k ) ∈ C ∀k ∈ N.
Donc T (C, a) est convexe. ¤
Plus précisément on a
Proposition 3.5.7 Si C est un convexe non vide de Rn et a ∈ C, alors

T (C, a) = R∗+ (C − a).

Preuve : On sait qu’on a l’inclusion
T (C, a) ⊂ R∗+ (C − a).
Posons K = R∗+ (C − a) et soit d ∈ K.
Alors
∃λ > 0 : a + λd ∈ C ⊂ C.
Comme C est convexe il en est de même pour C. Donc
λ 1 1
a + d = (1 − )a + (a + λd) ∈ C ∀k ∈ N∗
k k k
en tant que combinaison linéaire convexe de deux éléments de C.
Posons
λ
dk = d et λk = ∀k ∈ N∗ .
k
∗
La suite {λk } ⊂ R+ converge vers 0 et {d } converge vers d. De plus, on a
k

λ
a + λk dk = a + d ∈ C.
k
Donc
d ∈ T (C, a) = T (C, a).
Ce qui donne
K ⊂ T (C, a).
Mais comme T (C, a) est fermé, alors on a
K ⊂ T (C, a).
En conclusion on a
K = T (C, a).
D’où la proposition. ¤
A présent nous allons voir une autre famille de cônes convexe à savoir les cônes normaux.
44 CHAPITRE 3. CÔNES CONVEXES

3.6 Cônes normaux

On définit le vecteur normal à un ensemble en un point de la façon suivante.

Définition 3.6.1 Soit A un sous ensemble non vide de Rn et a ∈ A. On dit que x∗ ∈ Rn est un
vecteur normal à A en a, si
hx∗ , x − ai ≤ 0 ∀x ∈ A.

On montre facilement le résultat ci-dessous.

Proposition 3.6.1 Soit A un sous ensemble non vide de Rn et a ∈ A. L’ensemble

{x∗ ∈ Rn : hx∗ , x − ai ≤ 0 ∀x ∈ A},

des vecteurs normaux à A en a, est un cône convexe fermé non vide (il contient toujours 0).

Définition 3.6.2 Soit A un sous ensemble non vide de Rn et a ∈ A. L’ensemble des vecteurs
normaux à A en a est appelé cône normal à A en a. On le note N (A, a) ou NA (a).

On a les propriétés suivantes.

Proposition 3.6.2 Soit A un sous ensemble non vide de Rn et a ∈ A.

1) Si A ⊂ B alors N (B, a) ⊂ N (A, a).
2) N (A, a) = N (A, a).
3) Si a ∈ int(A) alors N (A, a) = {0}.
4) Si A = {a} alors N (A, a) = Rn .
5) N (A, a) = N (conv(A), a).
6) N (A, a) ⊂ T (A, a)◦ .

Preuve :
La proposition 1) est immédiate.
2) Comme A ⊂ A, d’après 1), on a l’inclusion

N (A, a) ⊂ N (A, a).

Soit x∗ ∈ N (A, a) et x ∈ A.
Alors,
∃{xk } ⊂ A : xk −→ x,
et donc
hx∗ , xk − ai ≤ 0 ∀k ∈ N.
Par passage à la limite, on obtient
hx∗ , x − ai ≤ 0.
Par suite x∗ ∈ N (A, a), et on a l’inclusion

N (A, a) ⊂ N (A, a).

D’où l’égalité
N (A, a) = N (A, a).
3.6. CÔNES NORMAUX 45

Les propositions 3) et 4) se démontrent facilement.

5) D’après 1) on a l’inclusion :
N (conv(A), a) ⊂ N (A, a).
Soit x∗ ∈ N (A, a).
Pour x ∈ conv(A),
X
p
∃p ∈ N, x ∈ A, λi ≥ 0, i = 1, · · · , p :
i
λi = 1,
i=1
tels que
X
p
x= λi xi .
i=1
On a alors
hx∗ , xi − ai ≤ 0 ∀i.
Donc
X
p
λi hx∗ , xi − ai ≤ 0.
i=1
Ce est équivalent à
X
p
∗
hx , λi (xi − a)i ≤ 0.
i=1
Soit
X
p
∗
hx , x − ai ≤ 0 car λi = 1 :
i=1
c’est-à-dire que
x∗ ∈ N (conv(A), a).
Ce qui donne l’inclusion
N (A, a) ⊂ N (conv(A), a).
D’où l’égalité
N (A, a) = N (conv(A), a).
6) Soit x∗ ∈ N (A, a) et d ∈ T (A, a). Alors
∃ {dk } ⊂ Rn , dk −→ d,
: xk = a + λk dk ∈ A ∀ k ∈ N,
∃ {λk } ⊂ R∗+ , λk −→ 0,
Comme x∗ ∈ N (A, a), on peut écrire
hx∗ , xk − ai ≤ 0 ⇔ λk hx∗ , dk i ≤ 0 ∀k,
et donc
hx∗ , dk i ≤ 0 ∀k.
Par passage à la limite, on a
hx∗ , di ≤ 0.
D’où
x∗ ∈ T (A, a)◦ .
Donc
N (A, a) ⊂ T (A, a)◦ .
Ce qui termine la démonstration. ¤
46 CHAPITRE 3. CÔNES CONVEXES

Théorème 3.6.1 Si A est un sous ensemble convexe non vide de Rn et a ∈ A, le cône tangent
T (A, a) et le cône normal N (A, a) sont polaires l’un de l’autre. C’est-à-dire :

N (A, a)◦ = T (A, a), et T (A, a)◦ = N (A, a).

Preuve : On sait que

N (A, a) ⊂ T (A, a)◦ .
Aussi, comme A est convexe, on a

T (A, a) = R∗+ (A − a).

Donc si x∗ ∈ T (A, a)◦ , on a

hx∗ , di ≤ 0 ∀d ∈ T (A, a).
Donc
hx∗ , x − ai ≤ 0 ∀x ∈ A.
Alors x∗ ∈ N (A, a) : et donc
T (A, a)◦ ⊂ N (A, a).
On a alors
T (A, a)◦ = N (A, a).
D’autre part T (A, a) est un cône convexe fermé. Il est donc égal à son bipolaire. C’est-à-dire

T (A, a) = T (A, a)◦◦ .

Donc on a
N (A, a)◦ = T (A, a)◦◦ = T (A, a).
D’où le théorème. ¤
Plus généralement on montre que

Théorème 3.6.2 Si A est un sous ensemble non vide de Rn et a ∈ A, alors

T (A, a) = T (conv(A), a) ⇔ N (A, a)◦ = T (A, a).

Preuve : Supposons que

T (A, a) = T (conv(A), a),
et montrons que
N (A, a)◦ = T (A, a).
Pour cela nous allons montrer que

N (A, a) = T (A, a)◦ .

On sait que
N (A, a) ⊂ T (A, a)◦ .
Il reste donc à montrer l’inclusion
T (A, a)◦ ⊂ N (A, a).
Soit
x∗ ∈ T (A, a)◦ .
3.6. CÔNES NORMAUX 47

Alors
hx∗ , di ≤ 0 ∀ d ∈ T (A, a).
On sait que
T (A, a) = T (conv(A), a) = R∗+ (conv(A) − a).
Donc on a
hx∗ , x − ai ≤ 0 ∀ x ∈ conv(A).
On en déduit que
x∗ ∈ N (conv(A), a) = N (A, a).
Ce qui donne l’inclusion recherchée

T (A, a)◦ ⊂ N (A, a).

Comme par hypothèse

T (A, a) = T (conv(A), a),
et T (conv(A), a) est un cône convexe fermé, il est donc égal à son bipolaire, on obtient

N (A, a)◦ = T (A, a)◦◦ = T (A, a).

D’où le résultat.
Réciproquement supposons que

N (A, a)◦ = T (A, a),

et montrons qu’on a
T (A, a) = T (conv(A), a).
On a toujours l’inclusion
T (A, a) ⊂ T (conv(A), a).
Soit
d ∈ T (conv(A), a),
et
x∗ ∈ N (A, a).
∃ {xk } ⊂ conv(A), 1 k
: lim (x − a) = d.
∃ {λk } ⊂ R∗+ , k→+∞ λk

Comme
N (A, a) = N (conv(A), a),
on a alors
hx∗ , xk − ai ≤ 0 ∀ k.
Donc
hx∗ , di ≤ 0.
On en déduit que
d ∈ N (A, a)◦ = T (A, a).
Donc
T (conv(A), a) ⊂ T (A, a).
Ce qui termine la démonstration. ¤
48 CHAPITRE 3. CÔNES CONVEXES
Chapitre 4

Fonctions convexes

4.1 Fonctions convexes d’une variable réelle

Définition 4.1.1 Soient I un intervalle de R. Une application f : I 7→ R est convexe si
∀ (x, y) ∈ I 2 , f ((1 − λ)x + λy) ≤ (1 − λ)f (x) + λf (y) ∀λ ∈ [0, 1].
On dit que f est concave si −f est convexe.
L’application f est convexe si et seulement si, la courbe est en dessous de chacune de ses cordes
(une corde étant ici un segment).
Proposition 4.1.1 Soient I un intervalle de R, f : I 7→ R. Pour tout a ∈ I on note τa : I −{a} →
R définie par τa (x) = f (x)−f
x−a
(a)
appelée taux d’accroissement en a. La fonction f est convexe si et
seulement si pour tout a ∈ I, τa est une application croissante sur I − {a}.
Preuve :
Soit x < y dans I − {a}.
•x<a<y
Dans ce cas on peut écrire a = x + t(y − a) avec t = a−x
y−x
et donc de part la convexité de f on a
f (a) ≤ (1 − t)f (x) + tf (y) ⇔ (1 − t + t)f (a) ≤ (1 − t)f (x) + tf (y).
Soit (1 − t)(f (a) − f (x)) ≤ t(f (y) − f (a)). Donc en remplaçant t par sa valeur, on obtient :
y−a a−x
( )(f (a) − f (x)) ≤ ( )(f (y) − f (a)).
y−x y−x
C’est-à-dire
f (x) − f (a) f (y) − f (a)
≤ .
x−a y−a
• a < x < y.
Ici on peut écrire x = a + t(y − a) avec t = x−a
y−a
. Alors on a
f (x) ≤ (1 − t)f (a) + tf (y)

⇔ f (x) − f (a) ≤ t(f (y) − f (a))

⇔ f (x) − f (a) ≤ ( x−a

y−a
)(f (y) − f (a))

⇔ f (x)−f (a)
x−a
≤ f (y)−f (a)
y−a

49
50 CHAPITRE 4. FONCTIONS CONVEXES

• x < y < a.
On a y = x + t(a − x) avec t = y−x
a−x
. Alors la convexité de f donne

f (y) ≤ (1 − t)f (x) + tf (a)

⇔ f (y) − f (a) ≤ (1 − t)f (x) − (1 − t)f (a))

⇔ f (y) − f (a) ≤ (1 − t)(f (x) − f (a))

⇔ f (y) − f (a) ≤ ( a−x

a−y
)(f (x) − f (a))

⇔ f (y)−f (a)
a−y
≤ f (x)−f (a)
a−x
Ce qui s’écrit encore

f (x) − f (a) f (y) − f (a)

≤ .
x−a y−a
Réciproquement supposons que pour tout a ∈ I, τa est une application croissante sur I − {a}.
Soit x et y, x < y deux éléments de I et λ ∈]0, 1[. Posons z = x + λ(y − x). On a z < y
et λ = y−x z−x
. Comme l’application τx est croissante sur I − {x}, on doit avoir τx (z) ≤ τx (y),
c’est-à-dire :
f (z) − f (x) f (y) − f (x)
≤ .
z−x y−x
Soit
z−x
f (z) − f (x) ≤ (f (y) − f (x)).
y−x
Ce qui s’écrit encore f (z) − f (x) ≤ λ(f (y) − f (x)).
D’où la convexité de f . ¤

Proposition 4.1.2 Soient I un intervalle de R et f : I 7→ R convexe. Alors f est derivable à

droite et à gauche en tout point de int(I) et, pour tout (a, b, c) ∈ I 3 tel que a < b < c, on a
f (b) − f (a) f (c) − f (a)
≤ fg0 (b) ≤ fd0 (b) ≤ .
b−a c−a
Preuve : Soit a, b, c ∈ int(dom(f )) tels que a < b < c soit t el que b = (1 − t)a + tc on a alors
f (b) ≤ (1 − t)f (a) + tf (c). On en déduit
f (b) − f (a) f (c) − f (a) f (c) − f (b)
≤ ≤ .
b−a c−a c−b
Fixons b et c et faisons tendre a vers b. On a
f (c) − f (b)
f 0− (b) ≤ ∀ c > b.
c−b
Fixons a et b et faisons tendre c vers b. On a
f (b) − f (a)
≤ f+0 (b), ∀ a < b.
b−a
On en déduit :
f (b) − f (a) f (c) − f (b)
f+0 (a) ≤ ≤ f−0 (b) ≤ f+0 (b) ≤ ≤ f−0 (c).
b−a c−b
¤
4.2. FONCTIONS CONVEXES À PLUSIEURS VARIABLES 51

Corollaire 4.1.1 Si f est convexe sur I, alors f est continue sur int(I).

Proposition 4.1.3 Soient I un intervalle de R et f : I 7→ R derivable sur I. f est convexe si et

seulement si f 0 est croissante sur I.

Proposition 4.1.4 Soient I un intervalle borné de R et f : I 7→ R convexe. Alors f est minorée

sur I.

Proposition 4.1.5 Soient I un intervalle de R, f : I 7→ R convexe. On suppose que f est majorée

et atteint sa borne supérieure en un point de int(I). Montrer que f est constante.

Proposition 4.1.6 Soient I un intervalle de R (a, b) ∈ (int(I))2 , f : I 7→ R : montrer que si f

est convexe sur I, alors f est lipschitzienne sur [a, b].

Proposition 4.1.7 Soient I un intervalle ouvert de R et f : I 7→ R convexe et dérivable. Alors f

est de classe C 1 sur I.

4.2 Fonctions convexes à plusieurs variables

4.2.1 Définitions
Définition 4.2.1 Soit f : Rn →] − ∞, +∞].
On appelle :
- domaine effectif de f , l’ensemble

dom(f ) = {x ∈ Rn : f (x) < +∞} .

- épigraphe de f , l’ensemble

epi(f ) = {(x, λ) ∈ Rn × R : f (x) ≤ λ} .

- épigraphe strict de f , l’ensemble

f ) = {(x, λ) ∈ Rn × R : f (x) < λ} .

epi(f

- section de niveau λ de f , l’ensemble

Sλ (f ) = {x ∈ Rn : f (x) ≤ λ} .

- section stricte de niveau λ de f , l’ensemble

Seλ (f ) = {x ∈ Rn : f (x) < λ} .

Il est clair qu’un sous ensemble F de Rn × R est un épigraphe si et seulement si il est ”infini”
vers le haut, c’est-à-dire que si (x, λ) ∈ F , alors (x, λ0 ) ∈ F dès que λ0 ≥ λ. Ainsi

epi(f ) = F ⇐⇒ ∀ x ∈ Rn , f (x) = inf λ.

(x,λ)∈F

On définit
52 CHAPITRE 4. FONCTIONS CONVEXES

Définition 4.2.2 Une fonction f : Rn →] − ∞, +∞] est dite propre si dom(f ) est non vide.

Définition 4.2.3 Une fonction f : Rn → R ∪ {+∞} est convexe si

∀ x, y ∈ domf, f ((1 − λ)x + λy) ≤ (1 − λ)f (x) + λf (y) ∀ λ ∈ [0, 1].

Définition 4.2.4 Une fonction f : Rn → R ∪ {+∞} est strictement convexe, si

∀ x, y ∈ domf, x 6= y, f ((1 − λ)x + λy) < (1 − λ)f (x) + λf (y) ∀ λ ∈]0, 1[.

Définition 4.2.5 Une fonction f : Rn → R ∪ {+∞} est fortement convexe de module r > 0, si

∀ x, y ∈ domf, f ((1 − λ)x + λy) ≤ (1 − λ)f (x) + λf (y) − 2r λ(1 − λ)ky − xk2 ∀ λ ∈ [0, 1].

Définition 4.2.6 f : Rn → R ∪ {−∞} est concave si

∀ x, y ∈ domf, f ((1 − λ)x + λy) ≥ (1 − λ)f (x) + λf (y) ∀ λ ∈ [0, 1].

Définition 4.2.7 Une fonction f : Rn → R ∪ {−∞} est strictement concave, si

∀ x, y ∈ domf, x 6= y, f ((1 − λ)x + λy) > (1 − λ)f (x) + λf (y) ∀ λ ∈]0, 1[.

Définition 4.2.8 Une fonction f : Rn → R ∪ {−∞} est fortement concave de module r > 0, si

∀ x, y ∈ domf, f ((1 − λ)x + λy) ≥ (1 − λ)f (x) + λf (y) − 2r λ(1 − λ)ky − xk2 .∀ λ ∈ [0, 1].

Il est immédiat que

Proposition 4.2.1 Une fonction f : Rn → R ∪ {−∞} est respectivement concave, strictement

concave, fortement concave de module r > 0, si −f définie sur Rn et à valeurs dans R ∪ {+∞}
est respectivement convexe, strictement convexe, fortement convexe de module r > 0.

On montre facilement que :

Proposition 4.2.2 Soit C un convexe non vide de Rn et f : C → R. f est convexe sur C si et

seulement si, la fonction étendue on dit aussi prolongement canonique de f , définie sur Rn par
(
f (x) si x ∈ C
f˜(x) =
+∞ sinon

est convexe sur Rn .

Pour cela, pour étudier la convexité des fonctions on peut supposer sans perte de généralités,
que les fonctions sont définies sur Rn tout entier.
On a le lemme suivant :

f ) est convexe.
Lemme 4.2.1 Soit f : Rn → R ∪ {+∞}, epi(f ) est convexe si et seulement si epi(f

On a une caractérisation géométrique de la convexité d’une fonction.

4.2. FONCTIONS CONVEXES À PLUSIEURS VARIABLES 53

Proposition 4.2.3 Soit f : Rn → R ∪ {+∞}. Les propositions suivantes sont équivalentes :

i) f est convexe.
ii) L’épigraphe de f , (epi(f )), est convexe.
iii) L’épigraphe strict de f est convexe.
La démonstration est immédiate.
On a pour les fonctions concaves des résultats analogues.

Définition 4.2.9 On appelle hypographe de f , l’ensemble :

hyp(f ) = {(x, λ) ∈ Rn × R : f (x) ≥ λ} .

On appelle hypographe strict de f , l’ensemble :

g ) = {(x, λ) ∈ Rn × R : f (x) > λ} .

hyp(f

Proposition 4.2.4 Soit f : Rn → R ∪ {−∞}. Les propositions suivantes sont équivalentes :

i) f est concave.
ii) L’hypographe de f , (epi(f )), est convexe.
iii) L’hypographe strict de f est convexe.

On a les caractérisations suivantes :

Proposition 4.2.5 Soit f : Rn → R ∪ {+∞} propre. On a les équivalences suivantes.

i) f est convexe
P
ii) Pour toute combinaison linéaire convexe x = ki=1 λi xi , on a

X
k X
k
f( λi xi ) ≤ λi f (xi ).
i=1 i=1

Proposition 4.2.6 f : Rn → R ∪ {+∞} est convexe (respectivement strictement convexe) si

et seulement si pour toute droite D ⊂ Rn , la restriction de f à D est convexe (respectivement
strictement convexe). C’est-à-dire, pour tout a et d dans Rn , la fonction ϕa, d définie sur R par
ϕa, d (t) = f (a + td) est convexe (respectivement strictement convexe).

Preuve : Supposons f convexe. Soit a, d ∈ Rn , montrons que ϕa, d est convexe.

Soient t1 et t2 deux réels et λ ∈ [0, 1]. On a :

ϕa, d (λt1 + (1 − λ)t2 ) = f (a + (λt1 + (1 − λ)t2 )d)

= f (λa + (1 − λ)a + λt1 d + (1 − λ)t2 d)
= f (λ(a + t1 d) + (1 − λ)(a + t2 d))
≤ λf (a + t1 d) + (1 − λ)f (a + t2 d)
= λϕa, d (t1 ) + (1 − λ)ϕa, d (t2 )

d’où la convexité de ϕa, d .

Réciproquement supposons que pour tous a, d ∈ Rn , la fonction ϕ définie sur R par ϕ(t) =
f (a + td) est convexe. Montrons que f est convexe.
54 CHAPITRE 4. FONCTIONS CONVEXES

Soient x, y ∈ Rn et λ ∈ [0, 1]. On a

f (λx + (1 − λ)y) = f (y + λ(x − y)) = ϕy, x−y (λ)

= ϕy, x−y (λ × 1 + (1 − λ) × 0).

Comme ϕy, x−y est convexe, on a

ϕy, x−y (λ × 1 + (1 − λ) × 0) ≤ λϕy, x−y (1) + (1 − λ)ϕy, x−y (0)

= λf (x) + (1 − λ)f (y)

d’où la convexité de f .
Pour la stricte convexité, on procède de la même façon. ¤

Proposition 4.2.7 Si f : Rn → R ∪ {+∞} est convexe propre alors pour a ∈ domf et d ∈ Rn ,

l’application définie sur ]0, +∞[ par

f (a + td) − f (a)
ϕ(t) =
t
est croissante.

Preuve : Soient 0 < t1 ≤ t2 . On a alors 0 < t1

t2
≤ 1. Donc

t1 t1 t1 t1
f (a + t1 d) = f ((1 − )a + (a + t2 d)) ≤ (1 − )f (a) + f (a + t2 d).
t2 t2 t2 t2
Il s’ensuit alors que
f (a + t1 d) − f (a) f (a + t2 d) − f (a)
≤ .
t1 t2
Ce qui prouve la proposition. ¤
On a aussi la proposition suivante.

Proposition 4.2.8 Si f : Rn → R ∪ {+∞} est convexe alors les sections de niveau Sλ (f ), λ ∈ R

sont convexes.

Preuve : Soit λ ∈ R et x, y deux éléments de Sλ (f ) et α ∈ [0, 1].

La convexité de f et la définition de Sλ (f ) nous donne :

f ((1 − α)x + αy) ≤ (1 − α)f (x) + αf (y) ≤ (1 − α)λ + αλ = λ.

Donc (1 − α)x + αy ∈ Sλ (f ) qui est donc convexe. ¤

Remarque 4.2.1 La réciproque de cette proposition n’est pas vraie.

On a dans la proposition ci-dessous une caractérisation de la forte convexité.

Proposition 4.2.9 Une fonction f : Rn → R ∪ {+∞} est fortement convexe de module r si et

seulement si la fonction g définie sur Rn
par g(x) = f (x) − 12 rkx − ak2 (a ∈ Rn ) est convexe.
4.2. FONCTIONS CONVEXES À PLUSIEURS VARIABLES 55

Preuve : La fonction g est convexe si et seulement si

∀ x, y ∈ Rn , ∀ λ ∈]0, 1[,

g((1 − λ)x + λy) ≤ (1 − λ)g(x) + λg(y). (4.1)

Posons
µ = k(1 − λ)x + λy − ak2 − (1 − λ)kx − ak2 − λky − ak2 .
La condition (4.1) est alors équivalente à :
1
f ((1 − λ)x + λy) ≤ (1 − λ)f (x) + λf (y) + rµ.
2
Or

µ = k(1 − λ)x + λy − ak2 − (1 − λ)kx − ak2 − λky − ak2

= k(1 − λ)(x − a) + λ(y − a)k2 − (1 − λ)kx − ak2 − λky − ak2
= (1 − λ)2 kx − ak2 + λ2 ky − ak2 + 2λ(1 − λ)hx − a, y − ai
−(1 − λ)kx − ak2 − λky − ak2
¡ ¢
= −λ(1 − λ) kx − ak2 + ky − ak2 − 2hx − a, y − ai
= −λ(1 − λ)ky − xk2 .

La condition (4.1) est donc encore équivalente à :

1
f ((1 − λ)x + λy) ≤ (1 − λ)f (x) + λf (y) − rλ(1 − λ)ky − xk2 .
2
Ce qui signifie que la fonction f est fortement convexe. ¤

4.2.2 Opération sur les fonctions convexes

On montre facilement que

Proposition 4.2.10 Si f : Rn → R est convexe et ϕ : R → R est convexe et croissante alors la

fonction h = ϕ ◦ f est convexe.

On en déduit alors que

Proposition 4.2.11 Si f : Rn → R est concave et ϕ : R → R est concave et croissante alors la

fonction h = ϕ ◦ f est concave.

On peut aussi montrer que

Proposition 4.2.12 Si f : Rn → R est strictement convexe et ϕ : R → R est convexe et stricte-

ment croissante alors la fonction h = ϕ ◦ f est strictement convexe.

On tire les conséquences suivantes :

Corollaire 4.2.1 Si f : Rn → R est convexe alors la fonction ef est convexe.

56 CHAPITRE 4. FONCTIONS CONVEXES

Corollaire 4.2.2 Si f : Rn → R∗+ est concave alors la fonction 1

f
est convexe.

On obtient aussi des fonctions convexes en considérant les opérations suivantes :

Proposition 4.2.13 Toute combinaison linéaire finie et positive de fonctions convexes est convexe.
C’est-à-dire : Si pour tout i = 1, · · · , p, fi : Rn → R ∪ {+∞} est convexe, alors pour tout αi ≥ 0,
P
i = 1, · · · , p, la fonction f = pi=1 αi fi est convexe.

Proposition 4.2.14 L’enveloppe supérieure d’une famille de fonction convexes est convexe. Au-
trement dit, si {fi }i∈I est une famille quelconque de fonctions convexes définies sur Rn et à valeurs
dans R ∪ {+∞}, alors la fonction f définie par f (x) = supi∈I fi (x) est une fonction convexe.
Preuve : Soient x et y deux éléments de Rn et λ ∈ [0, 1]. Comme pour tout i ∈ I, fi est convexe,
on a
∀ i ∈ I, fi ((1 − λ)x + λy) ≤ (1 − λ)fi (x) + λfi (y)
≤ (1 − λ) sup fk (x) + λ sup fk (y).
k∈I k∈I

Donc
sup fi ((1 − λ)x + λy) ≤ (1 − λ) sup fk (x) + λ sup fk (y).
i∈I k∈I k∈I

Ce qui signifie que f est convexe. ¤

Remarque 4.2.2 On peut démontrer ce résultat en vérifiant que

epi(f ) = ∩i∈I epi(fi ).

Et comme les fi sont convexes, leurs épigraphes sont convexes et donc l’épigraphe de f aussi. Par
suite f est convexe.

On sait que l’image réciproque d’un convexe par une transformation affine est convexe. On
utilise cette propriété pour montrer le résultat ci-dessous.
Proposition 4.2.15 Soit A une transformation affine de Rn dans Rm et f : Rm → R ∪ {+∞}
une fonction convexe. Alors la fonction notée f A définie sur Rn par f A(x) = f (Ax) est convexe.
Preuve : Considérons la transformation affine
T : Rn × R → Rm × R
(x, λ) 7−→ (Ax, λ)
La fonction f étant convexe, epi(f ) est un convexe de Rn × R. Comme
T −1 (epi(f )) = {(x, λ) : T (x, λ) ∈ epi(f )}
= {(x, λ) : (Ax, λ) ∈ epi(f )}
= {(x, λ) : f (Ax) ≤ λ}
= epi(f A)
on en déduit que f A est convexe. ¤

On pouvait démontrer ce résultat directement en utilisant la définition d’une fonction convexe.

4.2. FONCTIONS CONVEXES À PLUSIEURS VARIABLES 57

Proposition 4.2.16 Si h : Rn × Rm → R ∪ {+∞} est conjointement convexe par rapport aux

deux variables, alors la fonction f définie sur Rn par

f (x) = infm h(x, y)

y∈R

est convexe.

Preuve : Il faut et il suffit de montrer que

∀ ε > 0, ∀ x1 , x2 ∈ Rn , ∀ λ ∈ [0, 1],

f ((1 − λ)x1 + λx2 ) ≤ (1 − λ)f (x1 ) + λf (x2 ) + ε.

Soit donc ε > 0 et considérons x1 , x2 dans Rn et λ ∈ [0, 1].
Il existe y 1 ∈ Rm tel que
f (x1 ) ≤ h(x1 , y 1 ) ≤ f (x1 ) + ε.
Il existe y 2 ∈ Rm tel que
f (x2 ) ≤ h(x2 , y 2 ) ≤ f (x2 ) + ε.
Comme (1 − λ)y 1 + λy 2 ∈ Rm , on a

f ((1 − λ)x1 + λx2 ) ≤ h((1 − λ)x1 + λx2 , (1 − λ)y 1 + λy 2 ).

La fonction h est convexe. Donc

h((1 − λ)x1 + λx2 , (1 − λ)y 1 + λy 2 ) = h((1 − λ)(x1 , y 1 ) + λ(x2 , y 2 ))

≤ (1 − λ)h(x1 , y 1 ) + λh(x2 , y 2 )
≤ (1 − λ)(f (x1 ) + ε) + λ(f (x2 ) + ε)
= (1 − λ)f (x1 ) + λf (x2 ) + ε.

On tire alors l’inégalité recherchée

f ((1 − λ)x1 + λx2 ) ≤ (1 − λ)f (x1 ) + λf (x2 ) + ε.

D’où la convexité de f . ¤

Proposition 4.2.17 Soit f : Rn → R ∪ {+∞} une fonction convexe et λ > 0. Alors la fonction
notée f λ et définie par (f λ)(x) = λf ( λx ) est convexe.

Preuve : On a en effet epi(f λ) = λepi(f ). D’où le résultat. ¤

Définition 4.2.10 Soient f, g : Rn → R ∪ {+∞} : on appelle inf-convolution de f et de g la

fonction notée f ¤g et définie par

(f ¤g)(x) = inf [f (x1 ) + g(x2 )] .

x1 +x2 =x

f ¤g) = epi(f
Proposition 4.2.18 On a epi(f f ) + epi(g)
f
58 CHAPITRE 4. FONCTIONS CONVEXES

Preuve : Dans cette démonstration on utilise l’équivalence suivante.

Si a, b et c sont des réels alors

a + b < c ⇔ ∃ α, β, α > a, β > b : α + β = c. (4.2)

On a aussi :
a + b ≤ c ⇔ ∃ α, β, α ≥ a, β ≥ b : α + β = c.
f ¤g). Cela signifie :
Soit (x, λ) ∈ epi(f

∃ x1 , x2 ∈ Rn , x1 + x2 = x : f (x1 ) + g(x2 ) < λ.

D’après (4.2), cela équivaut à :

∃ x1 x2 ∈ Rn , ∃ λ1 , λ2 ∈ R : x1 + x2 = x, λ1 + λ2 = λ, f (x1 ) < λ1 , g(x2 ) < λ2 .

C’est-à-dire
f ), (x2 , λ2 ) ∈ epi(g)
∃ (x1 , λ1 ) ∈ epi(f f : (x1 , λ1 ) + (x2 , λ2 ) = (x, λ).
D’où le résultat. ¤

Comme une fonction f est convexe si et seulement si son épigraphe strict est convexe, on a :

Proposition 4.2.19 Si les fonctions f et g sont convexes propres, alors f ¤g est convexe.

Remarque 4.2.3 On peut montrer la proposition ci-dessus en remarquant que la fonction

h : Rn × Rn → R ∪ {+∞}
(x, y) 7−→ h(x, y) = f (x − y) + g(y)

est convexe conjointement par rapport aux deux variables (x, y). Donc

f ¤g(x) = inf [f (x − y) + g(y)] = inf h(x, y)

y y

est convexe.

On montre que

Proposition 4.2.20 La loi de composition inf-convolution est commutative et associative.

4.2.3 Quelques fonctions convexes particulières

Définition 4.2.11 Soit S un sous ensemble non vide de Rn . On appelle fonction indicatrice de
S, la fonction notée δS ou δ(., S) définie sur Rn par
(
0 si x ∈ S
δS (x) = δ(x, S) =
+∞ sinon

On peut se demander pourquoi aller chercher la valeur infinie (et ne pas se contenter de 1
par exemple). Une des raisons est qu’une telle fonction ne serait pas convexe même lorsque S est
convexe. Il est immédiat de montrer que
4.2. FONCTIONS CONVEXES À PLUSIEURS VARIABLES 59

Proposition 4.2.21 S est convexe si et seulement si δS est convexe.

Définition 4.2.12 Soit C un sous ensemble non vide de Rn : on appelle fonction support de C
la fonction notée σC ou σ(., C) définie sur Rn par :

σC (x) = σ(x, C) = sup [hx, yi : y ∈ C] .

y

Proposition 4.2.22 La fonction support est une fonction convexe.

Définition 4.2.13 Soit C un convexe non vide de Rn . On appelle fonction jauge ou fonction de
Minkowski de C, la fonction notée γC ou γ(., C) définie sur Rn par :

γC (x) = γ(x, C) = inf [λ ≥ 0 : x ∈ λC] .

λ

Proposition 4.2.23 La fonction jauge est une fonction convexe.

Preuve : Soient x1 , x2 dans Rn et α ∈ [0, 1].

Soit ε > 0.
∃λ1 ≥ 0 : x1 ∈ λ1 C : γC (x1 ) ≤ λ1 ≤ γC (x1 ) + ε.
∃λ2 ≥ 0 : x2 ∈ λ2 C : γC (x2 ) ≤ λ2 ≤ γC (x2 ) + ε.
Comme C est convexe, on a

(1 − α)x1 + αx2 ∈ (1 − α)λ1 C + αλ2 C = ((1 − α)λ1 + αλ2 )C.

Comme (1 − α)λ1 + αλ2 ≥ 0, alors

γC ((1 − α)x1 + αx2 ) ≤ (1 − α)λ1 + αλ2

≤ (1 − α)(γC (x1 ) + ε) + α(γC (x2 ) + ε)
= (1 − α)γC (x1 ) + αγC (x2 ) + ε

Ce qui termine la démonstration ¤

Définition 4.2.14 Soit C un convexe non vide de Rn . On appelle fonction distance Euclidienne
de C, la fonction notée dC ou d(., C) définie sur Rn par :

dC (x) = d(x, C) = inf [kx − yk : y ∈ C] .

y

Proposition 4.2.24 La fonction distance est une fonction convexe.

Preuve : On peut montrer ce résultat de plusieurs façons.

1) On remarque que
dC (x) = inf [kx − yk + δC (y)] ,
y

c’est-à-dire l’inf-convolution de la norme et de la fonction indicatrice qui sont toutes les deux
convexes. Par suite la fonction distance est convexe.
2) On considère la fonction h définie par : h(x, y) = kx − yk.
Elle est convexe en (x, y) et comme dC (x) = inf y h(x, y), alors la fonction distance est convexe.
¤
60 CHAPITRE 4. FONCTIONS CONVEXES

4.2.4 Caractérisation des fonctions convexes différentiables

Dans les résultats qui suivent, nous donnons une caractérisation de la convexité dans le cas
différentiable.

Théorème 4.2.1 Soit f : Rn → R différentiable. On a les équivalences suivantes :

1) f est convexe sur Rn
2) f (y) ≥ f (x) + h∇f (x), y − xi, ∀ x, y ∈ Rn .
3) h∇f (y) − ∇f (x), y − xi ≥ 0, ∀ x, y ∈ Rn .

Preuve : 1)⇒ 2) Soient x, y dans Rn et λ ∈]0, 1[. Comme f est convexe, alors on a

f (x + λ(y − x)) − f (x) ≤ λ(f (y) − f (x)).

Ce qui donne
f (x + λ(y − x)) − f (x)
≤ f (y) − f (x).
λ
En passant à la limite, on obtient :

h∇f (x), y − xi ≤ f (y) − f (x).

D’où la proposition 2).

2)⇒ 1) On sait par hypothèse que

f (y) ≥ f (x) + h∇f (x), y − xi, ∀ (x, y) ∈ Rn × Rn .

Soient x, et y dans Rn et λ ∈ [0, 1]. En considérant respectivement les couples (x + λ(y − x), x) et
(x + λ(y − x), y), on a :

f (x) ≥ f (x + λ(y − x) − λh∇f (x + λ(y − x)), y − xi (4.3)

et
f (y) ≥ f (x + λ(y − x) + (1 − λ)h∇f (x + λ(y − x), y − xi (4.4)
On multiplie (4.3) par (1 − λ) et (4.4) par λ et on fait la somme des deux résultats. On obtient
alors
(1 − λ)f (x) + λf (y) ≥ f (x + λ(y − x).
Ce qui prouve que f est convexe.
2)⇒ 3) Soient x et y dans Rn . On a

f (y) ≥ f (x) + h∇f (x), y − xi (4.5)

et
f (x) ≥ f (y) + h∇f (y), x − yi (4.6)
En considérant la somme de (4.5) et de (4.6), on obtient

h∇f (y) − ∇f (x), y − xi ≥ 0.

Montrons à présent que la proposition 3) implique 2).

4.2. FONCTIONS CONVEXES À PLUSIEURS VARIABLES 61

3)⇒ 2) Soient x et y dans Rn . Comme f est différentiable alors :

∃ z ∈]x, y[ : f (y) − f (x) = h∇f (z), y − xi (4.7)

Comme z ∈]x, y[, il existe λ ∈]0, 1[ tel que z = x + λ(y − x).

D’après la proposition 3), on a :

h∇f (z) − ∇f (x), z − xi ≥ 0.

Or z − x = λ(y − x). Il vient donc

λh∇f (z) − ∇f (x), y − xi ≥ 0.

Soit
h∇f (z) − ∇f (x), y − xi ≥ 0
car λ ∈]0, 1[. C’est-à-dire
h∇f (z), y − xi ≥ h∇f (x), y − xi.
En utilisant (4.7), on obtient

f (y) − f (x) = h∇f (z), y − xi ≥ h∇f (x), y − xi.

D’où la proposition 2). Ce qui termine la démonstration ¤

On a des résultats similaires pour la stricte convexité.

Théorème 4.2.2 Soit f : Rn → R différentiable.

On a les équivalences suivantes :
1) f est strictement convexe sur Rn .
2) f (y) > f (x) + h∇f (x), y − xi, ∀ x, y ∈ Rn , x 6= y.
3) h∇f (y) − ∇f (x), y − xi > 0, ∀ x, y ∈ Rn , x 6= y.

Donnons à présent les résultats concernant la forte convexité.

Théorème 4.2.3 Soit f : Rn → R différentiable. On a les équivalences suivantes :

1) f est fortement convexe de module r > 0 sur Rn .
2) f (y) ≥ f (x) + h∇f (x), y − xi + 2r ky − xk2 , ∀ x, y ∈ Rn .
3) h∇f (y) − ∇f (x), y − xi ≥ rky − xk2 , ∀ x, y ∈ Rn .

Preuve : 1)⇒ 2) Soient x, y dans Rn et λ ∈]0, 1[. Comme f est fortement convexe de module r,
alors on a
r
f (x + λ(y − x)) − f (x) ≤ λ(f (y) − f (x)) − λ(1 − λ)ky − xk2 .
2
Ce qui donne
f (x + λ(y − x)) − f (x) r
≤ f (y) − f (x) − (1 − λ)ky − xk2 .
λ 2
En passant à la limite, on obtient :
r
h∇f (x), y − xi ≤ f (y) − f (x) − ky − xk2 .
2
D’où la proposition 2).
62 CHAPITRE 4. FONCTIONS CONVEXES

2)⇒ 1) On sait par hypothèse que

r
f (y) ≥ f (x) + h∇f (x), y − xi + ky − xk2 , ∀ (x, y) ∈ Rn × Rn .
2
Soient x, et y dans Rn et λ ∈ [0, 1]. En considérant respectivement les couples (x + λ(y − x), x) et
(x + λ(y − x), y), on a :
r
f (x) ≥ f (x + λ(y − x)) − λh∇f (x + λ(y − x)), y − xi + λ2 ky − xk2 (4.8)
2
et
r
f (y) ≥ f (x + λ(y − x) + (1 − λ)h∇f (x + λ(y − x)), y − xi + (1 − λ)2 ky − xk2 (4.9)
2
On multiplie (4.8) par (1 − λ) et (4.9) par λ et on fait la somme des deux résultats. On obtient
alors
r
(1 − λ)f (x) + λf (y) ≥ f (x + λ(y − x) + λ(1 − λ)ky − xk2 .
2
Ce qui prouve que f est fortement convexe de module r.
2)⇒ 3) Soit x et y dans Rn . On a
r
f (y) ≥ f (x) + h∇f (x), y − xi + ky − xk2 (4.10)
2
et
r
f (x) ≥ f (y) + h∇f (y), x − yi + ky − xk2 (4.11)
2
En considérant la somme de (4.10) et de (4.11), on obtient
h∇f (y) − ∇f (x), y − xi ≥ rky − xk2 .

3)⇒ 2) Soient x et y dans Rn . Considérons la fonction ϕ définie sur [0, 1] et à valeurs dans R
par :
t2
ϕ(t) = f (x + t(y − x)) − f (x) − th∇f (x), y − xi − rky − xk2 .
2
Par hypothèse, on a :
h∇f (x + t(y − x)) − ∇f (x), x + t(y − x) − xi ≥ rkx + t(y − x) − xk2 .
Soit
th∇f (x + t(y − x)) − ∇f (x), y − xi ≥ rt2 ky − xk2 .
Donc pour t > 0, on a :
h∇f (x + t(y − x)) − ∇f (x), y − xi ≥ rtky − xk2 . (4.12)
Comme f est différentiable, la fonction ϕ est derivable et pour t ∈]0, 1[, on a :
ϕ0 (t) = h∇f (x + t(y − x)) − ∇f (x), y − xi − rtky − xk2 .
En considérant (4.12), il vient que ϕ0 (t) est positif pour tout t ∈]0, 1]. Donc la fonction ϕ est
croissante sur cet intervalle. On a alors ϕ(1) ≥ ϕ(0) = 0. Soit
r
f (y) ≥ f (x) + h∇f (x), y − xi + ky − xk2 .
2
D’où le théorème. ¤

Dans le cas où la fonction est deux fois différentiable, on a aussi les caractérisations suivantes.
4.2. FONCTIONS CONVEXES À PLUSIEURS VARIABLES 63

Théorème 4.2.4 Soit f : Rn → R deux fois différentiable. On a les équivalences suivantes :

1) f est convexe sur Rn .
2) Pour tout x ∈ Rn , h∇2 f (x)h, hi ≥ 0 ∀ h ∈ Rn .
Preuve : Soit x ∈ Rn . On sait que pour tout h ∈ Rn et t ∈ R, suffisamment petit, on a
t2 2
f (x + th) = f (x) + th∇f (x), hi + h∇ f (x)h, hi + t2 khk2 ε(t).
2
Par hypothèse, la fonction f est convexe, donc on a pour tout h ∈ Rn et t ∈ R,
f (x + th) ≥ f (x) + th∇f (x), hi.
Donc
t2 2
f (x) + th∇f (x), hi + h∇ f (x)h, hi + t2 khk2 ε(t) ≥ f (x) + th∇f (x), hi.
2
Ce qui donne

h∇2 f (x)h, hi + khk2 ε(t) ≥ 0.

Comme la fonction ε tend vers 0 quand t tend vers 0, on obtient :
h∇2 f (x)h, hi ≥ 0.
On conclut que la matrice hessienne ∇2 f (x) est semi définie positive.
Réciproquement supposons que pour tout x ∈ Rn , ∇2 f (x) est semi définie positive.
Soit x ∈ Rn . On sait que pour tout y ∈ Rn , on a
1
f (y) = f (x) + h∇f (x), y − xi + h∇2 f (z)(y − x), y − xi,
2
avec z ∈]x, y[. Comme par hypothèse la matrice ∇ f (z) est semi définie positive, alors on a
2

h∇2 f (z)(y − x), y − xi ≥ 0.

Ce qui implique que
f (y) ≥ f (x) + h∇f (x), y − xi.
Par suite la fonction f est convexe. ¤

Le résultat qui suit concerne la stricte convexité.

Théorème 4.2.5 Soit f : Rn → R deux fois différentiable. Si

∀ x ∈ Rn , h∇2 f (x)h, hi > 0 ∀ h ∈ Rn , h 6= 0,
alors f est strictement convexe sur Rn .
Preuve : Soit x, y ∈ Rn avec x 6= y. On a
1
f (y) = f (x) + h∇f (x), y − xi + h∇2 f (z)(y − x), y − xi,
2
avec z ∈]x, y[. Comme par hypothèse la matrice ∇ f (z) est définie positive, alors on a
2

h∇2 f (z)(y − x), y − xi > 0

car x 6= y. On obtient alors
f (y) > f (x) + h∇f (x), y − xi.
Ce qui signifie que f est strictement convexe. ¤
64 CHAPITRE 4. FONCTIONS CONVEXES

Remarque 4.2.4 Il faut signaler que la réciproque de ce résultat n’est pas vraie. On peut considérer
la fonction ϕ définie sur R suivante : ϕ(t) = t4 . Cette fonction est strictement convexe mais sa
dérivée seconde en 0 est nulle.

On a ici une caractérisation de la forte convexité.

Théorème 4.2.6 Soit f : Rn → R deux fois différentiable. On a les équivalences suivantes :

1) f est fortement convexe de module r > 0 sur Rn .
2) Pour tout x ∈ Rn , h∇2 f (x)h, hi ≥ rkhk2 ∀ h ∈ Rn .

Preuve : Supposons f fortement convexe de module r. Alors comme f est différentiable, on a

pour tout x, y ∈ Rn , on a
r
f (y) ≥ f (x) + h∇f (x), y − xi + ky − xk2 , ∀ x, y ∈ Rn .
2
Soit x ∈ Rn ; pour tout h ∈ Rn et t suffisamment petit, on a

t2 2
f (x + th) = f (x) + th∇f (x), hi + h∇ f (x)h, hi + t2 khk2 ε(t).
2
avec ε continue et tendant vers 0 quand t tend vers 0. Donc

t2 2 r
f (x) + th∇f (x), hi + h∇ f (x)h, hi + t2 khk2 ε(t) ≥ f (x) + th∇f (x), hi + t2 khk2 .
2 2
Soit
1 2 r
h∇ f (x)h, hi + khk2 ε(t) ≥ khk2 .
2 2
En passant à la limite, on obtient h∇ f (x)h, hi ≥ rkhk .
2 2

Réciproquement, supposons que pour tout x ∈ Rn ,

h∇2 f (x)h, hi ≥ rkhk2 ∀ h ∈ Rn .

On a pour tout x, y ∈ Rn , la relation

1
f (y) = f (x) + h∇f (x), y − xi + h∇2 f (z)(y − x), y − xi,
2
avec z ∈]x, y[. Donc on a
1
f (y) ≥ f (x) + h∇f (x), y − xi + rky − xk2 .
2
Ce qui signifie que f est fortement convexe de module r sur Rn . ¤
Chapitre 5

Notions sur la convexité généralisée

5.1 Fonctions quasi convexes

On définit :

Définition 5.1.1 Soit f : Rn → R ∪ {+∞}.

1) f est quasi convexe si

∀ x, y ∈ Rn , ∀λ ∈ [0, 1], f ((1 − λ)x + λy) ≤ max{f (x), f (y)}.

2) f est strictement quasi convexe si

∀ x, y ∈ Rn , f (x) 6= f (y) ∀λ ∈]0, 1[, f ((1 − λ)x + λy) < max{f (x), f (y)}.

3) f est fortement quasi convexe si

∀ x, y ∈ Rn , x 6= y ∀λ ∈]0, 1[, f ((1 − λ)x + λy) < max{f (x), f (y)}.

On a les définitions similaires concernant la concavité.

Définition 5.1.2 Soit f : Rn → R ∪ {−∞}.

1) f est quasi concave si

∀ x, y ∈ Rn , ∀λ ∈ [0, 1], f ((1 − λ)x + λy) ≥ min{f (x), f (y)}.

2) f est strictement quasi concave si

∀ x, y ∈ Rn , f (x) 6= f (y) ∀λ ∈]0, 1[, f ((1 − λ)x + λy) > min{f (x), f (y)}.

3) f est fortement quasi concave si

∀ x, y ∈ Rn , x 6= y ∀λ ∈]0, 1[, f ((1 − λ)x + λy) > min{f (x), f (y)}.

65
66 CHAPITRE 5. NOTIONS SUR LA CONVEXITÉ GÉNÉRALISÉE

En d’autres termes, une fonction f est quasi concave, respectivement strictement quasi concave,
fortement quasi concave si, la fonction −f est quasi convexe, respectivement strictement quasi
convexe, fortement quasi convexe.
On a les exemples suivants.
p
Exemple 5.1.1 1) La fonction ϕ définie sur R par ϕ(t) = |t| est quasi convexe sur R.
2) Les fonctions monotones sur R sont quasi convexes et quasi concaves. D’ailleurs on peut
montrer qu’une fonction ϕ définie sur R est monotone si et seulement si les fonctions ϕ et −ϕ
sont quasi convexes.

On a la caractérisation suivante.

Proposition 5.1.1 Soit f : Rn → R ∪ {+∞}. On a les équivalences.

1) f est quasi convexe.
2) ∀ λ ∈ R , la section inférieure de niveau λ, Sλ (f ) est convexe.

La démonstration est immédiate.

De même on montre facilement que

Proposition 5.1.2 L’enveloppe supérieure d’une famille de fonctions quasi convexes est quasi
convexe.

Proposition 5.1.3 Si f : Rn → R ∪ {+∞} est quasi convexe et ϕ est croissante de R dans R

alors la fonction ϕ ◦ f est quasi convexe.

Proposition 5.1.4 Toute fonction fortement quasi convexe est strictement quasi convexe et quasi
convexe.

On n’a pas par contre la relation stricte quasi convexité implique quasi convexité comme on
pouvait s’attendre. Il faut en plus l’hypothèse de semi continuité inférieure comme le montre la
proposition suivante.

Proposition 5.1.5 Toute fonction strictement quasi convexe et s.c.i. est quasi convexe.

Preuve : Soit f : Rn → R ∪ {+∞} une fonction s.c.i. et strictement quasi convexe. Montrons
qu’elle est quasi convexe.
Soit x, y dans Rn et λ ∈ [0, 1].
1) Si f (x) 6= f (y), alors comme f est strictement quasi convexe on a

∀ λ ∈ [0, 1], f ((1 − λ)x + λy) < max{f (x), f (y)}.

2) Supposons à présent que f (x) = f (y).

Supposons qu’il existe α ∈]0, 1[ tel que

f ((1 − α)x + αy) > max{f (x), f (y)}.

Posons u = (1 − α)x + αy. On a u ∈ / Sf (x) (f ) qui est fermé car f est s.c.i.. Il existe alors
un voisinage de u inclus dans le complémentaire de Sf (x) (f ). Il existe alors β ∈]0, 1[ tel que :
5.2. FONCTIONS PSEUDOCONVEXES 67

f (u) > f ((1 − β)u + βx) > f (x).

Posons v = (1 − β)u + βx. On obtient alors :

f (u) > f (v) > f (x). (5.1)

En exprimant x en fonction de u et y, et en considérant l’expression de v, on obtient

1 − α + αβ αβ
v= u− y.
1−α 1−α
Ce qui donne
1−α αβ
u= v+ y.
1 − α + αβ 1 − α + αβ
Alors on a u ∈]v, y[. La stricte quasi convexité et la relation (5.1) donnent :

f (u) < max{f (y), f (v)} = max{f (x), f (v)} = f (v).

Ce qui est en contradiction avec la relation (5.1). Par suite la fonction est quasi convexe. ¤

Lorsque la fonction est différentiable, on a une autre caractérisation de la quasi convexité ;

Proposition 5.1.6 Soit f : Rn → R différentiable. Les propositions suivantes sont équivalentes.

1) La fonction f est quasi convexe.
2) ∀ x, y ∈ Rn , f (y) ≥ f (x) ⇒ h∇f (x), y − xi ≥ 0.

5.2 Fonctions pseudoconvexes

La notion de pseudoconvexité définie ci-dessous concerne les fonctions différentiables.

Définition 5.2.1 Soit f : Rn → R différentiable.

1) f est pseudoconvexe si

∀ x, y ∈ Rn avec h∇f (x), y − xi ≥ 0, on a f (y) ≥ f (x).

2) f est strictement pseudoconvexe si

∀ x, y ∈ Rn x 6= y, avec h∇f (x), y − xi ≥ 0, on a f (y) > f (x).

On montre que

Proposition 5.2.1 Soit f : Rn → R différentiable.

1) Si f est pseudoconvexe, alors f est strictement quasi convexe et quasi convexe.
2) Si f est strictement pseudoconvexe, alors f est fortement quasi convexe.
68 CHAPITRE 5. NOTIONS SUR LA CONVEXITÉ GÉNÉRALISÉE
Bibliographie

[1] Bazaraa, Mokhtar S. and Shetty, C. M., 1979. Nonlinear Programming Theory and Algo-
rithms, John Wiley and Sons.
[2] Bazaraa, Mokhtar S. and Shetty, C. M., 1976. Foundations of Optimization, Lecture Notes
in Economic and Mathematical Systems, No 122, Springer-Verlag New-York.
[3] Bergounioux Maı̈tine, 2001. Optimisation et Conrôle des systèmes linéaires, Dunod.
[4] Bertsekas, Dimiri P. 1995. Non Linear Programming, Athena Scientific.
[5] Bonnans, J. Fréderic and Shapiro, Alexander 2000. Perturbations Analysis of Opimization
Problems, Springer.
[6] Culioli, Jean-Christophe, 1994. Introduction à l’optimisation, Ellipses.
[7] Hiriart-Urruty, Jean-Baptiste, 1998. Optimisation et Analyse Convexe, Presse Universitaire
de France.
[8] Hiriart-Urruty, Jean-Baptiste and Lemaréchal, Claude, 1993. Convex Analysis and Minimi-
zation algorithms, Vol I et II Grundlehren der mathematichen Wissenschaften 305 and 306,
Springer-Verlag.
[9] Hiriart-Urruty, Jean-Baptiste, 1996. L’Optimisation, in collection ”Que sais-je ?”, Presse
Universitaire de France.
[10] Minoux, Michel, 1983. Programmation mathématique : Théorie et Algorithmes, Vol I, Dunod.
[11] Rockafellar, R. Tyrrel, 1970. Convex Analysis, Princeton University Press, Princeton N. J..
[12] Roberts, A. Wayne and Varberg, Dale E., 1973. Convex Functions, Academic Press.

69