Quelques résultats d’existence

Définition 1. Soient Ω un sous-ensemble de Rn et f : Rn → ]−∞, ∞] une

fonction.
(1) Un vecteur x̄ ∈ Ω est un minimiseur local de f sur Ω s’il existe ε > 0 tel
que
∀x ∈ Ω ∩ B(x̄, ε), f (x) ≥ f (x̄).
(2) Un vecteur x̄ ∈ Ω est un minimiseur global de f sur Ω si
∀x ∈ Ω, f (x) ≥ f (x̄).
(3) Un vecteur x̄ ∈ Ω est un minimiseur local strict de f sur Ω s’il existe
ε > 0 tel que


∀x ∈ Ω ∩ B(x̄, ε) \ {x̄} , f (x) > f (x̄).
(4) Un vecteur x̄ ∈ Ω est un minimiseur global strict de f sur Ω si
∀x ∈ Ω \ {x̄}, f (x) > f (x̄).

Remarque. L’ensemble B(x̄, ε) \ {x̄} s’appelle la boule ouverte pointée de

centre x̄ et de rayon ε.
1
Définition 2. Soit E un sous-ensemble de R. Une suite minimi-
sante de E est une suite (xk )k∈N∗ à valeurs dans E telle que

xk → inf E lorsque k → ∞.

Par exemple, la suite (xk )k∈N∗ définie par xk = 1/k est une suite
minimisante de l’intervalle ]0, 1].

Proposition 1. Soit E un sous-ensemble non vide de R. Alors E

admet au moins une suite minimisante.

2
Définition 3. Soient Ω un sous-ensemble de Rn et f : Ω →
]−∞, ∞] une fonction. Une suite minimisante de f sur Ω est
une suite (xk )k∈N∗ à valeurs dans Ω telle que

f (xk ) → inf f (x) lorsque k → ∞.

x∈Ω

Par exemple, si Ω = R∗+ et f (x) = 1/x, alors la suite (xk )k∈N∗

définie par xk = k est une suite minimisante de f sur R∗+.

Proposition 2. Soient Ω un sous-ensemble de Rn et f : Ω →

]−∞, ∞] une fonction quelconque. Alors f admet au moins une
suite minimisante sur Ω.

3
Théorème 1. Soient K ⊂ Rn un compact non vide et f : K → R
une fonction continue. Alors il existe un minimiseur global de f
sur K.
Démonstration. C’est une conséquence immédiate du fait que toute fonction
continue atteint ses bornes sur tout compact, qui est lui même une consé-
quence du fait que l’image d’un compact par une application continue est un
compact. Voici un autre argument utilisant la notion de suite minimisante.

Soit (xk )k∈N∗ une suite minimisante de f sur K :

f (xk ) → inf f (x) lorsque k → ∞.
x∈K

Puisque K est compact, on peut extraire une sous-suite (xkj )j∈N∗ qui converge
vers un point de K. Notons x̄ ce point. On a :
xkj → x̄ et f (xkj ) → inf f (x) lorsque j → ∞.
x∈K

Par continuité de f , f (xkj ) → f (x̄) lorsque j → ∞. Par unicité de la limite,

f (x̄) = inf f (x).
x∈K

4
Définition 4. Soient F ⊂ Rn un sous-ensemble fermé non vide et f : F → R.
(1) On dit que f est inifinie à l’infini ou 0-coercive si
f (x) → ∞ lorsque kxk → ∞,
autrement dit, si
R∗+ :
 
∀M ∈ R+ , ∃R ∈ kxk ≥ R ⇒ f (x) ≥ M .
(2) On dit que f est 1-coercive si
f (x)
→∞ lorsque kxk → ∞,
kxk
autrement dit, si
 
f (x)
∀M ∈ R+ , ∃R ∈ R∗+ : kxk ≥ R ⇒ ≥M .
kxk

Remarque. Toute fonction 1-coercive est évidemment 0-coercive.

5
Théorème 2. Soient F ⊂ Rn un fermé non vide et f : F → R une
fonction continue 0-coercive. Alors il existe un minimiseur global
de f sur F .
Démonstration. Nous allons montrer que minimiser f sur F équivaut à mini-
miser f sur un compact K ⊂ F .
Puisque F est non vide et f à valeurs réelles, inf x∈F f (x) ∈ [−∞, ∞[. Donc
∃M ∈ R : M > inf f (x).
x∈F

L’ensemble K := {x ∈ F | f (x) ≤ M } est compact, non vide, inclus dans F .

En effet,
• K est non vide puisque M > inf x∈F f (x) ;
−1


• K est fermé puisque K = F ∩ f ]−∞, M ] , et f est continue ;
• K est borné puisque f est 0-coercive.
D’après le théorème précédent, f atteint son minimum sur K, disons en x̄.
Mais x̄ est aussi un minimiseur de f sur F , puisque
∀x ∈ F \ K, f (x) > M > f (x̄) = inf f (x).
x∈K

6
 Conditions d’optimalité
pour les problèmes sans contrainte

Optimalité locale

On s’intéresse ici aux problèmes de la forme suivante :

(P ) Minimiser f (x), x ∈ Rn,

où f : Rn → R. Dans, un premier temps, nous nous intéressons
à l’optimalité locale. La section suivante sera consacrée au cas
convexe, qui permet de passer de l’optimalité locale à l’optimalité
globale.

7
Théorème 3. [CN1] Soient f : Rn → R une fonction et x̄ un
minimiseur local de f . Si f est différentiable en x̄, alors

∇f (x̄) = 0. (1)

La condition (1) est appelée condition nécessaire d’optimalité

locale du premier ordre. Le théorème ci-dessus est souvent appelé
principe de Fermat.

8
Démonstration. Soit y quelconque dans Rn. Puisque f est différentiable en x̄,
on a, pour tout t ∈ R,
f (x̄ + ty) = f (x̄) + h∇f (x̄), tyi + o(ktyk)
= f (x̄) + h∇f (x̄), tyi + ktykε(ktyk),
où la fonction ε est telle que ε(h) → 0 lorsque h → 0. Donc,
f (x̄ + ty) − f (x̄)
h∇f (x̄), yi = − kykε(ktyk).
t
Puisque x̄ est un minimiseur local, il existe un ouvert Ω contenant x̄ tel que
∀x ∈ Ω, f (x) ≥ f (x̄).
On en déduit que, pour t > 0 suffisamment petit,
f (x̄ + ty) − f (x̄)
≥ 0 et donc h∇f (x̄), yi ≥ −kykε(ktyk).
t
Par passage à la limite t ↓ 0, on obtient : h∇f (x̄), yi ≥ 0. Puisque y est
quelconque dans Rn, il s’ensuit que ∇f (x̄) = 0.

9
Notation. Pour toute matrice symétrique S, la notation S  0
signifie : S est semi-définie positive, et la notation S  0 signifie :
S est définie positive.

Théorème 4. [CN2] Soient f : Rn → R une fonction et x̄ un

minimiseur local de f . S’il existe r > 0 tel que f soit deux fois
différentiable sur B(x̄, r), alors

∇2f (x̄)  0. (2)

La condition (2) est appelée condition nécessaire d’optimalité

locale du second ordre.

10
Démonstration. Soit y quelconque dans Rn. Puisque f est deux fois différen-
tiable sur B(x̄, r), on peut écrire
1
f (x̄ + ty) = f (x̄) + h∇f (x̄), tyi +ty, ∇2 f (x̄) · ty + ktyk2 ε(ktyk), (3)
2
avec ε(h) → 0 lorsque h → 0. D’après le théorème 3, ∇f (x̄) = 0, de sorte que
h∇f (x̄), tyi = 0. L’équation (3) devient :
1 f (x̄ + ty) − f (x̄)
y, ∇2f (x̄) · y = − k y k 2
ε(ktyk).
2 t2
Puisque x̄ est un minimiseur local, il existe ε > tel que, pour tout x ∈ B(x̄, ε),
f (x) ≥ f (x̄). Il s’ensuit que, pour t > 0 suffisamment petit,
f (x̄ + ty) − f (x̄) 1
≥ 0, et donc y, ∇2f (x̄) · y ≥ −kyk2ε(ktyk).
t2 2
En faisant tendre t vers 0, nous voyons que y, ∇2 f (x̄) · y ≥ 0. Puisque y est
quelconque dans Rn, il s’ensuit que ∇2 f (x̄) est semi-définie positive.

11
Théorème 5. [CS1] Soient f : Rn → R une fonction et x̄ ∈ Rn.
On suppose qu’il existe r > 0 tel que :
(1) f soit différentiable en tout point de B(x̄, r) ;
(2) ∀x ∈ B(x̄, r) \ {x̄}, h∇f (x), x − x̄i ≥ 0.
Alors x̄ est un minimiseur local de f .

12
Démonstration. Soient x ∈ B(x̄, r) \ {x̄} et ϕ : [0, 1] → R définie par



ϕ(t) = f (1 − t)x̄ + tx = f x̄ + t(x − x̄) .
Les hypothèses sur f impliquent que
• ϕ est continue sur [0, 1] ;
• ϕ est dérivable sur ]0, 1[, de dérivée ϕ0 (t) = h∇f (x̄ + t(x − x̄)), x − x̄i.
D’après le théorème des accroissements finis, il existe τ ∈ ]0, 1[ tel que
0


ϕ(1) − ϕ(0) = ϕ (τ ) = ∇f x̄ + τ (x − x̄) , x − x̄ ,
c’est-à-dire,


f (x) − f (x̄) = ∇f (1 − τ )x̄ + τ x , x − x̄
1

= ∇f (1 − τ )x̄ + τ x , (1 − τ )x̄ + τ x − x̄ .
τ
Or, (1 − τ )x̄ + τ x ∈ B(x̄, r) \ {x̄} puisque B(x̄, r) est convexe et τ 6= 0. La
condition (2) montre alors que f (x) − f (x̄) ≥ 0. Puisque x était arbitraire dans
B(x̄, r) \ {x̄}, on a montré que x̄ est un minimiseur local de f .

13
Théorème 6. [CS2] Soient f : Rn → R une fonction et x̄ ∈ Rn.
On suppose que :
(1) f est deux fois différentiable en x̄ ;
(2) ∇f (x̄) = 0 ;
(3) ∇2f (x̄)  0.
Alors x̄ est un minimiseur local strict de f .

14
Démonstration. Puisque f est deux fois différentiable en x̄ (condition (1)), et
puisque ∇f (x̄) = 0 (condition (2)), on peut écrire :
1
∇2 f (x̄) · h, h + khk2 ε(khk),
f (x̄ + h) − f (x̄) =
2
où ε(t) → 0 lorsque t → 0. Puisque ∇2 f (x̄)  0 (condition (3)), il existe λ > 0
tel que
∀h ∈ Rn, ∇2 f (x̄) · h, h ≥ λkhk2 .
On a donc :
 
λ
f (x̄ + h) − f (x̄) ≥ + ε(khk) khk2 .
2
Or, il existe r > 0 tel que, pour tout h ∈ B(0, r), |ε(khk)| ≤ λ/4. Ainsi
λ
khk2 ,
f (x̄ + h) − f (x̄) ≥
4
ce qui montre que pour tout h ∈ B(0, r) \ {0}, f (x̄ + h) > f (x̄).

15
 Optimalité globale

Théorème 7. Soient f : Rn → R une fonction continue et x̄ un

minimiseur local de f .
(1) Si f est convexe, alors x̄ est un minimiseur global de f .
(2) Si f est strictement convexe, alors x̄ est l’unique minimiseur
global de f .

16
Démonstration.
(1) Supposons que f soit convexe et que x̄ soit un minimiseur local de f , ce
qui s’écrit :
∃ε > 0 : ∀x ∈ B(x̄, ε), f (x) ≥ f (x̄).
Supposons, en vue d’obtenir une contradiction, qu’il existe x̂ ∈ Rn tel que
f (x̂) < f (x̄). Par convexité de f ,


∀λ ∈ ]0, 1[ , f (1 − λ)x̂ + λx̄ ≤ (1 − λ)f (x̂) + λf (x̄) < f (x̄).
Fixons ε > 0. Pour λ suffisamment proche de 1,
x := (1 − λ)x̂ + λx̄ ∈ B(x̄, ε).
Ainsi, pour tout ε > 0, il existe x ∈ B(x̄, ε) tel que f (x) < f (x̄), en
contradiction avec le fait que x̄ soit un minimiseur local de f .
(2) Supposons que f soit strictement convexe. D’parès la première partie, x̄
est un minimiseur global de f . Supposons, en vue d’obtenir une contra-
diction, que x0 soit un minimiseur global de f distinct de x̄. Alors, par
stricte convexité de f ,


∀λ ∈ ]0, 1[, f (1 − λ)x̄ + λx0 < (1 − λ)f (x̄) + λf (x0 ) = f (x̄),
en contradiction avec la minimalité de x̄.
17
 Conditions d’optimalité
pour les problèmes avec contraintes

En présence de contraintes, il n’est plus possible d’utiliser les

conditions d’optimalité vues pour les problèmes sans contraintes.

Exemple 1. La solution du problème

Minimiser f (x) := x2
s. c. x ≥ 1
est x = 1 et pourtant f 0(1) = 2 6= 0.

Notation. Dans la suite, CN (resp. CS) signifiera Conditions Né-

cessaires (resp. Conditions Suffisantes).
18
 Cas général
Soient f : Rn → R et C un sous-ensemble de Rn. On considère le problème
d’optimisation suivant :
Minimiser f (x)
(P )
s. c. x ∈ C.
Théorème 8. Soient f : Rn → R une fonction différentiable et C ⊂ Rn un
ensemble convexe fermé. Alors toute solution x̄ de (P ) vérifie la condition
nécessaire d’optimalité du premier ordre
∀x ∈ C, h∇f (x̄), x − x̄i ≥ 0.

Démonstration. Soit x̄ une solution de (P ) et x ∈ C. Par convexité de C,

x̄ + t(x − x̄) ∈ C pour tout ∀t ∈]0, 1[, et l’optimalité de x̄ s’écrit :


f x̄ + t(x − x̄) − f (x̄) ≥ 0.
En divisant par t, puis en faisant tendre t vers 0+ , on obtient :
f (x̄ + t(x − x̄)) − f (x̄)
h∇f (x̄), x − x̄i = f 0 (x̄; x − x̄) = lim ≥ 0.
t↓0 t

19
Dans le cas particulier où f et C sont convexes, la condition nécessaire du
théorème précédent devient suffisante.
Théorème 9. Soient f : Rn → R une fonction convexe différentiable, C ⊂ Rn
un ensemble convexe fermé et x̄ ∈ C. Alors x̄ est solution de (P ) si et
seulement si
∀x ∈ C, h∇f (x̄), x − x̄i ≥ 0. (4)

Démonstration. Il reste à montrer que la condition est suffisante. Par convexité

de f , on a
∀x ∈ C, f (x) − f (x̄) ≥ h∇f (x̄), x − x̄i
(voir le théorème 2 du chapitre Convexité). La condition (4) permet d’en
déduire que
∀x ∈ C, f (x) ≥ f (x̄).

Exercice. Montrer que si C = Rn, on retrouve la condition classique ∇f (x̄) = 0.

20
 Contraintes d’égalité et d’inégalité
On considère maintenant le problème d’optimisation avec contraintes d’éga-
lité et d’inégalité suivant :
Minimiser f (x)
(PEI ) s. c. g(x) ≤ 0
h(x) = 0,
où f : Rn → R, h : Rn → Rm et g : Rn → Rp .
Si x = (x1 , . . . , xn) ∈ Rn, on écrit x ≤ 0 pour signifier : x1 ≤ 0, . . . , xn ≤ 0.
Par exemple, dans le problème (PEI ) ci-dessus, la condition g(x) ≤ 0 équivaut
aux p conditions
g1 (x) ≤ 0, . . . , g1 (x) ≤ 0.
Une fonction g = (g1 , . . . , gp ) à valeurs vectorielles est dite différentiable
(resp. de classe C k ) lorsque chaque composante gj est différentiable (resp.
de classe C k ). Lorsque chaque fonction gj admet un gradient, la notation
∇g(x) désigne le p-uplet de vecteurs


∇g1 (x), . . . , ∇gp (x) .

21
 Conditions nécessaires d’ordre 1 non qualifiées

Théorème 10. [F. John, 1948] On suppose que f , g et h sont

de classe C 1(Rn). Soit x̄ une solution de (PEI ). Alors il existe
un réel µ̄0 et deux vecteurs λ̄ ∈ Rm, µ̄ ∈ Rp tels que
m
X m
X
µ̄0∇f (x̄) + µ̄i∇gi(x̄) + λ̄i∇hi(x̄) = 0, (5)
i=1 i=1
µ̄0 ≥ 0, (6)

∀i ∈ {1, . . . , p}, µ̄i ≥ 0, (7)

∀i ∈ {1, . . . , p}, µ̄igi(x̄) = 0. (8)

22
Remarque.
(1) Les réels λ̄i et µ̄i sont appelés des multiplicateurs de Lagrange.
(2) Les conditions g(x) ≤ 0 et h(x) = 0 sont appelées conditions de réalisa-
bilité ou de faisabilité du problème (PEI ).
(3) La condition (8) est dite de complémentarité.
(4) Les conditions (5) à (8) du théorème sont dites non qualifiées, pour la
raison suivante : lorsque µ̄0 devient nul, on n’a aucune information sur le
minimum de f .
(5) On s’intéressera, après la démonstration de ce théorème, à des conditions,
dites de qualification, qui permettent de garantir que µ̄0 6= 0.
Notation. Etant donnée une fonction ϕ : Rn → R, on notera ϕ+ la partie
positive de ϕ :
(
n +
ϕ(x) si ϕ(x) ≥ 0,
∀x ∈ R , ϕ (x) := max{ϕ(x), 0} =
0 si ϕ(x) < 0.

Exercice. Montrer que, si ϕ est différentiable sur Rn, alors (ϕ+ )2 est différen-
tiable sur Rn et
∀x ∈ Rn, ∇(ϕ+ )2 (x) = 2ϕ+ (x)∇ϕ(x).

23
Démonstration du théorème. On utilise une méthode de pénalisation : on
construit une suite de problèmes d’optimisation sans contraintes qui approche
le problème originel.

Pour tout entier k ≥ 1 et tout x ∈ Rn, posons

p 
X 2 m 
X 2
fk (x) := f (x) + k gi+ (x) +k hi(x) + kx − x̄k2 .
i=1 i=1

Nous allons étudier la suite de problèmes suivante :

(
Minimiser fk (x),
(Pk )
s. c. x ∈ B̄(x̄, ρ)
où B̄(x̄, ρ) est la boule fermée centrée en x̄ et de rayon ρ > 0.

Étape 1. Montrons que le problème (Pk ) admet au moins une solution.

La fonction fk étant continue, elle atteint son minimum sur le compact B̄(x̄, ρ).
On note x̄k un minimiseur de fk sur B̄(x̄, ρ).

24
Étape 2. Montrons que la suite (x̄k ) converge vers x̄.

• Par définition de x̄k , on a fk (x̄k ) ≤ fk (x̄) = f (x̄), c’est-à-dire,

p 
X 2 m 
X 2
f (x̄k ) + k gi+ (x̄k ) +k hi(x̄k ) + kx̄k − x̄k2 ≤ f (x̄). (9)
i=1 i=1

• On déduit de (9) que

p  2 m  2
X X 1 
gi+ (x̄k ) + hi(x̄k ) ≤ 2
f (x̄) − f (x̄k ) − kx̄k − x̄k .
i=1 i=1
k

Puisque, pour tout k, x̄k appartient au compact B̄(x̄, ρ), et puisque les
fonctions f et k · k sont continues, la suite
(f (x̄) − f (x̄k ) − kx̄k − x̄k2 )k∈N∗
est bornée. Un passage à la limite dans l’inégalité précédente permet
alors d’obtenir
∀i ∈ {1, . . . , p}, lim gi+ (x̄k ) = 0 et ∀i ∈ {1, . . . , m}, lim hi(x̄k ) = 0.
k→∞ k→∞

25
• La suite (x̄k ) étant à valeurs dans le compact B̄(x̄, ρ), on peut en extraire
une sous-suite (x̄kl ) qui converge vers un certain x̃ ∈ B̄.
• Par continuité des fonctions hi et gi+ , on a :

∀i ∈ {1, . . . , p}, gi+ (x̃) = 0 et ∀i ∈ {1, . . . , m}, hi(x̃) = 0.

Remarquons que la condition gi+ (x̃) = 0 équivaut à la condition gi(x̃) ≤ 0.
On en déduit que x̃ est réalisable pour (PEI ).
• De (9), on tire que f (x̄kl ) + kx̄kl − x̄k2 ≤ f (x̄). En passant à la limite, on
obtient f (x̃) + kx̃ − x̄k2 ≤ f (x̄). Donc
f (x̃) ≤ f (x̃) + kx̃ − x̄k2 ≤ f (x̄) ≤ f (x̃),
où la dernière inégalité provient de ce que x̄ est solution de (PEI ). Il
s’ensuit que f (x̄) = f (x̃), que kx̃ − x̄k, et donc que x̃ = x̄.
• Comme ce raisonnement est valable pour toutes les valeurs d’adhérence
de la suite (x̄k ), toute la suite (x̄k ) converge vers x̄.

26
Étape 3. Montrons les conditions (5) à (8) du théorème.

Comme la suite (x̄k ) converge vers x̄, les x̄k sont dans l’intérieur de B̄(x̄, ρ)
à partir d’un certain rang. Ainsi, pour k suffisamment grand, x̄k est un mi-
nimiseur local sans contraintes de fk . Par conséquent, pour k suffisamment
grand, ∇fk (x̄k ) = 0.

En utilisant l’exercice qui précède la démonstration, on obtient :

0 = ∇fk (x̄k )
p
X
= ∇f (x̄k ) + 2k gi+ (x̄k )∇gi(x̄k )
i=1
m
X
+ 2k hi(x̄k )∇hi(x̄k ) + 2(x̄k − x̄). (10)
i=1

27
• On pose
1 2kgi+ (x̄k ) 2khi(x̄k )
µ(k)
0 := , µi(k) := , λ(k)
i := ,
∆k ∆k ∆k
où
v
u p 
X 2 m 
X 2
u 2 + 2
∆k := t1 + 4k gi (x̄k ) + 4k hi(x̄k )
i=1 i=1

est choisi pour que le vecteur (µ(k) (k) (k) (k) (k) p
0 , µ1 , . . . , µp , λ1 , . . . , λm ) ∈ R×R ×R
m

soit de norme euclidienne égale à 1.

• Avec ces notations, et en divisant l’équation (10) par ∆k , on obtient :
p m
X X x̄k − x̄
0 = µ(k)
0 ∇f (x̄k ) + µ(k)
i ∇gi (x̄k ) + λ(k)
i ∇hi (x̄k ) + 2 . (11)
i=1 i=1
∆k

28
• Comme la suite (µ(k) (k) (k) (k) (k)
0 , µ1 , . . . , µp , λ1 , . . . , λm ) est à valeurs dans la
sphère unité de R × Rp × Rm , on peut en extraire une sous-suite qui
converge vers un vecteur
(µ̄0 , µ̄1 , . . . , µ̄p , λ̄1 , . . . , λ̄m ) 6= 0.
En passant à la limite dans (11), on obtient
p
X m
X
0 = µ̄0∇f (x̄k ) + µ̄i∇gi(x̄) + λ̄i∇hi(x̄k ),
i=1 i=1

en tenant compte de la continuité des applications ∇f , ∇hi, ∇gi et du

fait que ∆k ≥ 1. Il s’agit de la condition (5) du théorème.
• Les quantités µ̄0 , µ̄1 , ..., µ̄p , limites de quantités positives, sont positives.
On a donc les conditions (6) et (7) du théorème.
• Si gi(x̄) < 0, on a nécessairement gi(x̄k ) < 0 à partir d’un certain rang et
donc µ(k)i = 0 (par définition de µ(k)
i ). Par conséquent, à la limite, on a
µ̄i = 0. La condition (8) du théorème est donc satisfaite.

29
 Qualification des contraintes

On dit qu’une contrainte d’inégalité gi(x) ≤ 0 est active en y si gi(y) = 0. On

note I (x) l’ensemble des indices des contraintes actives en x :
I (x) = {i ∈ {1, . . . , p} | gi(x) = 0}.
Définition 5. On dit que x̄ ∈ Rn vérifie la condition de qualification de
Mangasarian-Fromovitz (MF) pour les contraintes g et h si
(1) x̄ est réalisable : h(x̄) = 0 et g(x̄) ≤ 0 ;
(2) les m vecteurs ∇hi(x̄) sont linéairement indépendants ;
(3) il existe d ∈ Rn \ {0} tel que
∀i ∈ I (x̄), h∇gi(x̄), di < 0, et ∀i ∈ {1, . . . , m}, h∇hi(x̄), di = 0.
Définition 6. On dit que x̄ ∈ Rn vérifie la condition de qualification (CQ2)
pour les contraintes h et g si
(1) x̄ est réalisable : g(x̄) ≤ 0 et h(x̄) = 0 ;
(2) les vecteurs ∇gj (x̄), j ∈ I (x̄) et ∇hi(x̄), i ∈ {1, . . . , m} sont linéairement
indépendants.

Exercice. Montrer que (CQ2) =⇒ (MF).

30
 Conditions nécessaires d’ordre 1 qualifiées

Théorème 11. [Karush-Kuhn-Tucker, 1951] On suppose que f ,

g et h sont de classe C 1(Rn). Soit x̄ une solution de (PEI ). Si x̄
est qualifié au sens de (MF), alors il existe deux vecteurs µ̄ ∈ Rp
et λ̄ ∈ Rm tels que
p
X m
X
∇f (x̄) + µ̄i∇gi(x̄) + λ̄i∇hi(x̄) = 0, (12)
i=1 i=1
∀i ∈ {1, . . . , p}, µ̄i ≥ 0, (13)

∀i ∈ {1, . . . , p}, µ̄igi(x̄) = 0. (14)

31
Démonstration. Il suffit de montrer que sous l’hypothèse (MF), le réel µ̄0
donné par le théorème 10 est non nul. On passe alors de la condition (5) à
la condition (12) en divisant par µ̄0 .

Supposons que µ̄0 = 0 et montrons qu’on arrive alors à une contradiction.

Distinguons 2 cas :
• Si tous les µ̄i sont nuls, alors les λ̄i ne sont pas tous nuls (puisque
(µ̄0 , µ̄1 , . . . , µ̄p , λ̄1 , . . . , λ̄m ) 6= 0) et la relation (5) du théorème 10
m
X m
X
µ̄0 ∇f (x̄) + µ̄i∇gi(x̄) + λ̄i∇hi(x̄) = 0
i=1 i=1

dégénère en
m
X
λ̄i∇hi(x̄) = 0.
i=1
Ceci contredit une partie de l’hypothèse (MF), à savoir, l’indépendance
linéaire des m vecteurs ∇hi(x̄).

32
• S’il existe j0 ∈ I (x̄) pour lequel µ̄j0 6= 0, c’est-à-dire µ̄j0 > 0, en faisant
le produit scalaire de (5)
p
X m
X
0 = µ̄0 ∇f (x̄) + µ̄i∇gi(x̄) + λ̄i∇hi(x̄)
i=1 i=1

avec la direction d apparaissant dans (MF), on obtient

p
X
0 = µ̄i h∇gi(x̄), di
i=1
X
= µ̄i h∇gi(x̄), di
|{z} | {z }
i∈I (x̄) ≥0 <0

≤ µ̄j0 h∇gj0 (x̄), di

< 0,
où la première égalité est due au fait que, d’après la condition de com-
plémentarité (8), µ̄i = 0 pour tout i 6∈ I (x̄).

33
Définition 7. On appelle lagrangien associé au problème (PEI ) la fonction
définie sur Rn × Rp × Rm par
p
X m
X
L(x, µ, λ) = f (x) + µigi(x) + λihi(x)
i=1 i=1
= f (x) + hµ, g(x)i + hλ, h(x)i .

Remarque. Avec cette notation, la condition (12) s’écrit encore

∇xL(x̄, µ̄, λ̄) = 0,
où ∇x désigne le gradient par rapport à la variable x.

34
 Conditions nécessaires et suffisantes dans le cas convexe

Théorème 12. On suppose que f , g et h sont de classe C 1(Rn),

que f et les gi sont convexes et que les hi sont affines. On
suppose encore que x̄ est qualifié au sens de (MF). Alors il y a
équivalence entre :
(1) x̄ est une solution de (PEI ) ;
(2) x̄ est réalisable pour (PEI ) et il existe deux vecteurs λ̄ ∈ Rm
et µ̄ ∈ Rp tels que les conditions (12) à (14) du théorème de
Karush-Kuhn-Tucker soient satisfaites.

35
Démonstration. Il suffit de montrer que les conditions (12) à (14) sont suffi-
santes pour qu’un vecteur x̄ réalisable soit solution de (PEI ).

Soit donc x̄ réalisable pour (PEI ) et satisfaisant les conditions (12) à (14).
Comme toutes les fonctions sont convexes, x → L(x, λ, µ) est convexe et la
condition (12) équivaut à dire que x̄ est un minimiseur de L(·, µ̄, λ̄). On a
donc :
∀x ∈ Rn, L(x, µ̄, λ̄) ≥ L(x̄, µ̄, λ̄).

D’une part, la réalisabilité de x̄ et la complémentarité induisent

p
X m
X
L(x̄, µ̄, λ̄) = f (x̄) + µ̄igi(x̄) + λ̄ihi(x̄) = f (x̄).
i=1 i=1

36
D’autre part, pour x ∈ Rn tel que h(x) = 0 et g(x) ≤ 0, du fait de la positivité
des multiplicateurs µ̄i, on a
p
X m
X
L(x, µ̄, λ̄) = f (x) + µ̄igi(x) + λ̄ihi(x)
i=1 i=1
Xm
= f (x) + µ̄igi(x)
i=1
≤ f (x).
On en déduit que, pour tout x ∈ Rn tel que h(x) = 0 et g(x) ≤ 0, on a
f (x̄) ≤ f (x),
autrement dit, que x̄ est solution de (PEI ).

37