Cours

Programmation Mathématique
Cycle Préparatoire

Abdelmalek Aboussoror

Année Universitaire 2021-2022

Université Cadi Ayyad

Ecole Nationale des Sciences Appliquées

Marrakech
2

Avant Propos

Pour des raisons pédagogiques, les démonstrations des résultats

(Théorèmes, Propositions,...) présentés dans ce polycopié ne sont données
qu’en Amphi. Certaines d’entre elles sont faites sous forme d’exercices en
travaux dirigés. Une bonne compréhension de ces démontrations facilite la
résolution des exercices posés en travaux dirigés. A noter aussi que la plupart
des exercices proposés en cours sont corrigés en travaux dirigés. Le cours sur
les méthodes d’optimisation sera traité séparément. Les prérequis demandés
pour ce cours sont essentiellement ceux de topologie, espaces normés, calcul
différentiel, algèbre linéaire et bilinéaire.

c Abdelmalek Aboussoror
Contents

1 Sous Espaces Affines 5

2 Ensembles Convexes 9
2.1 Définitions et Propriétés . . . . . . . . . . . . . . . . . . . . . 9
2.2 Propriétés Topologiques des Ensembles Convexes . . . . . . . 10
2.3 L’Enveloppe Convexe . . . . . . . . . . . . . . . . . . . . . . . 12
2.4 Séparation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.5 Point Extrémal et Face . . . . . . . . . . . . . . . . . . . . . . 17
2.6 Cône Normal . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3 Fonctions Convexes 21
3.1 Préliminaires et Définitions . . . . . . . . . . . . . . . . . . . 21
3.2 Propriétés Topologiques des Fonctions Convexes et Application 23
3.3 Propriétés des Fonctions Convexes Différentiables . . . . . . . 24
3.4 Sous Différentiel de Fonctions Convexes . . . . . . . . . . . . 27

4 Conditions d’Optimalité 31
4.1 L’ensemble des contraintes est un ouvert . . . . . . . . . . . . 31
4.2 Contraintes d’Egalités Linéaires . . . . . . . . . . . . . . . . . 32
4.3 Contraintes d’Egalités non Linéaires . . . . . . . . . . . . . . 34
4.4 Contraintes d’Inégalités . . . . . . . . . . . . . . . . . . . . . 34
4.5 Contraintes d’Egalités et d’Inégalités . . . . . . . . . . . . . . 35
4.6 Conditions d’Optimalité: cas non Différentiable . . . . . . . . 37

5 Dualité Lagrangienne 39
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5.2 Etude de la Dualité Lagrangienne . . . . . . . . . . . . . . . . 40

3
4 CONTENTS
Chapter 1

Sous Espaces Affines

Ce chapitre est consacré aux sous espaces affines de Rn . Dans ce chapitre

on s’intéresse aux définitions et propriétés qui nous seront utiles pour la
suite. Notamment, celles qui seront utilisées pour définir et établir quelques
propriétés topologiques des ensembles convexes en chapitre 2.

Définition 1.1 1) Soient x, x1 , ..., xp ∈ Rn , p ∈ N∗ . On dit que x est

Pp combinaison affine de x1 , ..., xp , s’il existe λ1 , ..., λp ∈ R, avec
une
i=1 λi = 1, tels que

p
X
x= λ i xi .
i=1

2) Soient u0 , ..., uq ∈ Rn , q ∈ N∗ . On dit que u0 , ..., uq , sont

P affinement
indépendents si pour tous λi ∈ R, i = 0, ..., q, vérifiant qi=0 λi = 0, et
q
X
λi ui = 0
i=0

alors

λi = 0 ∀ i ∈ 0, ..., q .
Dans le cas contraire, on dit qu’ils sont affinement dépendents.

Proposition 1.1 Soient x0 , ..., xk ∈ Rn , k ≥ 2. Alors, les propriétés suiv-

antes sont équivalentes :

1) x0 , ..., xk , sont affinement indépendents,

2) x1 − x0 , ..., xk − x0 , sont linéairement indépendents.

Preuve. Voir TD.

5
6 CHAPTER 1. SOUS ESPACES AFFINES

Remarque 1.1 La propriété 2) de la Proposition 1.1 peut être écrite sous

la forme plus générale
 suivante :
Pour tout j ∈ 0, ..., k , les vecteurs xi − xj , i = 0, ..., k, i 6= j, sont linéaire-
ment indépendents.

Définition 1.2 Soit A un sous ensemble non vide de Rn . L’ensemble A est

dit un sous espace affine de Rn , si pour tous x, y ∈ A et α ∈ R, on a

αx + (1 − α)y ∈ A

i.e., A contient la droite passant par x et y.

Exemple 1.1 i) Rn et tout singleton {a}, a ∈ Rn , sont des sous espaces

affines de Rn .
ii) Tout sous espace vectoriel de Rn est un sous espace affine.
n o
iii) Soit C = x ∈ Rn / Ax = b , où A ∈ Mm,n (R) et b ∈ Rm . Alors, on
vérifie facilement que C est un sous espace affine.

Exercice 1.1 Soit A ⊂ Rn , A 6= ∅. Montrer que si A est un sous espace

affine contenant 0, alors A est un sous espace vectoriel de Rn .

Définition 1.3 Soit A un sous ensemble non vide de Rn . L’enveloppe affine

engendrée par A, notée affA, est le plus petit sous espace affine contenant A,
i.e., l’intersection de tous les sous espaces affines contenant A
\
affA = C.
C sous espace affine
A⊂C

Remarque 1.2 Il est clair d’après la Définition 1.3 que si A et B sont des
sous ensembles de Rn avec A ⊂ B, on a affA ⊂ affB. En effet, on a

A ⊂ B ⊂ affB.

Puisque affA est le plus petit sous espace affine contenant A, il s’en suit que
affA ⊂ affB.

Exercice 1.2 Soit A un sous ensemble non vide de Rn . Montrer que

1) aff(affA) = affA,
2) si A est un sous espace affine, alors affA = A.

Proposition 1.2 Soient A un sous espace affine de Rn et a ∈ A. Alors,

A − a est un sous espace vectoriel de Rn .

Preuve. Voir TD.

 7

Proposition 1.3 Soit A un sous ensemble non vide de Rn . Alors, A est

un sous espace affine si et seulement si il existe un sous espace vectoriel V ,
tel que A soit une translation de V par un élément de A. De plus, le sous
espace vectoriel V est unique, appelé le sous espace vectoriel associé à A.

Preuve : Preuve donnée en Amphi.

Remarque 1.3 Géométriquement, le sous espace V est parallèle à A. De

plus, on remarque que le sous espace vectoriel V associé à A ne dépend pas
du choix de a dans A. C’est à dire, on peut choisir n’importe quel élément
dans A.

Définition 1.4 1) Nous appelons la dimension d’un sous espace affine de

n
R , la dimension du sous espace vectoriel qui lui est associé.

2) Soit A un sous ensemble non vide de Rn . On appelle dimension affine

de A, la dimension de son enveloppe affine affA.

Notation : dimA = dim(affA) = dimV, où V est le sous espace vectoriel

associé à affA.

Théorème 1.1 Soit A un sous ensemble non vide de Rn . Alors

n k
X k
X o
n
affA = x ∈ R / x = αi xi , xi ∈ A, αi ∈ R, i = 1, ..., k, αi = 1, k ∈ N∗
i=1 i=1

Preuve. Preuve donnée en Amphi.

Proposition 1.4 Soient A un sous ensemble non vide de Rn et x0 ∈ A.

Alors
affA = Vect(A − x0 ) + x0
où Vect(A − x0 ) désigne le sous espace vectoriel de Rn engendré par A − x0 .
Donc, Vect(A − x0 ) est le sous espace vectoriel associé à affA.

Preuve. Preuve donnée en Amphi.

Exercice 1.3 Soient C1 et C2 deux sous ensembles non vides de Rn tels que
C1 ⊂ C2 .

1) Montrer que affC1 ⊂ affC2 .

2) Supposons que dim(affC1 ) = dim(affC2 ). Montrer que affC1 = affC2 .

Proposition 1.5 Soient C1 et C2 deux sous ensembles de Rn et Rm , respec-

tivement. Alors
aff(C1 × C2 ) = affC1 × affC2 .
8 CHAPTER 1. SOUS ESPACES AFFINES

Preuve. Voir TD.

 
Exemple 1.2 Soit C = 0, 1 × {1}. Alors
 

affC = aff 0, 1 × aff({1}) = R × {1}.

Proposition 1.6 Soient X et Y deux sous ensembles non vides de Rn . Soit

(α, β) ∈ R2 . Alors aff(αX + βY ) = αaffX + βaffY .

Preuve. La preuve est laissée comme exercice (voir TD).

Chapter 2

Ensembles Convexes

2.1 Définitions et Propriétés

Définition 2.1 1) Soit C un sous ensemble de Rn . On dit que C est
convexe si
 
∀ x, y ∈ C, ∀ λ ∈ 0, 1 , λx + (1 − λ)y ∈ C
 
i.e., C contient le segment x, y .

2) Soient xi ∈ Rn , i = 1, ..., k, k ∈ N∗ . Toute

Psomme de la forme α1 x1 +
k
... + αk xk , avec αi ∈ 0, 1 , i = 1, ..., k, i=1 αi = 1, est appelée une
combinaison convexe de x1 , ..., xk .

Exemple 2.1 1) L’ensemble Rn , l’ensemble vide ∅, et tout singleton {a},

n
a ∈ R , sont des convexes.

2) Toute boule de Rn est convexe.

   
3) Soit A ⊂ R, avec A = 1, 2 ∪ 3, 4 . Alors, A est non convexe. Par
exemple la combinaison convexe 12 .2 + (1 − 12 ).3 = 52 6∈ A.

C
C

Fig 2.1 : C est convexe Fig 2.2 : C est non convexe

Nous avons les propriétés élémentaires suivantes :

Proposition 2.1 1) Soient C et D deux sous ensembles de Rn . On a

9
10 CHAPTER 2. ENSEMBLES CONVEXES
n o
i) si C est convexe, alors, pour tout réel α, αC = αx, x ∈ C est
convexe,
n o
ii) si C et D sont convexes, alors, C + D = x + y/ x ∈ C, y ∈ D
est convexe.

2) Soient C et D deux sous ensembles non vides de Rn et Rm , respective-

ment. Alors, C × D est un convexe de Rn × Rm si et seulement si C
et D sont convexes.

Preuve. Les preuves sont laissées sous forme d’exercice.

Remarque 2.1 D’après i) et ii) de la Proposition 2.1, on déduit que si C

et D sont deux convexes de Rn , alors αC + βD est un convexe pour tous
α, β ∈ R.

Exercice 2.1\Soit (Ci )i∈I une famille de sous ensembles convexes de Rn .

Montrer que Ci est convexe.
i∈I

Proposition 2.2 Soit C un sous ensemble non vides de Rn. Alors, C est
convexe si et seulement si pour tous xi ∈ C, et αi ∈ 0, 1 , i = 1, ..., k,
k ∈ N∗ , avec ki=1 αi = 1, on a α1 x1 + ... + αk xk ∈ C.
P

Preuve. Preuve donnée en Amphi.

2.2 Propriétés Topologiques des Ensembles Con-

vexes
Définition 2.2 Soit C un sous ensemble convexe de Rn . L’intérieur relatif
de C, noté par riC, est l’intérieur de C relative à affC muni de la topologie
induite par celle de Rn , i.e.,

x ∈ riC ⇐⇒ x ∈ affC et ∃ B(x, r) telle que B(x, r) ∩ affC ⊂ C,

où B(x, r) est la boule ouverte de Rn de centre x et de rayon r. On dit que

C est relativement ouvert si C = riC.

Exemple 2.2 Soit x ∈ Rn et C = x . Alors




1) affC = x (utiliser le Théorème 1.1),

2) dim(affC) = dim (affC − x) = dim 0 = 0,

3) riC = x ,

4) intC = ∅.
2.2. PROPRIÉTÉS TOPOLOGIQUES DES ENSEMBLES CONVEXES11

Pour deux convexes C1 et C2 de Rn , on peut avoir C1 ⊂ C2 , mais riC1 6⊂ riC2

comme on peut le voir dans l’exemple suivant.
  
Exemple 2.3 Soient C1 = 1 , et C2 = 1, 2 . Alors
  
riC1 = 1 et riC2 = 1, 2 .

On a donc C1 ⊂ C2 , mais riC1 6⊂ riC2 .

On a le résultat important suivant d’analyse convexe.

Théorème 2.1 Soit C un sous ensemble non vide de Rn . Alors, riC 6= ∅,

i.e., l’intérieur relatif d’un convexe non vide est toujours non vide.

Exercice 2.2 Soient C1 et C2 deux ensembles non vides convexes de Rn ,

avec C1 ⊂ C2 . Montrer que si affC1 = affC2 , alors riC1 ⊂ riC2 .

Définition 2.3 Soit C un sous ensemble non vide de Rn . La frontière rel-

ative de C, notée rbdC, est l’ensemble défini par rbdC = C \ riC.

Exercice 2.3 Soit C un sous ensemble convexe non vide de Rn d’intérieur

non vide.

1) Montrer que affC = Rn . Déduire la dimension affine de C.

2) Montrer que riC = intC.

Exercice 2.4 Soient α, β ∈ R+ et C un sous ensemble convexe de Rn .

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

Proposition 2.3 Soit C un sous ensemble non vide convexe de Rn . Soit

x ∈ C, et y ∈ riC. Alors
 n o
x, y = z ∈ Rn / z = αx + (1 − α)y, 0 ≤ α < 1 ⊂ riC.


Preuve. Voir TD.

Remarque 2.2 Soit C un sous ensemble convexe de Rn avec intC 6= ∅

 intC = riC. D’après la Proposition 2.3 pour x ∈ C et
(Exercice 2.3). Alors,
y ∈ intC, on a x, y ⊂ intC.

Proposition 2.4 Soit C un sous ensemble non vide convexe de Rn . Alors

1) riC = C,

2) riC = riC.
12 CHAPTER 2. ENSEMBLES CONVEXES

Preuve. 1) Preuve donnée en Amphi.

2) Voir TD.
On obtient alors le corollaire suivant.

Corollaire 2.1 Soit C un sous ensemble convexe de Rn . Supposons que

intC 6= ∅. Alors, on a

1) intC = C,

2) intC = intC.

Preuve. Résulte de la Proposition 2.4.

Proposition 2.5 Soit C un sous ensemble non vide convexe de Rn . Alors,

riC et riC sont convexes.

Preuve. Preuve donnée en Amphi.

Corollaire 2.2 Soit C un sous ensemble non vide convexe de Rn avec

intC 6= ∅. Alors, intC et intC sont convexes.

Preuve. Résulte de la Proposition 2.5.

Exercice 2.5 Soient C1 et C2 deux sous ensembles non vides de Rn , vérifi-

ant riC1 ∩ riC2 6= ∅. Montrer que

riC1 ∩ riC2 = C1 ∩ C2 .

Proposition 2.6 Soient C1 et C2 deux sous ensembles non vides convexes

de Rn , vérifiant riC1 ∩ riC2 6= ∅. Alors

ri (C1 ∩ C2 ) = riC1 ∩ riC2 .

Preuve. Preuve donnée en Amphi.

2.3 L’Enveloppe Convexe

Par analogie à l’enveloppe affine d’un ensemble définie dans le chapitre
précédent, on définit aussi l’enveloppe convexe d’un ensemble.

Définition 2.4 Soit C un sous ensemble non vide de Rn . L’enveloppe con-

vexe de C notée par conv C, ou coC, est le plus petit convexe contenant C,
i.e., l’intersection de tous les convexes contenant C
\
convC = F.
F convexe
C⊂F
2.4. SÉPARATION 13

co C
C

Fig 2.3 : C et son enveloppe convexe

Remarque 2.3 Si C est convexe, alors convC = C.

Théorème 2.2 Soit C un sous ensemble non vide de Rn . Alors

n k
X
convC = x ∈ Rn / x =
 
λi xi , λi ∈ 0, 1 , xi ∈ C,
i=1 o
Pk
i = 1, ..., k, i=1 λi = 1, k ∈ N∗ .

Preuve. Preuve identique à celle du Théorème 1.1 en remplaçant la combi-

naison affine par la combinaison convexe.
On a le résultat important suivant dû à Carathéodory.

Théorème 2.3 (C. Carathéodory) Soit C un sous ensemble non vide de Rn .

Alors, tout élément de convC peut être exprimé comme combinaison convexe
d’au plus n + 1 éléments de C.

Preuve. Preuve donnée en Amphi.

Exercice 2.6 Soit C un sous ensemble compact de Rn . Montrer que convC

est compact.

2.4 Séparation
Dans cette section, avant de donner des résultats sur la séparation de
deux convexes, nous commençons par donner des résultats préliminaires.

Proposition 2.7 Soient f : Rn → R une fonction, et C un sous ensemble

fermé non vide de Rn . Supposons que f est semicontinue inférieurement
(s.c.i.) sur C, et 0-coercive, i.e.,

lim f (x) = +∞.

kxk→+∞

Alors, le problème
(P) : Min f (x)
x∈C

admet au moins une solution.

14 CHAPTER 2. ENSEMBLES CONVEXES

Preuve. Preuve donnée en Amphi.

Le résultat suivant dont la démonstration utilise des éléments de topologie
sera utilisé ultérieurement.

Proposition 2.8 Soit f : Rn → R une fonction semicontinue supérieure-

ment (s.c.s.) sur Rn . Soit A un sous ensemble non vide de Rn . Alors

inf f (x) = inf f (x).

x∈A x∈Ā

Dans le cas où f est semicontinue inférieurement (s.c.i.) sur Rn on a le

résultat analogue suivant

sup f (x) = sup f (x).

x∈A x∈Ā

Définition 2.5 Soit f : Rn → R une fonction. On dit que f est strictement

convexe si pour tous x, y ∈ Rn , x 6= y, et tout α ∈]0, 1[, on a

f (αx + (1 − α)y) < αf (x) + (1 − α)f (y).

Exemple 2.4 La fonction f définie sur Rn par f (x) = kx−x0 k22 , où x0 ∈ Rn

donné, est strictement convexe (voir chapitre 3 sur les fonctions convexes).

Exercice 2.7 Montrer que la fonction considérée dans l’exemple 2.4 est 0-
coercive.

Exercice 2.8 Soient f : Rn → R, une fonction strictement convexe et C

un sous ensemble non vide convexe de Rn . Montrer que le problème de
minimisation suivant
(P) : min f (x)
x∈C

admet au plus une solution.

Définition 2.6 Soient C ⊂ Rn et x̄ ∈ Rn . Une solution du problème

1 2
Min x − x̄ 2
x∈C 2
est appelée une projection de x̄ sur C. C’est à dire le point de C le plus
proche de x̄.

Théorème 2.4 Soient C un sous ensemble convexe fermé de Rn , et x ∈ Rn .

Soit x̄ ∈ C. Alors, x̄ est une projection de x sur C si et seulement si

x − x̄, y − x̄ ≤ 0 ∀ y ∈ C.

Preuve. Preuve donnée en Amphi.

2.4. SÉPARATION 15

Théorème 2.5 Soit C un sous ensemble convexe fermé de Rn et x0 6∈ C.

Alors

1) La projection de x0 sur C existe et est unique. On la note par pC (x0 ),

2) Pour tout x ∈ C, on a x̄ − x0 2
≤ x − x0 2
, avec x̄ = pC (x0 ).

Preuve. Preuve donnée en Amphi.

Proposition 2.9 Soit C un sous ensemble convexe fermé de Rn . Alors

pC (x) − pC (y) 2
≤ x−y 2
∀ x, y ∈ Rn .

Preuve. Voir TD.

Remarquons que si 0 ∈ C, alors

kpC (x) 2
≤ x 2, ∀x ∈ Rn .

Définition 2.7 Soient a ∈ Rn \ {0}, et b ∈ R.

n o
1) L’ensemble H = x ∈ Rn / ha, xi = b est appelé un hyperplan affine.

2) Les ensembles
n o n o
H + = x ∈ Rn / ha, xi ≥ b et H − = x ∈ Rn / ha, xi ≤ b

sont appelés des demi espaces. Il s’en suit qu’un hyperplan donne deux
demi espaces.

3) Pour un sous ensemble A non vide de Rn , un hyperplan H est appelé

un hyperplan d’appui de A en x̄ ∈ rbdA, si x̄ ∈ H, et A ⊂ H + , ou
A ⊂ H −.

Définition 2.8 Soient A et B deux sous ensembles non vides de Rn , et

n o
H = x ∈ Rn / ha, xi = b

un hyperplan affine. On dit que

1) H sépare A et B, si A ⊂ H + et B ⊂ H − ,

2) H sépare A et B strictement, s’il existe  > 0, tel que A ⊂ H− et

B ⊂ H+ , où
16 CHAPTER 2. ENSEMBLES CONVEXES

n o n o
H+ = x ∈ Rn / ha, xi ≥ b+ et H− = x ∈ Rn / ha, xi ≤ b− .

ha, xi = b

ha, xi ≥ b +  ha, xi ≤ b − 

B
A

Fig 2.4 : séparation stricte des convexes A et B

Proposition 2.10 Soit C un sous ensemble convexe fermé de Rn . Soit

x ∈ Rn , avec x 6∈ C. Alors, il existe α ∈ R, et y ∈ Rn \ {0}, tels que

hy, zi ≤ α < hy, xi, ∀ z ∈ C.

Preuve. Voir TD.

Exercice 2.9 Soit C un sous ensemble convexe de Rn , avec intC 6= ∅. Mon-

trer que (intC)c = (C)c , où pour un sous ensemble A de Rn , Ac désigne le
complémentaire de A dans Rn .

Exercice 2.10 Soit C ⊂ Rn un convexe, avec intC 6= ∅. Soit x̄ ∈ Rn \ intC.

Montrer qu’il existe d ∈ Rn \ {0}, tel que

suphx, di ≤ hx̄, di.

x∈C

Proposition 2.11 Soit C un sous ensemble convexe de Rn . Soit x̄ ∈ rbdC.

Alors, il existe un hyperplan d’appui de C en x̄.

Preuve. Preuve donnée en Amphi.

Remarque 2.4 Si dimC = n, alors riC = intC. Dans ce cas, rbdC =

C \ riC = C \ intC = FrC.

Exercice 2.11 Soient C et D deux convexes de Rn vérifiant

ha, xi ≤ ha, yi, ∀ x ∈ C, ∀ y ∈ D

où a ∈ Rn \ {0}. Monter qu’il existe un hyperplan affine qui sépare C et D.

2.5. POINT EXTRÉMAL ET FACE 17

Théorème 2.6 Soient C et D deux convexes de Rn vérifiant C ∩ D = ∅.

Alors, C et D sont séparés au sens large, i.e., il existe a ∈ Rn \ {0} et α ∈ R,
tel que
ha, xi ≤ α ≤ ha, yi ∀ x ∈ C, ∀ y ∈ D.

Preuve. Preuve donnée en Amphi.

Exercice 2.12 Soient C et D deux convexes disjoints de Rn . Montrer que

C et D sont strictement séparés si et seulement si il existe a ∈ Rn \ {0}, tel
que
supha, xi < inf ha, yi.
x∈C y∈D

Théorème 2.7 (Hahn-Banach, Séparation stricte) Soient C et D deux sous

ensembles non vides de Rn , tels que

1) C est un convexe fermé,

2) D est un convexe compact,

3) C ∩ D = ∅.

Alors, il existe un hyperplan affine qui sépare strictement C et D.

Preuve. Preuve donnée en Amphi.

2.5 Point Extrémal et Face

Définition 2.9 Soit C un sous ensemble convexe non vide de Rn .

1) Soit F une partie convexe de C. On dit que F est une face de C si la

propriété suivante est satisfaite
   
∀ x, y ∈ C tels que x, y ∩ F 6= ∅ =⇒ x, y ⊂ F.

2) Soit a ∈ C. On dit que a est point extrémal de C si a ne peut être écrit
sous la forme a = αx + (1 − α)y, avec α ∈ 0, 1 , x, y ∈ C, x 6= y,
i.e., a ne peut être écrit comme combinaison convexe stricte de deux
éléments distincts de C.
L’ensemble des points extrémaux de C est noté extC.

Exercice 2.13 Soit C un sous ensemble convexe de Rn et H un hyperplan

d’appui de C en un point de rbdC. Montrer que H ∩ C est une face de C.
18 CHAPTER 2. ENSEMBLES CONVEXES

Exercice 2.14 Soit C un convexe de Rn non vide.

1) Soit F une partie convexe de C. On suppose que F est une face de C.
Montrer que extF ⊂ extC.
2) On suppose maintenant que C est un convexe fermé de Rn . Soit H un
hyperplan d’appui de C en un point de rbdC, avec H ne contenant pas C.
Montrer que
dim(H ∩ C) < dimC.

Remarque 2.5 Notons que dans l’exercice 2.14, on a

1) la condition F est une face est suffisante mais pas nécessaire (voir
figure 2.5),

2) si F n’est pas une face, on peut avoir un point extrémal F qui n’est pas
un point extrémal de C (voir figure 2.6).

y
x
C C
F = [x, y] F ⊂C
x
Fig 2.5 : F n’est pas une face, mais Fig 2.6 : F n’est pas une face et
extF = {x, y} ⊂ extC x un point extrémal de F
mais pas un point extrémal de C

Théorème 2.8 Soit C un sous ensemble convexe compact de Rn . Alors,

extC 6= ∅.

Preuve. Preuve donnée en Amphi.

On a le résultat important suivant d’analyse convexe.
Théorème 2.9 (H. Minkowski) Soit C ⊂ Rn un convexe compact. Alors,
C = co(extC).

2.6 Cône Normal

Cette notion de cône normal en un point d’un ensemble convexe sera
utilisée ultérieurement pour donner des conditions d’optimalité pour un prob-
lème d’optimisation.
Définition 2.10 Soit C un sous ensemble convexe de Rn . Soit x̄ ∈ C. Le
cône normal à C en x̄, noté NC (x̄) ou N (C, x̄) est l’ensemble défini par
n o
NC (x̄) = x∗ ∈ Rn / hx∗ , x − x̄i ≤ 0, ∀ x ∈ C .
2.6. CÔNE NORMAL 19

Remarque 2.6 1) Soient x∗ ∈ N (C, x̄) \ {0} et y ∈ C, avec y 6= x̄. Soit

θ l’angle entre x∗ et y − x̄. On a

hx∗ , y − x̄i
cos θ = ≤ 0.
kx∗ k2 ky − x̄k2

Alors, θ est obtus (voir figure 2.7 ci-dessous).

2) NC (x̄) est un cône convexe fermé contenant zéro.

3) Supposons que C est un sous ensemble convexe fermé de Rn . Soit

x ∈ Rn , x 6∈ C et posons x̄ = pc (x) (une telle projection existe et est
unique puisque C est un convexe fermé). On a

x̄ = pC (x) ⇐⇒ hx − x̄, y − x̄, i ≤ 0 ∀y ∈ C

⇐⇒ x − x̄ ∈ NC (x̄).

NC (x̄)

x̄

x̃ NC (x̃)
C

Fig 2.7: Cônes normaux en différents points de C

Proposition 2.12 Soient C et D deux sous ensembles convexes non vides

de Rp et Rq respectivement. Soit (x̄, ȳ) ∈ C × D. Alors

NC×D (x̄, ȳ) = NC (x̄) × ND (ȳ).

Preuve. Preuve laissée comme exercice.

Nous avons le résultat suivant pour les points intérieurs de C.

Proposition 2.13 Soit C un sous ensemble convexe de Rn d’intérieur non

vide. Soit x̄ ∈ intC. Alors

N (C, x̄) = 0 .

Preuve. Preuve donnée en Amphi.

Proposition 2.14 Soit C un sous ensemble non vide convexe de Rn

d’intérieur non vide. Soit x ∈ FrC. Alors, il existe a∗ ∈ N (C, x), avec
a∗ 6= 0.

Preuve. Voir TD.

20 CHAPTER 2. ENSEMBLES CONVEXES
Chapter 3

Fonctions Convexes

3.1 Préliminaires et Définitions

Dans toute la suite k.k désigne la norme euclidienne.
Soit X un sous ensemble non vide de Rn , et f : X → R, une fonction. On
définit les ensembles suivants :
n o
1) domf = x ∈ X/ f (x) < +∞ ,
n o
2) epif = (x, t) ∈ X × R/ f (x) ≤ t ,

appelés respectivement, le domaine effectif et l’épigraphe de f .

Définition 3.1 Soit X un sous ensemble non vide de Rn , et f : X → R,

une fonction. On dit que la fonction f est propre si

f (x) > −∞, ∀ x ∈ X et ∃ x̄ ∈ X tel que f (x̄) < +∞.

Définition 3.2 Soit f : Rn −→ R, une fonction.

  La fonction f est dite
convexe si pour tous x, y ∈ domf et tout α ∈ 0, 1 , on a

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

Elle est dite strictement convexe si l’inégalité ci-dessus est stricte pour tous
x, y ∈ domf , x 6= y, et tout α ∈ ]0, 1[. La fonction f est dite concave
(respectivement strictement concave), si −f est convexe (respectivement si
−f is strictement convexe).

Proposition 3.1 Soit f : Rn −→ R, une fonction. Alors, f est convexe si

et seulement si epif est convexe dans Rn+1 .

Preuve. Preuve donnée en Amphi.

21
22 CHAPTER 3. FONCTIONS CONVEXES

Exercice 3.1 Montrer que si f est convexe sur Rn , alors domf est un
convexe de Rn .

Proposition 3.2 (Inégalité de Jensen) Soit f : Rn → R, une fonction.

Alors, f est convexe si et seulement si pour tout p ∈ N∗ , pour tout xi ∈
p
X
 
domf , et tout αi ∈ 0, 1 , i = 1, ..., p, avec αi = 1, on a
i=1

p p
!
X X
f αi xi ≤ αi f (xi ).
i=1 i=1

Preuve. Preuve donnée en Amphi.

Comme application de l’analyse convexe en optimisation, on a les résultats

suivants sur un problème de maximisation d’une fonction convexe.

Proposition 3.3 Soient f : Rn → R, une fonction convexe et C un sous

ensemble non vide de Rn . Alors

sup f (x) = sup f (x).

x∈C x∈conv C

Preuve. Preuve donnée en Amphi.

Théorème 3.1 Soient f : Rn → R, une fonction convexe et C un sous

ensemble convexe compact de Rn . Alors

sup f (x) = sup f (x).

x∈C x∈extC

Preuve. Preuve donnée en Amphi.

Pour un exemple voir exemple 3.1.

Exercice 3.2 1) Soit (fi )i∈I une famille de fonctions convexes, où fi :

n
R → R. Montrer que la fonction sup fi est convexe, où sup fi est la
i∈I i∈I
fonction définie sur Rn par (sup fi )(x) = sup fi (x).
i∈I i∈I

2) Soit (gi )i∈I une famille de fonctions concaves, où gi : Rn → R. Montrer

que la fonction inf i∈I gi est concave, où inf gi est la fonction définie de
i∈I
la même manière que dans 1).
3.2. PROPRIÉTÉS TOPOLOGIQUES DES FONCTIONS CONVEXES ET APPLICATION23

3.2 Propriétés Topologiques des Fonctions Con-

vexes et Application
Dans cette section nous donnons quelques propriétés topologiques fondamen-
tales des fonctions convexes, ainsi qu’une application en optimisation.

Théorème 3.2 Soit f : Rn → R ∪ {+∞}, une fonction convexe et propre.

Alors, la fonction f est continue sur ri(domf ).

Remarque 3.1 1) Si int(domf ) 6= ∅, alors int(domf ) = ri(domf ) et

donc f est sur int(domf ).
2) Soit g : Rn → R une fonction convexe. On a domg = Rn . Donc
ri(domg) = int(domg) = Rn . Par suite, g est continue sur Rn .

Théorème 3.3 Soient f : Rn → R ∪ {+∞}, une fonction convexe propre et

C un sous ensemble convexe compact de Rn , avec C ⊂ ri(domf ). Soit M
l’ensemble des solutions du problème
Max f (x).
x∈C

Alors
M ∩ extC 6= ∅.
C’est à dire le supremum de f sur C est atteint en un point extrémal de C.

Preuve. Preuve donnée en Amphi.

Exemple 3.1 Soit f : R2 −→ R, la fonction définie par
f (x1 , x2 ) = x21 + 3x1 − 2x2
et soit
C = [−1, 1] × [−1, 1] ⊂ R2 .
Considérons le problème de maximisation suivant
(P) : Max (x21 + 3x1 − 2x2 ).
(x1 ,x2 )∈[−1,1]×[−1,1]

Pour tout (x1 , x2 ) ∈ R2 , on a

   
2x1 + 3 2 0
∇f (x1 , x2 ) = , ∇2 f (x1 , x2 ) = = M,
−2 0 0
et pour λ ∈ R,
det(M − λI2 ) = −λ(2 − λ),
où I2 est la matrice unité d’ordre 2. Les valeurs propres de ∇2 f (x1 , x2 ) sont
0 et 2. Donc ∇2 f (x1 , x2 ) est semi-définie positive pour tout (x1 , x2 ) ∈ R2
(voir Théorème 3.6 plus loin). Alors f est convexe sur R2 (voir Proposition
3.6).
24 CHAPTER 3. FONCTIONS CONVEXES

x2

(−1, 1) 1 (1, 1)

C
-1 0 1 x1

(−1, −1) -1 (1, −1)

Figure 1: Représentation des points extrémaux de C

Les points extrémaux de C sont (−1, 1), (1, 1), (1, −1) et (−1, −1). On a
C est un convexe compact et f une fonction convexe. Alors, d’après le
Théorème 3.3, il existe un point extrémal de C où le maximum de (P) est
atteint. Calculons alors les valeurs de f en les points extrémaux. On a


 f (1, −1) = 6,
f (−1, 1) = −4,


 f (1, 1) = 2,
f (−1, −1) = 0.


Donc max f (x1 , x2 ) = max f (x1 , x2 ) = 6 (Théorème 3.1), et

(x1 ,x2 )∈C (x1 ,x2 )∈extC
(1, −1) est une solution de (P) (Théorème 3.3).

3.3 Propriétés des Fonctions Convexes Différen-

tiables
Rappelons tout d’abord des définitions et résultats de calcul différentiel que
nous aurons besoin dans la suite.

Définition 3.3 Soient U un ouvert non vide de Rn et f : U −→ R, une

fonction. Soit x̄ ∈ U .
1) La fonction f est dite différentiable en x̄ s’il existe un vecteur noté ∇f (x̄),
appelé gradient de f en x̄, et une fonction βx̄ (.) : Rn −→ R, tels que pour
tout x ∈ U , on a

f (x) = f (x̄) + h∇f (x̄), x − x̄i + kx − x̄kβx̄ (x − x̄),

avec limx→x̄ βx̄ (x − x̄) = 0.

3.3. PROPRIÉTÉS DES FONCTIONS CONVEXES DIFFÉRENTIABLES25

2) La fonction f est dite deux fois différentiable en x̄ ∈ U s’il existe une

matrice notée ∇2 f (x̄) ∈ Mn (R), appelée la matrice hessienne de f en x̄, et
une fonction βx̄ (.) : Rn −→ R, telles que pour tout x ∈ U , on a
1
f (x) = f (x̄) + h∇f (x̄), x − x̄i + h∇2 f (x̄)(x − x̄), x − x̄i + kx − x̄k2 βx̄ (x − x̄)
2
avec limx→x̄ βx̄ (x − x̄) = 0.

Théorème 3.4 (la valeur moyenne) Soit U un ouvert convexe de Rn , et

f : U −→ R,  fonction différentiable sur U . Alors, pour tous x, y ∈ U , il
 une
existe α ∈ 0, 1 , tel que

f (x) − f (y) = h∇f (αx + (1 − α)y), x − yi.

Théorème 3.5 (Théorème de Taylor) Soit U un ouvert convexe de Rn , et

f : U −→ R, une fonction  deux fois différentiable sur U . Alors, pour tous
x, y ∈ U , il existe α ∈ 0, 1 , tel que

1
f (y) − f (x) = h∇f (x), y − xi + h∇2 f (αy + (1 − α)x)(y − x), y − xi.
2
Proposition 3.4 Soient f : Rn → R, une fonction, et C un ouvert con-
vexe de Rn . Supposons que f est différentiable sur C. Alors, les propriétés
suivantes sont équivalentes

1) f est convexe sur C,

2) f (x) ≥ f (y) + h∇f (y), x − yi, ∀ x, y ∈ C,

3) h∇f (x) − ∇f (y), x − yi ≥ 0, ∀ x, y ∈ C.

Preuve. Preuve donnée en Amphi.

Proposition 3.5 Soient f : Rn → R, une fonction et C un ouvert convexe

de Rn . Supposons que f est différentiable sur C. Alors, la fonction f est
strictement convexe sur C si et seulement si

f (y) > f (x) + h∇f (x), y − xi, ∀ x, y ∈ C, x 6= y.

Preuve. Preuve donnée en Amphi.

Nous rappelons les résultats importants suivants d’algèbre que nous utilis-
erons dans la suite pour reconnaitre la convexité d’une fonction.

Théorème 3.6 Soit A ∈ Mn (R) une matrice symétrique. Alors

1) A est semi-définie positive (resp. définie positive) si et seulement si ses

valeurs propres sont positives ou nulles (resp. strictement positives),
26 CHAPTER 3. FONCTIONS CONVEXES

2) A est semi-définie négative (resp. définie négative) si et seulement si

ses valeurs propres sont négatives ou nulles (resp. strictement néga-
tives).

Proposition 3.6 Soient f : Rn → R, une fonction deux fois différentiable

sur un ouvert convexe C de Rn . Alors, les assertions suivantes sont équiva-
lentes

1) la fonction f est convexe sur C,

2) pour tout x ∈ C, la matrice hessienne ∇2 f (x) est semi-définie positive

sur Rn , i.e.,
h∇2 f (x)y, yi ≥ 0, ∀ y ∈ Rn .

Preuve. Voir TD.

Remarque 3.2 En remarquant qu’une fonction g est concave si et seule-

ment si −g est convexe, on déduit le résultat suivant analogue à celui de la
Proposition 3.6 :
- La fonction f est concave sur C si et seulement si pour tout x ∈ C la
matrice hessienne ∇2 f (x) est semi-définie négative sur Rn , i.e.,

h∇2 f (x)y, yi ≤ 0, ∀ y ∈ Rn .

Proposition 3.7 Soit f : Rn → R, une fonction deux fois différentiable sur

un ouvert convexe C de Rn . Supposons que pour tout x ∈ C, la matrice
hessienne ∇2 f (x) est définie positive sur Rn , i.e.,

h∇2 f (x)y, yi > 0, ∀ y ∈ Rn .

Alors, f est strictement convexe sur C.

Preuve. La preuve est simple et laissée comme exercice (Indication : utiliser

le Théorème 3.5).

Exemple 3.2 1) Soit f : Rn → R, la fonction définie par f (x) = kxk2 =

x21 + x22 + ... + x2n , avec x = (x1 , ..., xn ). Soit x ∈ Rn . On a ∇2 f (x) = 2In , où
In est la matrice unité d’ordre n. La seule valeur propre de ∇2 f (x) est alors
2 qui est strictement positive. Par suite f est strictement convexe sur Rn .
2) Soit f : R2 → R, la fonction définie par f (x1 , x2 ) = x21 + x1 − 4x2 . Soit
x = (x1 , x2 ) ∈ R2 . On a
   
2x1 + 1 2 2 0
∇f (x1 , x2 ) = , ∇ f (x1 , x2 ) = ,
−4 0 0

dont les valeurs propres sont 0 et 2. Par suite f est convexe sur R2 .
3.4. SOUS DIFFÉRENTIEL DE FONCTIONS CONVEXES 27

3.4 Sous Différentiel de Fonctions Convexes

Dans cette section, nous allons voir une notion plus faible que la différen-
tiabilité appelée sous différentiabilité qui sera utilisée pour étudier des prob-
lèmes d’optimisation. Plus précisément, nous l’utiliserons pour exprimer des
conditions d’optimalité pour un problème d’optimisation dans le cas non
différentiable.
Définition 3.4 Soit f : Rn → R, une fonction. On définie la fonction
f ∗ : Rn → R, par n o
f ∗ (x∗ ) = sup hx∗ , xi − f (x)
x∈Rn

appelée la conjuguée de Legendre-Fenchel de f .

Remarque 3.3 D’après la définition de f ∗ , on a toujours

f ∗ (x∗ ) + f (x) ≥ hx∗ , xi, ∀ x∗ ∈ Rn , ∀ x ∈ Rn ,

appelée inégalité de Fenchel.

Définition 3.5 Soit f : Rn → R ∪ {+∞}, une fonction convexe et propre.

Soit x̄ ∈ domf . Un vecteur x∗ ∈ Rn est dit un sous gradient de f en x̄ si

f (x) ≥ f (x̄) + hx∗ , x − x̄i, ∀ x ∈ Rn .

L’ensemble des sous gradients de f en x̄ est appelé le sous differential de f

en x̄, et est noté ∂f (x̄), i.e.,
n o
∂f (x̄) = x∗ ∈ Rn / f (x) ≥ f (x̄) + hx∗ , x − x̄i, ∀ x ∈ Rn .

La fonction f est dite sous différentiable en x̄ si ∂f (x̄) 6= ∅.

Remarque 3.4 Si x 6∈ domf , alors f (x) = +∞. Il en résulte que ∂f (x) =

∅. En effet, supposons le contraire, i.e., ∂f (x) 6= ∅. Soit alors x∗ ∈ ∂f (x).
On a

x∗ ∈ ∂f (x) =⇒ f (y) ≥ f (x) + hx∗ , y − xi, ∀ y ∈ Rn

= +∞ + hx∗ , y − xi, ∀ y ∈ Rn
= +∞, ∀ y ∈ Rn .

Donc f (y) = +∞, pour tout y ∈ Rn . Ceci contredit le fait que f est non
identique à +∞ puisqu’elle est propre (∃x̄ ∈ Rn , tel que f (x̄) < +∞).

Exercice 3.3 Soit f : Rn → R ∪ {+∞}, une fonction convexe et propre.

Soit x∗ ∈ Rn . Montrer que pour tout x ∈ domf , on a

x∗ ∈ ∂f (x) ⇐⇒ f ∗ (x∗ ) + f (x) = hx∗ , xi.

28 CHAPTER 3. FONCTIONS CONVEXES

Théorème 3.7 Soit f : Rn → R ∪ {+∞}, une fonction convexe et propre.

Alors
1) Pour tout x ∈ ri(domf ), on a ∂f (x) 6= ∅.
2) Si int(domf ) 6= ∅, alors pour tout x ∈ int(domf ), ∂f (x) 6= ∅, et ∂f (x)
est un convexe compact.

Exercice 3.4 Montrer que ∂f (x) est un convexe fermé pour tout x ∈ domf .

Proposition 3.8 Soit f : Rn → R, une fonction convexe. On suppose que

f est différentiable sur Rn . Alors, pour tout x ∈ Rn , on a ∂f (x) = {∇f (x)}.

Preuve. Voir TD.

On a l’application suivante du sous différentiel pour exprimer des conditions
d’optimalité pour un problème de minimisation dont la fonction objectif est
convexe, que nous donnons dans la remarque suivante.

Remarque 3.5 Soit f : Rn → R, une fonction convexe. On a domf =

{x ∈ Rn : f (x) < +∞} = Rn . Par suite d’après le Théorème 3.7, on a
pour tout x ∈ Rn , ∂f (x) 6= ∅. Considérons le problème de minimisation sans
contrainte suivant
(P) : minn f (x).
x∈R

Soit x̄ ∈ Rn . Alors

x̄ solution de (P) ⇐⇒ f (y) ≥ f (x̄), ∀y ∈ Rn

⇐⇒ f (y) ≥ f (x̄) + h0, y − x̄i, ∀y ∈ Rn
⇐⇒ 0 ∈ ∂f (x̄).

Si de plus f est différentiable sur Rn , alors ∂f (x̄) = {∇f (x̄)}. Dans ce cas,
on a alors

x̄ solution de (P) ⇐⇒ 0 ∈ ∂f (x̄) = {∇f (x̄)}

⇐⇒ ∇f (x̄) = 0.

Exercice 3.5 Soit X un sous ensemble non vide de Rn et iX sa fonction

indicatrice, i.e., la fonction définie sur Rn par

0, si x ∈ X,
iX (x) =
+∞, si x 6∈ X.

Montrer que X est convexe si et seulement si iX est convexe sur Rn .

Proposition 3.9 Soient X un sous ensemble non vide convexe de Rn et

x ∈ X. Montrer que
∂iX (x) = NX (x).
3.4. SOUS DIFFÉRENTIEL DE FONCTIONS CONVEXES 29

Preuve. Voir TD.

Théorème 3.8 Soient f, g : Rn → R ∪ {+∞}, deux fonctions convexes et

propres. On suppose qu’il existe x0 ∈ domg tel que f est continue en x0 .
Alors, on a

∂(f + g)(x) = ∂f (x) + ∂g(x), ∀x ∈ domf ∩ domg.

Théorème 3.9 Soit f : Rn → R ∪ {+∞}, une fonction convexe et propre,

avec int(domf ) 6= ∅ . Alors, pour tout x ∈ int(domf ), on a
h 0 0
i
∂f (x) = fg (x), fd (x) ,

0 0
où fg (x) et fd (x) sont respectivement les dérivées à gauche et à droite de f
en x.

Exemple 3.3 Soit f : R → R, la fonction définie par f (x) = |x|. Alors,

0
f est une fonction convexe qui est non dérivable en 0. On a fg (0) = −1 et
0
fd (0) = 1. Par suite ∂f (0) = [−1, 1].
30 CHAPTER 3. FONCTIONS CONVEXES
Chapter 4

Conditions d’Optimalité

Dans ce chapitre, nous donnons des conditions nécessaires et suffisantes

d’optimalité pour des problèmes d’optimisation avec et sans contraintes. A
titre de rappel, les démonstrations sont données en Amphi. D’autres exem-
ples illustratifs sont aussi donnés en Amphi.

4.1 L’ensemble des contraintes est un ouvert

On considère le problème de minimisation suivant
(P) : min f (x),
x∈C
où f :Rn → R, est une fonction et C un ouvert de Rn . Si f est différentiable
en x ∈ C, et ∇f (x) = 0, on dit que x est un point stationnaire de f .
Conditions Nécessaire d’Optimalité
Théorème 4.1 (Conditions nécessaire d’optimalité de premier ordre) Soit
x̄ ∈ C une solution locale (i.e. minimum local) de (P). Supposons que f est
différentiable en x̄. Alors, ∇f (x̄) = 0.
Exemple 4.1 Considérons le problème
(P) : min f (x1 , x2 )
x∈C

x21
où f (x1 , x2 ) = − 2x22
+ x1 x2 et C =] − 2, 2[×]
− 2, 2[ qui est un ouvert
2 T −1
de R . Soit x̄ = (−1, 1) . On a ∇f (x̄) = −5 . Alors, x̄ ne vérifie pas
la condition nécessaire d’optimalité de premier ordre, et par suite ne peut
pas être un minimum local de (P). L’unique point réalisable qui satisfait la
condition nécessaire d’optimalité est (0, 0)T .
Théorème 4.2 (Conditions nécessaire d’optimalité de second ordre) Soit
x̄ ∈ C une solution locale du problème (P). Supposons que f est deux fois
continûment différentiable en x̄. Alors, ∇f (x̄) = 0, et la matrice hessienne
∇2 f (x̄) est semi-définie positive sur Rn .

31
32 CHAPTER 4. CONDITIONS D’OPTIMALITÉ

Conditions suffisantes d’optimalité

Théorème 4.3 Supposons que f et C sont convexes. Soit x̄ ∈ C. Supposons
de plus que f est différentiable en x̄ et ∇f (x̄) = 0. Alors, x̄ est solution de
(P), i.e., minimum global de f sur C.

Alors, quand le problème (P) est convexe d’après les Théorèmes 4.1 et 4.3
on a la caractérisation d’optimalité suivante.

Corollaire 4.1 Supposons que f et C sont convexes. Soit x̄ ∈ C. Supposons

que f est différentiable en x̄. Alors, x̄ est un minimum global de (P) si et
seulement si ∇f (x̄) = 0.

Théorème 4.4 (Conditions suffisantes d’optimalité de premier ordre) Sup-

posons que f est deux fois différentiable en x̄ ∈ C. Si ∇f (x̄) = 0, et la
matrice hessienne ∇2 f (x̄) est définie positive sur Rn , alors x̄ est un mini-
mum local strict de f sur C.

Remarque 4.1 Si ∇f (x̄) = 0 et ∇2 f (x̄) est semi-définie positive, en

général x̄ n’est pas un minimum local comme on peut le voir dans l’exemple
suivant.

Exemple 4.2 Soit C = R2 , et f (x1 , x2 ) = −2x61 + x22 . Soit x̄ = (x̄1 , x̄2 )T .

L’équation
∇f (x̄) = (−12x̄51 , 2x̄2 )T = (0, 0)T ,
admet la solution unique x̄ = (0, 0)T . On a

−60 x̄41 0
   
0 0
∇2 f (x̄) = = ,
0 2 0 2
1
2
qui est semi-définie positive. Soit xk = k . On a f (xk ) = − 6 , et xk → x̄,
0 k
quand k → +∞. Pour tout r > 0, il existe k0 (r) = k0 ∈ N, tel que pour tout
k ≥ k0 , xk ∈ B(x̄, r), et
2
f (xk ) = − < f (x̄) = 0.
k6
Par suite, x̄ n’est pas un minimum local de f sur R2 .

4.2 Contraintes d’Egalités Linéaires

Considérons le problème de minimisation suivant

(P) : min f (x),

x∈Rn
Ax=b

où f : Rn → R, A ∈ Mm,n (R), et b ∈ Rm , avec m ≤ n. Posons

4.2. CONTRAINTES D’EGALITÉS LINÉAIRES 33
n o
C = x ∈ Rn / Ax = b .

Remarque 4.2 1) Soient x̄ ∈ C, i.e., Ax̄ = b, et d ∈ Rn \ {0}. Soit

KerA = {x ∈ Rn : Ax = 0Rm }, le noyau de A. Alors, d est une
direction admissible de C en x̄
 
⇐⇒ ∃ α > 0, tel que x̄ + td ∈ C, ∀ t ∈ 0, α
 
⇐⇒ ∃ α > 0, tel que A(x̄ + td) = b, ∀ t ∈ 0, α
 
⇐⇒ ∃ α > 0, tel que tAd = 0, ∀ t ∈ 0, α
⇐⇒ Ad = 0 ⇐⇒ d ∈ KerA

où pour le passage de la deuxième équivalence à la troisième, on utilise

le fait que Ax̄ = b. Donc d est une direction admissible de C en x̄, si
et seulement si d ∈ KerA.

2) Puisque KerA est un espace vectoriel, nous avons alors

d ∈ KerA ⇐⇒ −d ∈ KerA.

Donc d est une direction admissible de C en x̄ si et seulement si −d

est une direction admissible de C en x̄.

Conditions Nécessaires d’Optimalité

Théorème 4.5 Soit x̄ ∈ C une solution locale (minimum local) de (P).
Supposons que f est différentiable en x̄. Alors, il existe un vecteur λ ∈ Rm ,
vérifiant
∇f (x̄) + AT λ = 0.
Si de plus, rgA = m, alors le vecteur λ est unique.

Conditions Suffisantes d’Optimalité

Théorème 4.6 Soit x̄ ∈ C. Supposons que f est différentiable en x̄ et
convexe sur Rn . S’il existe λ ∈ Rm , tel que

∇f (x̄) + AT λ = 0,

alors, x̄ est un minimum global de (P).

Les résultats des Théorèmes 4.5 et 4.6 entraînent le résultat suivant.

Corollaire 4.2 (Conditions nécessaires et suffisantes d’optimalité) Soit x̄ ∈

C. Supposons que f est convexe et différentiable en x̄ et que rgA = m. Alors,
x̄ est un minimum global de (P) si et seulement si il existe λ ∈ Rm , tel que

∇f (x̄) + AT λ = 0.
34 CHAPTER 4. CONDITIONS D’OPTIMALITÉ

4.3 Contraintes d’Egalités non Linéaires

Considérons le problème de minimisation suivant

(P) : Min f (x)

x∈Rn
h(x)=0

où f : Rn → R, et h = (h1 , ..., hm )T : Rn → Rm , hj : Rn → R, avec m ≤ n.

Posons n o
C = x ∈ Rn : h(x) = 0 .

Dans le cas où f et h sont différentiables on dit que (P) est un problème

différentiable.

Conditions Nécessaires d’Optimalité

Théorème 4.7 Soit x̄ ∈ C un minimum local de f sur C. Supposons que les

fonctions f et h sont continûment différentiables sur Rn , et que les vecteurs
gradients ∇h1 (x̄),...,∇hm (x̄), sont linéairement indépendants. Alors, il ex-
iste un unique vecteur λ = (λ1 , ..., λm )T ∈ Rm , tel que
m
X
∇f (x̄) + λi ∇hi (x̄) = 0.
i=1

Le vecteur λ = (λ1 , ..., λm )T est dit le vecteur multiplicateur de Lagrange

associé au problème (P) (les scalaires λi , i = 1, ..., m, sont aussi appelés les
multiplicateurs de Lagrange).

4.4 Contraintes d’Inégalités

Considérons le problème de minimisation suivant

(P) : min f (x)

x∈C

où f : Rn → R, C l’ensemble défini par

C = x ∈ Rn : gi (x) ≤ 0, i = 1, ..., m ,


et gi : Rn → R, des fonctions. Soit x̄ ∈ C. Si gi (x̄) = 0, on dit que la

contrainte gi est active ou saturée en x̄. On note par I(x̄) = {i ∈ {1, ..., m} :
gi (x̄) = 0}, l’ensemble des indices des contraintes gi , i = 1, ..., m, saturées
en x̄.

Remarque 4.3 Si les fonctions gi , i = 1, ..., m, sont convexes, alors

l’ensemble C est convexe (voir TD 1).
4.5. CONTRAINTES D’EGALITÉS ET D’INÉGALITÉS 35

Conditions Nécessaires d’Optimalité

Théorème 4.8 Soit x̄ un point réalisable minimum local de f sur C. Sup-

posons que les fonctions f , gi , i = 1, ..., m, sont de classe C 1 , et que l’une
des quatre conditions suivantes de qualification des contraintes est satisfaite
1) les fonctions gi , i = 1, ..., m, sont affines,
2) Condition de Slater : les fonctions gi , i = 1, ..., m, sont convexes et il
existe x0 ∈ Rn , tel que gi (x0 ) < 0, pour tout i = 1, ..., m,
3) {∇gi (x̄), i ∈ I(x̄)} est un système libre,
4) Condition de Mangasarian-Fromovitz

(MFCQ): ∃ d ∈ Rn \ {0} tel que h∇gi (x̄), di < 0, ∀ i ∈ I(x̄).

Alors, il existe λi ∈ R, i = 1, ..., m, tels que

i) ∇f (x̄) + m
P
i=1 λi ∇gi (x̄) = 0,

ii) λi gi (x̄) = 0, ∀ i = 1, ..., m (condition de complémentarité),

iii) λi ≥ 0, ∀ i = 1, ..., m.

Conditions Suffisantes d’Optimalité

Théorème 4.9 Supposons que les fonctions f , gi , i = 1, ..., m, sont con-

vexes et de classe C 1 . Soit x̄ un point réalisable de (P). S’il existe un vecteur
λ = (λ1 , ..., λm )T ∈ Rm , tel que les conditions de Kuhn-Tucker i), ii) et iii)
ci-dessus sont satisfaites, alors x̄ est un minimum global de f sur C.

4.5 Contraintes d’Egalités et d’Inégalités

Considérons le problème de minimisation suivant

(P) : min f (x),

x∈C

où n o
C = x ∈ Rn : g(x) ≤ 0, h(x) = 0 ,

f : Rn → R, g = (g1 , ..., gm )T : Rn → Rm , et h = (h1 , ..., hl )T : Rn → Rl ,

des fonctions avec ` < n. Si les fonctions f , g et h sont différentiables, on dit
que le problème (P) est différentiable.

Remarque 4.4 Si les fonctions gi , i = 1, ..., m, sont convexes, et les fonc-

tions hj , j = 1, ..., l, sont affines, alors l’ensemble C est convexe (voir TD
6).

Posons I = {1, ..., m} et J = {1, ..., `}. Alors, on a le théorème suivant.

36 CHAPTER 4. CONDITIONS D’OPTIMALITÉ

Théorème 4.10 (Conditions nécessaires d’optimalité de Kuhn-Tucker) Soit

x̄ ∈ C un minimum local de (P). Supposons que les fonctions f , et gi ,
i ∈ I, sont de classe C 1 et que les fonctions hj , j = 1, ..., l, avec l < n,
sont continûment différentiables sur Rn . Si de plus, la condition suivante de
qualification des contraintes (MFCQ) (condition de Mangasarian-Fromovitz)
est satisfaite en x̄:
1) ∃ d ∈ Rn \ {0}/ h∇gi (x̄), di < 0, ∀ i ∈ I(x̄), h∇hj (x̄), di = 0, ∀ j ∈ J,
2) les gradients ∇h1 (x̄), ..., ∇h` (x̄), sont linéairement indépendants,
alors, il existe α = (α1 , ..., αm )T et β = (β1 , ..., β` )T , tels que
m
X `
X
i) ∇f (x̄) + αi ∇gi (x̄) + βj ∇hj (x̄) = 0,
i=1 j=1

ii) αi gi (x̄) = 0, ∀ i ∈ I (condition de complémentarité),

iii) αi ≥ 0, ∀ i ∈ I.
Les vecteurs α et β sont appelés les multiplicateurs de Lagrange (ou de
Lagrange-Kuhn-Tucker) associés au problème (P) ou associés respectivement
aux contraintes d’égalités et d’inégalités.

Remarque 4.5 La condition de Mangasarian-Fromovitz ne peut être sat-

isfaite si ` = n. En effet dans ce cas, puisque ∇h1 (x̄), ..., ∇h` (x̄), sont
linéairement indépendants, on a
n o n o
n
R = Vect ∇h1 (x̄), ..., ∇h` (x̄) = Vect ∇h1 (x̄), ..., ∇hn (x̄) ,

et donc le vecteur d est orthogonal aux vecteurs ∇h1 (x̄), ..., ∇hn (x̄), qui for-
ment une base de Rn . Par conséquent d ∈ (Rn )⊥ = {0}.

Conditions Suffisantes d’Optimalité

Théorème 4.11 (Conditions suffisantes d’optimalité de Kuhn-Tucker) Soit
x̄ ∈ C un point réalisable de (P). Supposons que les fonctions f et g sont
convexes et de classe C 1 , et les fonctions hj , j = 1, ..., l, sont affines sur Rn .
Si x̄ satisfait les conditions suivantes dites de Kuhn-Tucker :
∃ (α, β) ∈ Rm × R` , α = (α1 , ..., αm )T , β = (β1 , ..., β` )T , tels que
m
X `
X
i) ∇f (x̄) + αi ∇gi (x̄) + βj ∇hj (x̄) = 0,
i=1 j=1

ii) αi gi (x̄) = 0, ∀i = 1, ..., m,

iii) αi ≥ 0, ∀ i = 1, ..., m,
alors, x̄ est un minimum global de (P).
4.6. CONDITIONS D’OPTIMALITÉ: CAS NON DIFFÉRENTIABLE 37

4.6 Conditions d’Optimalité: cas non Différentiable

Soient f : Rn → R, une fonction convexe et C un sous ensemble non vide
convexe de Rn . Dans cette section, on donne des conditions d’optimalité
dans le cas non différentiable pour les problèmes de minimisation suivants

(P1 ) : min f (x) et (P2 ) : min f (x).

x∈Rn x∈C

Ces conditions d’optimalité sont exprimées en fonction du cône normal et du

sous différentiel.

Théorème 4.12 Soit x̄ ∈ Rn . Alors, les propriétés suivantes sont équiva-

lentes

i) x̄ minimise f sur Rn , i.e., solution globale de (P1 ),

ii) 0 ∈ ∂f (x̄).

Théorème 4.13 Supposons que f et C sont convexes. Alors, les propriétés

suivantes sont équivalentes
i) x̄ minimise f sur C, i.e., solution globale de (P2 ),
ii) 0 ∈ ∂f (x̄) + NC (x̄),
où NC (x̄) désigne le cône normal à C en x̄.

Dans le cas où f est en plus différentiable, on a ∂f (x) = {∇f (x)}, et le

Théorème 4.13 donne alors le résultat suivant

Théorème 4.14 Supposons que f est convexe différentiable sur Rn et C

convexe. Alors, les propriétés suivantes sont équivalentes

i) f (x̄) = min f (x), i.e., x̄ minimise f sur C,

x∈C

ii) −∇f (x̄) ∈ NC (x̄).

Remarque 4.6 Si C est un ouvert de Rn (en particulier C = Rn ), ou

x̄ ∈ intC, alors NC (x̄) = {0} (voir chapitre 2), et donc la propriété ii) du
Théorème 4.14 devient ∇f (x̄) = 0.

Théorème 4.15 Soient f, f1 , ..., fk : Rn → R, des fonctions convexes. Con-

sidérons le problème
(P) : min f (x),
x∈C

où
k
\ n o
C= Ci et Ci = x ∈ Rn / fi (x) ≤ 0 , i = 1, ..., k.
i=1
38 CHAPTER 4. CONDITIONS D’OPTIMALITÉ

Supposons que ki=1 intCi 6= ∅. Un point x̄ ∈ C résout (P) si et seulement

T
si il existe α1 , ..., αk ∈ R, tels que
 Pk
 i) 0 ∈ ∂f (x̄) + i=1 αi ∂fi (x̄),
ii) αi fi (x̄) = 0, ∀ i = 1, ..., k,
iii) αi ≥ 0, ∀ i = 1, ..., k.


Remarque 4.7 Dans le cas où les fonctions fi , i = 1, ..., k, sont différen-

tiables et convexes, alors les conditions i), ii) et iii) du Théorème 4.15 de-
viennent  Pk
 i) ∇f (x̄) + i=1 αi ∇fi (x̄) = 0,
ii) αi fi (x̄) = 0, ∀ i = 1, ..., k,
iii) αi ≥ 0, ∀ i = 1, ..., k.


qui sont les conditions de Kuhn-Tucker dans le cas différentiable.

Chapter 5

Dualité Lagrangienne

5.1 Introduction
Soient f : Rn → R, g = (g1 , ..., gm )T : Rn → Rm , h = (h1 , ..., hl ) : Rn → Rl
des fonctions, et X un sous ensemble non vide de Rn . On considère le
problème de minimisation suivant

(P) : min f (x).

x∈X
g(x)≤0
h(x)=0

Posons
n o
C = x ∈ X / g(x) ≤ 0, h(x) = 0 .

Définition 5.1 1) La fonction L : Rn × Rm l

+ × R → R, définie par

L(x, λ, µ) = f (x) + λ> g(x) + µ> h(x)

m
X l
X
= f (x) + λi gi (x) + µj hj (x),
i=1 j=1

est appelée la fonction lagrangienne associée au problème (P), où λ =

(λ1 , ..., λm )> et µ = (µ1 , ..., µl )> .

2) Le problème dual lagrangien associé au problème (P) est le problème

(D) : max θ(λ, µ),

(λ,µ)∈Rm
+ ×R
l

où
n o
θ(λ, µ) = inf f (x) + λ> g(x) + µ> h(x)
x∈X
= inf L(x, λ, µ).
x∈X

39
40 CHAPTER 5. DUALITÉ LAGRANGIENNE

Le problème (P) est appelé problème primal, θ la fonction duale, et λ

et µ les variables duales.

Définition 5.2 1) On dit que

i) les problèmes (P) et (D) sont en dualité faible si inf(P) ≥ sup(D),
ii) les problèmes (P) et (D) sont en dualité forte si inf(P) = sup(D),
et le dual (D) admet des solutions.
2) Le nombre ν = inf(P) − sup(D) est appelé le saut de dualité. Quand
(P) et (D) sont en dualité forte, on a ν = 0.

5.2 Etude de la Dualité Lagrangienne

Le recours à la dualité suppose que la résolution du problème dual (D) est
moins difficile que celle du problème primal (P). Dans section, on donne des
résultats sur la dualité faible et forte entre le problème primal (P) et son
dual (D). Ces résultats permettent de faire le lien entre les valeurs optimales
et les solutions des problèmes (P) et (D).

Dualité Faible
Théorème 5.1 (Dualité faible) On a
inf(P) ≥ sup(D),
i.e., les problèmes (P) et (D) sont en dualité faible. Donc, f (x) ≥ θ(λ, µ),
pour tous x ∈ C, et (λ, µ) ∈ Rm+ ×R.
l

Corollaire 5.1 1) s’il existe x̄ ∈ C, et (λ̄, µ̄) ∈ Rm l

+ × R , tels que

f (x̄) ≤ θ(λ̄, µ̄)

alors x̄ est solution de (P) et (λ̄, µ̄) solution de (D).
2) Si inf(P) = −∞, alors θ(λ̄, µ̄) = −∞, pour tout (λ, µ) ∈ Rm l
+ ×R.

Dualité Forte
Le théorème suivant donne des conditions assurant la dualité forte entre (P)
et son dual (D).
Théorème 5.2 (Dualité forte) Supposons que X est convexe, les fonctions
f et g sont convexes et les fonctions hj , j = 1, ..., m, sont affines. De plus,
on suppose que la condition suivante de qualification des contraintes (dite
condition de Slater) est satisfaite

 ∃x b ∈ X tel que gi (x̂) < 0, i = 1, ..., m et h(x̂) = 0,

0 ∈ int h(X),

5.2. ETUDE DE LA DUALITÉ LAGRANGIENNE 41
n o
où h(X) = h(x), x ∈ X . Alors

1) inf(P) = sup(D),

2) si de plus inf(P) est fini, alors sup(D) est atteint en un point (ū, v̄) ∈
Rm
+ ×R,
l

3) si inf(P) est atteint en un point x̄, alors,

ūT g(x̄) = 0.