OPTIMISATION

Adama COULIBALY
UFR de Mathématiques et Informatique,
Université Félix HOUPHOUET-BOIGNY D’ABIDJAN, 22
BP 582 Abidjan 22, Côte d’Ivoire.

6 octobre 2015
Table des matières

1 Introduction à l’optimisation 2
1.1 Introduction et Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Notion d’infimum, supremum, minimum, maximum . . . . . . . . . . . . . . . . . 2
1.3 Notion de programme mathématique . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Optimisation sans contraintes 6

2.1 Résultats d’existence et unicité . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Conditions d’optimalité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.1 Conditions d’optimalité du premier ordre . . . . . . . . . . . . . . . . . . . 8
2.2.2 Conditions d’optimalité du second ordre . . . . . . . . . . . . . . . . . . . 10
2.3 Méthodes numériques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3.1 Algorithmes et vitesse de convergence . . . . . . . . . . . . . . . . . . . . . 11
2.3.2 Méthodes de descente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3.3 Méthodes de directions conjuguées . . . . . . . . . . . . . . . . . . . . . . 13
2.3.4 Méthode de relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.5 Méthode de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3 Optimisation avec contraintes 18

3.1 Résultats d’existence et d’unicité . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2 Conditions d’optimalité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2.2 Cas des contraintes d’égalité . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.2.3 Problème avec contraintes d’inégalité . . . . . . . . . . . . . . . . . . . . . 27
3.2.4 Problème avec contraintes d’égalité et d’inégalité . . . . . . . . . . . . . . 35

1
Chapitre 1

Introduction à l’optimisation

1.1 Introduction et Notations

L’optimisation, c’est-à-dire les techniques permettant de chercher les minima ou les maxima
de fonctions ou de fonctionnelles intervient dans pratiquement tous les processus de modélisation
actuels. Qu’il s’agisse de problèmes directs (ajustement de données, contrôle optimal, résolution
des ystèmes linéaires par moindres carrés, etc) ou inverses (identification de paramètres), il est
rare qu’un problème d’optimisation plus ou moins complexe n’intervienne pas à un stade donné
de la modélisation et/ou de la simulation.
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 .
Nous considérons les notations suivantes.
⟨. , .⟩, ∥.∥ désigneront respectivement le produit scalaire usuel et la norme euclidienne de Rn .

1.2 Notion d’infimum, supremum, minimum, maximum

On définit ici les notions d’infimum de supremum, minimum et de maximum qui sont des
prérequis pour les démonstrations des résulatst d’existence et d’unicité d’extrema d’une fonction
donnée.

Définition 1.2.1 (Minorant/Majorant) Soit X une partie de R.

m ∈ R ∪ {−∞, +∞} est un minorant de X si et seulement si

∀ x ∈ X, m ≤ x.

M ∈ R ∪ {−∞, +∞} est un majorant de X si et seulement si

∀ x ∈ X, x ≤ M.

Définition 1.2.2 (Infimum/Supremum) Soit X une partie de R.

1) Si X est non vide et admet des minorants, par définition l’infimum de X est le plus grand
des minorants de X. On le note inf(X) ou inf x∈X (x).
Si X est non vide et n’admet pas de minorants, par convention, l’infimum de X est égal à
−∞.

2
 Si X = ∅, par convention son infimum est égal à +∞ : inf(∅) = +∞
2) Si X est non vide et admet des majorants, par définition le supremum de X noté sup(X)
ou supx∈X (x) est le plus petit des majorants de X.
Si X est non vide et n’admet pas de majorants, par convention, le supremum de X est égal à
+∞.
Si X = ∅, par convention sup(∅) = −∞.
Ces notions sont aussi caractérisées par :
Proposition 1.2.1 1) Si X est non vide et admet des minorants,
{
m ≤ x ∀x ∈ X
m = inf(X) ⇔
∀ε > 0, ∃xε ∈ X : m ≤ xε < m + ε.
2) Si X est non vide et admet des majorants,
{
x ≤ M ∀x ∈ X
M = sup(X) ⇔
∀ε > 0, ∃xε ∈ X : M − ε < xε ≤ M.
On a le résultat suivant.
Proposition 1.2.2 Pour tout X ⊂ R, on a supx∈X (x) = − inf x∈X (−x)
Définition 1.2.3 (Suite minimisante/Suite maximisante) Soit X une partie non vide de R.
On appelle suite minimisante de X, toute suite {xk } d’éléments de X telle que
lim xk = inf(X).
k→+∞

On appelle suite maximisante de X, toute suite {xk } d’éléments de X telle que

lim xk = sup(X).
k→+∞

On montre que
Proposition 1.2.3 Si X est une partie non vide R, alors il existe toujours une suite minimisante
de X et une suite maximisante de X.
Preuve : Montrons d’abord l’existence d’une suite minimisante. Comme X est non vide, alors
nécessairement inf(X) ∈ R ∪ {−∞}
i) inf(X) ∈ R. D’après la proposition (1.2.1)
1
∀k ∈ N∗ , ∃xk ∈ X : inf(X) ≤ xk ≤ inf(X) + .
k
La suite {xk } ainsi construite converge vers inf(X).
ii) inf(X) = −∞. X admet seulement −∞ comme minorant. Par conséquent pour tout k ∈ N,
il existe xk ∈ X tel que

xk ≤ −k
La suite {xk } ainsi construite converge vers −∞.
On montre de façon analogue l’existence d’une suite maximisante. 

Définition 1.2.4 (Minimum/Maximum) Soit X une partie de R.

On dit que X a un minimum si inf(X) ∈ X. Dans ce cas, on note min(X) = inf(X).
On dit que X a un maximum si sup(X) ∈ X. Dans ce cas, on note max(X) = sup(X).

3
1.3 Notion de programme mathématique
Soit f une fonction définie sur un ouvert Ω de Rn et à valeurs dans R̄ = [−∞, +∞] et C une
partie de Ω.

Définition 1.3.1 Un programme mathématique, est un problème de la forme

”Trouver α = inf x∈C f (x) (respectivement β = supx∈C f (x)) et x∗ ∈ C tel que f (x∗ ) = α
(respectivement β).”
On le note symboliquement α = inf x∈C f (x) (respectivement β = supx∈C f (x)) et on l’appelle
problème d’infimum (respectivement problème de supremum).

S’il existe un élément x∗ ∈ C tel que f (x∗ ) = α (respectivement β), le problème est dit
problème de minimisation (respectivement maximisation) et se note symboliquement :

α = min f (x) (respectivement β = max f (x)).

x∈C x∈C

Remarque 1.3.1 Très souvent par abus de notation, on note les problèmes d’infimum (respecti-
vement de supremum) comme des problèmes de minimisation (respectivement de maximisation).

De la proposition 1.2.2 on déduit la relation suivante.

Proposition 1.3.1
sup f (x) = − inf (−f )(x).
x∈C x∈C

La conséquence de cette proposition est que tout problème de programmation mathématique

peut se ramener à un problème de minimisation. Dans tout ce qui suit on considerera le problème

α = inf f (x) (P )
x∈C

On a les définitions suivantes.

Définition 1.3.2 Etant donné le problème (P ),

- la fonction f est dite fonction-objectif,
- α est la valeur optimale de (P ),
- l’ensemble C est appelé ensemble des solutions réalisables ou admissibles de (P ),
- l’ensemble {x ∈ C : f (x) = α} est appelé ensemble des solutions optimales de (P ).

On montre que

Proposition 1.3.2 Si g est une fonction à une variable strictement croissante, alors l’ensemble
des solutions optimales du programme (P ) est identique à celui de

inf g(f (x)) (P ∗ ).

x∈C

Outre les solutions optimales, on distingue aussi les solutions optimales locales définies comme
suit.

4
Définition 1.3.3 x∗ ∈ C est dite solution optimale locale de (P ) si
∃ V ∈ V(x∗ ) tel que f (x) ≥ f (x∗ ) ∀ x ∈ C ∩ V.
Ce minimum est dit strict si on a en plus

f (x∗ ) < f (x) ∀ x ∈ C ∩ V ∀ x ̸= x∗ ,

où V(x∗ ) désigne l’ensemble des voisinages de x∗ .

Par opposition les solutions optimales sont dites solutions optimales globales.
On a le résultat suivant.

Proposition 1.3.3 Si f est convexe, toute solution optimale locale de (P ) est globale.

La démonstration est immédiate.

On distingue les problèmes d’optimisation sans contraintes c’est le cas où C = Rn et avec
contraintes dans le cas contraire.
Dans le cas avec contraintes, très souvent l’ensemble C est défini à l’aide d’équations et/ou
d’inéquations. Par exemple,
{ }
gi (x) ≤ 0, i = 1, · · · , p
C= x∈R : n
,
hj (x) = 0, j = 1, · · · , m

où les fonctions gi et hj sont définies sur Rn et à valeurs dans R ∪{+∞}. Dans ce cas les conditions
gi (x) ≤ 0, i = 1, · · · , p et hj (x) = 0, j = 1, · · · , m sont appélées respectivement contraintes
d’inégalité et contraintes d’égalité.
Une classe de programmes mathématiques particulièrement intéressante est à signaler : c’est la
programmation linéaire. C’est le cas où la fonction-objectif est linéaire et l’ensemble des solutions
réalisables est un polyèdre convexe.
Dans la grande famille des problèmes de programmation non linéaire, on distingue le cas où
C est un polyèdre convexe et f quadratique (c’est-à-dire de la forme f (x) = 21 ⟨Ax, x⟩ + ⟨b, x⟩ où
A est une matrice à coefficients réels carrée d’ordre n et b un vecteur de Rn ), On dit alors que le
problème est un problème de programmation quadratique.

5
Chapitre 2

Optimisation sans contraintes

Dans cette partie nous nous intéressons aux problèmes du type

α = infn f (x) (P )
x∈R

où f est une fonction définie sur Rn et à valeurs dans R ∪ {+∞}

2.1 Résultats d’existence et unicité

Définition 2.1.1 Une fonction f : Rn → R ∪ {+∞} est dite inf-compacte si, pour tout λ ∈ R, la
section de niveau inférieure de f , Sλ (f ) = {x ∈ Rn : f (x) ≤ λ} est compact.

Théorème 2.1.1 Considérons le problème (P ). Si f est propre inf-compacte, l’ensemble des so-
lutions optimales globales de (P ) est un compact non vide et α > −∞.

Preuve : Soit S l’ensemble des solutions optimales de (P ). On a

S = ∩λ>α Sλ (f )

Les ensembles Sλ (f ) sont des compacts non vides emboı̂tés car f est inf-compacte. On en déduit
alors que S est un compact non vide. Soit alors x ∈ S, on a α = f (x) > −∞. Ce qui termine la
démonstration. 
On peut aussi démontrer ce résultat en utilisant la notion de suite minimisante qu’on définit
comme suit.

Définition 2.1.2 Soit f : Rn → R ∪ {+∞}. On appelle suite minimisante de f sur Rn toute suite
{xk } ⊂ Rn telle que f (xk ) −→ inf x∈Rn f (x).

Les résultats qui suivent nous donnent des conditions pour qu’une fonction soit inf-compacte.

Proposition 2.1.1 Si f : Rn → R ∪ {+∞} est s.c.i. propre alors

f est inf-compacte ⇐⇒ ∀{xk } ⊂ Rn , ∥xk ∥ −→ +∞ =⇒ f (xk ) −→ +∞.

6
Preuve : Supposons f non inf-compacte. Alors il existe λ tel que Sλ (f ) est non borné. c’est-à-
dire que pour tout k ∈ N, ∃xk ∈ Sλ (f ) avec ∥xk ∥ ≥ k. Mais alors ∥xk ∥ −→ +∞ et pourtant
lim sup f (xk ) ≤ λ.
Réciproquement supposons f inf-compacte et qu’il existe une suite {xk }, ∥xk ∥ −→ +∞ avec
lim sup f (xk ) ≤ λ < +∞. On a alors xk ∈ Sλ+1 (f ) pour k assez grand, ce qui est impossible
puisque Sλ+1 (f ) est borné. 

Définition 2.1.3 La fonction f est dite coercive si on a : f (x) −→ +∞ quand ∥x∥ −→ +∞.

On a alors le corollaire suivant :

Corollaire 2.1.1 Si f est s.c.i. propre et coercive alors f est inf-compacte.

Proposition 2.1.2 Si f est s.c.i. propre et fortement convexe alors f est inf-compacte.

Preuve : Soit µ le coefficient de forte convexité de f , x ∈ domf et

µ
g(x) = f (x) − ∥x − x∥2 .
2
g est alors convexe et sci.
On considère
D = {x ∈ Rn : ∥x − x∥ ≤ 1}.
On a
β = inf[g(x) : x ∈ D] = infn ge(x)
x∈R

où {
g(x) si x ∈ D
ge(x) =
+∞ sinon
ge est inf-compacte et donc on a g(x) ≥ β > −∞ pour tout x ∈ D.
Comme g est convexe on a
g(x + t(x − x)) − g(x)
g(x) + ≤ g(x) ∀ x ∈ Rn , ∀ t ∈]0, 1[.
t
Soit {xk } tel que ∥xk ∥ −→ +∞, on peut supposer que ∥xk − x∥ > 1. On a
g(x) + ∥xk − x∥(β − g(x)) ≤ g(xk ).
C’est-à-dire :
µ k
f (x) + ∥xk − x∥(β − g(x)) + ∥x − x∥2 ≤ f (xk ).
2
Pour k tendant vers l’infini, on a f (xk ) qui tend vers l’infini. 

En ce qui concerne l’unicité de la solution optimale on a le théorème ci-dessous.

Théorème 2.1.2 Si f est strictement convexe, alors le problème (P ) a au plus une solution
optimale globale.

Remarque 2.1.1 1) Comme la forte convexité implique la stricte convexité, on a la même conclu-
sion si on remplace dans le théorème précédent la stricte convexité par la forte convexité.
2) On sait qu’une fonction sci propre et fortement convexe est inf-compacte. Donc si f est sci
propre et fortement convexe, le problème (P ) admet une et une seule solution optimale globale.

7
2.2 Conditions d’optimalité
2.2.1 Conditions d’optimalité du premier ordre
Les conditions que nous donnons ici sont des conditions différentielles qui portent sur la dérivée
de la fonction à minimiser.
On définit :

Définition 2.2.1 Soit f : Rn → R une fonction différentiable. On dit que x∗ est un point station-
naire ou critique de f si ∇f (x∗ ) = 0.

On a le théorème

Théorème 2.2.1 (Condition nécessaire d’optimalité du premier ordre) Soit f : Rn → R

une fonction différentiable.
Si x∗ réalise un minimum local (global) de f sur Rn , alors ∇f (x∗ ) = 0.

Preuve : Soit x∗ réalisant un minimum local de f sur Rn . Le developpement de Taylor au voisinage

de x∗ donne : pour tout h ∈ Rn et t > 0 suffisamment petit,

f (x∗ + th) = f (x∗ ) + ⟨∇f (x∗ ), th⟩ + ∥th∥ε(th) ≥ f (x∗ ).

On obtient alors
⟨∇f (x∗ ), th⟩ + ∥th∥ε(th) ≥ 0.
En divisant par t > 0, et faisant tendre t vers 0, on obtient

⟨∇f (x∗ ), h⟩ ≥ 0

pour tout h ∈ Rn , Donc nécessairement

∇f (x∗ ) = 0.

Donc la condition est nécessaire. 

Remarque 2.2.1 1) Ce théorème n’a pas de sens si la fonction f n’est pas différentiable en x∗ .
2) Cette condition nécessaire du premier ordre permet de sélectionner un certain nombre de
candidats à être des minima locaux ou globaux. La réciproque est fausse. Un point critique n’est pas
nécessairement un minimum local (global). Ce peut être un minimum local ou global, un maximum
local ou global ou ni l’un ni l’autre. C’est dire que ce résultat n’est en général pas une condition
suffisante.

Dans le cas convexe, la condition nécessaire du premier ordre ci-dessus est suffisante.

Théorème 2.2.2 Soit f : Rn → R une fonction convexe et différentiable. Un point x∗ réalise un

minimum global de f sur Rn si et seulement si

∇f (x∗ ) = 0.

8
Preuve : On sait que la condition est nécessaire. Montrons à présent qu’elle est suffisante.
Soit x∗ un point tel que ∇f (x∗ ) = 0. Comme f est convexe alos, on a

f (x) ≥ f (x∗ ) + ⟨∇f (x∗ ), x − x∗ ⟩ ∀ x ∈ Rn .

Par hypothèse, on a ∇f (x∗ ) = 0 ; il vient alors que

f (x) ≥ f (x∗ ) ∀ x ∈ Rn .

Ce qui termine la démonstration. 

En l’absence de convexité de f , une information sur le comportement de ∇f au voisinage du
point x∗ considéré permet dans certains cas d’assurer que x∗ est un minimum local (strict même)
de f .

Théorème 2.2.3 Soit x∗ ∈ Rn un point en lequel f est continue et supposons qu’il existe un
voisinage ouvert V de x∗ tel que :
1) f est différentiable sur V \ {x∗ }
2) ⟨∇f (x), x − x∗ ⟩ ≥ 0 (respectivement > 0) ∀ x ∈ V \ {x∗ }.
Alors x∗ est un minimum local (respectivement minimum local strict) de f .

Preuve : On peut supposer sans perte de généralité que V est une boule ouverte de centre x∗ et
rayon r. Soit x ∈ V \{x∗ } et considérons la fonction φ : [0, 1] → R telle que φ(t) = f (x∗ +t(x−x∗ )).
La fonction φ est continue sur [0, 1], dérivable sur ]0, 1[ avec

φ′ (t) = ⟨∇f (x∗ + t(x − x∗ )); x − x∗ ⟩ ∀ t ∈ ]0, 1[ .

Le théorème des accroissement finis appliqué à [0, 1] implique que : ∃ t0 ∈ ]0, 1[ tel que :

φ(1) − φ(0) = φ′ (t0 ) ⇐⇒ f (x) − f (x∗ ) = ⟨∇f (x∗ + t0 (x − x∗ )); x − x∗ ⟩.

Il est clair que x0 = x∗ + t0 (x − x∗ ) ∈ V \ {x∗ }, x − x∗ = 1

t0
(x0 − x∗ ),

1
f (x) − f (x∗ ) = ⟨∇f (x0 ); x0 − x∗ ⟩.
t0
La condition 2) nous permet alors de conclure. 

2 4
Exemple 2.2.1 Soit f (x) = x13 + x23 + 1.
Cette fonction n’est pas différentiable en (0, 0) mais la différentiabilité en (0, 0) n’est pas exigée
pour appliquer le théorème ci-dessus.
On a en effet f qui est différentiable sur R2 \ {(0, 0)} et
2 2 4 4
⟨∇f (x), x − 0⟩ = x13 + x23 > 0 ∀ x ∈ R2 \ {(0, 0)}.
3 3
Alors le théorème nous permet de conclure que (0, 0) est un minimum strict de f sur R2 .

9
2.2.2 Conditions d’optimalité du second ordre
Théorème 2.2.4 (Conditions nécessaires d’optimalité du second ordre) Soit f : Rn →
R une fonction deux fois différentiable sur Rn .
Si x∗ est un minimum local (global) de f sur Rn alors on a :
1) ∇f (x∗ ) = 0,
2) ∇2 f (x∗ ) est semi défini positif.

Preuve : Soit x∗ un minimum local de f sur Rn . On sait que la condition 1) est satisfaite. Il reste
à montrer la condition 2). Par définition du minimum local, il existe un voisinage V de x∗ dans
Rn tel que f (x) ≥ f (x∗ ) pour tout x ∈ V .
Soit h ∈ Rn . En utilisant le developpement de Taylor au voisinage de x∗ , à l’ordre deux et la
condition 1), on a : pour t suffisamment petit,

t2 2
f (x∗ + th) = f (x∗ ) + ⟨∇ f (x∗ )h, h⟩ + t2 ε(t),
2
avec ε continue et limt→0 ε(t) = 0.
Pour t ̸= 0 suffisamment petit de sorte que x∗ + th ∈ V , on a :

f (x∗ + th) − f (x∗ ) 1 2

0≤ = ⟨∇ f (x∗ )h, h⟩ + ε(t).
t2 2
En passant à la limite, t tendant 0, on obtient : ⟨∇2 f (x∗ )h, h⟩ ≥ 0. 
On a aussi une condition suffisante d’optimalité.

Théorème 2.2.5 (Condition suffisante d’optimalité du second ordre) Soit f : Rn → R

une fonction deux fois différentiable sur Rn .
Si x∗ est tel que :
1) ∇f (x∗ ) = 0,
2) ∇2 f (x∗ ) est défini positif,
alors x∗ est un minimum local strict de f .

Preuve : La matrice étant définie positive, il existe λ > 0 tel que

∀ h ∈ Rn , ⟨∇2 f (x∗ )h, h⟩ ≥ λ∥h∥2 .

D’après la formule de Taylor on a

1
f (x) − f (x∗ ) = ⟨∇f (x∗ ), x − x∗ ⟩ + ⟨∇2 f (x∗ )(x − x∗ ), x − x∗ ⟩ + ∥x − x∗ ∥2 ε(x − x∗ )
2
avec ε continue et limx→x∗ ε(x − x∗ ) = 0.
On a alors ( )
∗ ∗ 2 λ ∗
f (x) − f (x ) ≥ ∥x − x ∥ + ε(x − x )
2
Pour x suffisamment proche de x∗ , λ
2
+ ε(x − x∗ ) est du signe de λ c’est-à-dire strictement
positif. 

10
2.3 Méthodes numériques
Dans cette partie nous nous intéressons aux méthodes numériques pour résoudre le problème :

α = infn f (x) (P )
x∈R

où f est une fonction définie et différentiable sur Rn et à valeurs dans R.

Les principales méthodes de résolution connues ne permettent pas la détermination d’un mi-
nimum global. Il faut alors parfois se contenter d’optimum locaux.
Les algorithmes les plus utilisés sont des procédures itératives où l’on engendre une suite de
points x0 , x1 , · · · , xk , · · · convergeant vers un optimum local.

2.3.1 Algorithmes et vitesse de convergence

Définition 2.3.1 Un algorithme est défini par une application A de Rn dans Rn permettant la
génération d’une suite d’éléments de Rn par la formule :
{
x0 ∈ Rn donné k := 0 Etape d’initialisation
x k+1
= A(x )k
k := k + 1 Itération k

Ecrire un algorithme c’est se donner une suite {xk } de Rn .

Etudier la convergence de cet algorithme c’est étudier la convergence de la suite {xk }.

Définition 2.3.2 On dit que l’algorithme A converge si la suite {xk } engendrée par l’algorithme
converge vers une limite x∗ .
La convergence est dite locale si elle n’a lieu que pour des points de départ x0 dans un voisinage
de x∗ . Dans le cas contraire la convergence est globale.

Définition 2.3.3 Soit {xk } une suite de limite x∗ définie par la donnée d’un algorithme conver-
geant A. On dit que la convergence de A est :
- linéaire si l’erreur ek = ∥xk − x∗ ∥ décroit linéairement i.e

∃ C ∈ [0, 1[, ∃ k0 : ∀ k ≥ k0 , ek+1 ≤ Cek .

- superlinéaire si l’erreur ek = ∥xk − x∗ ∥ décroit de la manière suivante : ek+1 ≤ αk ek où αk est

une suite positive qui converge vers 0.
Si αk est une suite géométrique, la convergence de l’algorithme est dite géométrique.
- superlinéaire d’ordre p > 1 si l’erreur ek = ∥xk − x∗ ∥ décroit de la manière suivante :

∃ C ≥ 0, ∃ k0 : ∀ k ≥ k0 , ek+1 ≤ C[ek ]p .
Dans le cas p = 2, la convergence de l’algorithme est dite quadratique.

11
2.3.2 Méthodes de descente
A chaque étape k, xk+1 est défini par :

xk+1 = xk + λk dk

où dk est une direction de déplacement et λk le pas de déplacement.

La plupart des méthodes numériques usuelles sont des méthodes de descente c’est-à-dire que
la direction de deplacement à chaque étape xk est une direction de descente pour la fonction en
ce point.

Définition 2.3.4 On dit qu’une direction d est une direction de descente pour f en x, si

∃ α > 0 : f (x + αd) < f (x) ∀ α ∈]0, α[.

On montre facilement que :

Proposition 2.3.1 Soit f différentiable en x, si d est telle que ⟨∇f (x), d⟩ < 0 alors d est une
direction de descente pour f en x.

Corollaire 2.3.1 Soit f différentiable en x. Si ∇f (x) ̸= 0, alors d = −∇f (x) est une direction
de descente pour f en x.

Le principe des méthode à directions de descente est le suivant :

0) Choix d’un itéré initial x0 ∈ Rn ;
Initialisation : k := 0 ;
1) Arrêt de l’algorithme si test d’arrêt vérifié ;
2) Choix d’une direction de descente dk ;
3) Détermination d’un pas de déplacement λk > 0 le long de dk de manière à ”faire décroı̂tre f
suffisamment” ;
4) xk+1 = xk + λk dk , k := k + 1 et aller en 1.

Méthodes du gradient
Il s’agit d’une famille de méthodes itératives qui s’appliquent à des fonctions différentiables et
qui utilisent l’opposé du gradient comme direction de déplacement. L’algorithme du gradient à
pas optimal on dit aussi de la plus forte pente est le suivant :

a) Algorithme du gradient à pas optimal

0) Choix d’un itéré initial x0 ∈ Rn initialisation : k := 0 ;
1) Arrêt de l’algorithme si test d’arrêt vérifié ;
2) Prendre dk = −∇f (xk ) ;
3) Déterminer λk > 0 tel que f (xk + λk dk ) = minλ≥0 f (xk + λdk ) ;
4) xk+1 = xk + λk dk , k := k + 1 et aller en 1.
Le test d’arrêt peut être par exemple :
• le gradient est très petit : ∥∇f (xk )∥ ≤ ε, où ε est un paramètre donné ;
• la suite {xk } est ”presque” stationnaire : |f (xk+1 ) − f (xk )| ≤ ε, (ε donné).
On peut aussi exiger que l’un de ces tests soit vérifié sur plusieurs itérations ou que plusieurs
tests soient satisfaits simultanément.

12
 On montre que dans la méthode du gradient à pas optimal, les directions de déplacement
successives sont orthogonales : ⟨∇f (xk+1 ), ∇f (xk )⟩ = 0.
On a le résultat de convergence suivant :

Théorème 2.3.1 Si la fonction f est de classe C 1 et coercive, alors pour tout point de départ x0 ,
la méthode du gradient à pas optimal (avec recherche linéaire exacte ou approchée) converge vers
un point stationnaire de f .

On remarque que dans la pratique, pour certains types de fonctions, la convergence est très
lente, par exemple, les fonctions mal conditionnées du type vallée étroite et allongée.
Il existe des techniques d’accélération de la convergence.

b) Algorithme du gradient à pas optimal accéléré

La méthode du gradient à pas optimal accéléré est une méthode de descente qui s’appuie sur
la méthode de la plus forte pente.
Soit p un entier fixé. A partir d’un point xk , on effectue p itérations de la méthode de la plus
forte pente ; on obtinet un point y k et on pose dk = y k − xk . Le point xk+1 est le point où la
fonction f (xk + λdk ) admet un minimum pour λ > 0.
Cette méthode peut gagner beaucoup de temps par rapport à la méthode précédente.

2.3.3 Méthodes de directions conjuguées

Il s’agit de méthodes itératives qui, appliquées à une fonction quadratique de n variables
conduisent à l’optimum en n étapes au plus.

Définition 2.3.5 Soit A une matrice carrée d’ordre n symétrique définie positive.
On dit que les vecteurs x et y de Rn sont conjugués par rapport à A ou encore A-conjugués
s’ils vérifient xT Ay = 0.

La matrice A étant symétrique définie positive, la forme bilinéaire a(x, y) = xT Ay définit un

produit scalaire et la relation xT Ay = 0 traduit l’orthogonalité des vecteurs x et y par ce produit
scalaire.

Théorème 2.3.2 Si {d0 , · · · , dk } sont des directions 2 à 2 conjuguées par rapport à A, soit
⟨di , Adj ⟩ = 0 ∀ i, j ∈ {0, · · · , k}, i ̸= j alors elles sont linéairement indépendantes.

Définition 2.3.6 Soit {d0 , · · · , dk } une famille de vecteurs A-conjugués. On appelle méthode
de directions conjuguées la méthode
{
x0 donné
xk+1 = xk + λk dk , λk optimal

13
 a) Algorithme du gradient conjugué : cas des fonctions quadratiques
On considère la fonction quadratique
1
q(x) = ⟨Ax, x⟩ + ⟨b, x⟩ + c
2
où A est une matrice carrée d’ordre n symétrique définie positive, b ∈ Rn et c ∈ R.
La méthode consiste à partir d’un point x0 , à minimiser q suivant n directions d0 , d1 , · · · , dn−1
mutuellement conjuguées par rapport à A.
Soient n telles directions : d0 , d1 , · · · , dn−1 .
Ayant déterminé xk , le point xk+1 est le point : xk+1 = xk + λk dk où λk est chosi de façon à
minimiser q(xk + λdk ) par rapport à λ. On a donc ⟨dk , ∇q(xk + λk dk )⟩ = 0 ou encore ⟨dk , A(xk +
λk dk ) + b⟩ = 0 d’où l’on déduit : λk = − ⟨d⟨Ad
k ,Axk +b⟩
k ,dk ⟩ .

On montre que

Lemme 2.3.1 Si d0 , d1 , · · · , dk−1 sont mutuellement conjuguées par rapport à A, alors on a pour
tout i < k la relation : ⟨di , ∇q(xk )⟩ = 0.

Preuve : On a en effet
⟨di , ∇q(xk )⟩ = ⟨di , Axk + b⟩
∑
= ⟨di , A(xi + k−1 j
j=i λj d ) + b⟩
= ⟨di , Axi + b⟩ + λi ⟨di , Adi ⟩
= 0 d’après la valeur de λi calculée ci-dessus
D’où le résultat. 

Théorème 2.3.3 Le point xn est l’optimum de q(x) sur Rn .

Preuve : Les directions d0 , d1 , · · · , dn−1 étant mutuellement conjuguées, elles forment une base
de Rn . D’après le lemme , ∇q(xn ) = 0, ce qui démontre le théorème. 
La méthode de Fletcher et Reeves engendre au fur et à mesure les directions dk . A chaque
étape k, la direction dk est obtenue comme combinaison linéaire du gradient de q en xk et de la
direction précédente dk−1 , les coefficients étant choisis de telle manière que dk soit A-conjuguée
avec toutes les directions précédentes.
Algorithme de Fletcher et Reeves
On considère dans cet algorithme g k = ∇q(xk ) = Axk + b
• Choisir un point initial x0 ∈ Rn et poser d0 = −g 0 ;
• Pour k variant de 0 à n faire :
⟨dk ,g k ⟩
◦ λk = − ⟨Adk ,dk ⟩
◦ xk+1 = xk + λk dk
◦ βk = − ⟨g⟨Adk,Ad
k+1 k⟩

,dk ⟩
;
◦d k+1
= −g + βk dk .
k

(on pourra remarquer l’égalité suivante : ⟨dk , g k ⟩ = −∥g k ∥2 ).

La convergence de l’algorithme est assurée par le fait que les directions d0 , d1 , · · · , dn−1 sont
mutuellement conjuguées. Montrons cela par récurrence. pour cela, soit k compris entre 0 et n − 2 ;
on suppose que les directions d0 , d1 , · · · , dk sont mutuellement conjuguées. On a alors pour k + 1 :
⟨dk , Adk+1 ⟩ = ⟨dk , A(−g k+1 + βk dk ⟩
= −⟨dk , Ag k+1 ⟩ + βk ⟨dk , Adk ⟩ = 0 d’après le choix de βk

14
Pour i < k,
⟨dk+1 , Adi ⟩ = −⟨g k+1 , Adi ⟩ + βk − ⟨dk , Adi ⟩ = −⟨g k+1 , Adi ⟩.
Or ( )
i xi+1 − xi Axi+1 − Axi g i+1 − g i
Ad = A = = .
λi λi λi
D’autre part, g i+1 = −di+1 + βi di et g i = −di + βi−1 di−1 .
D’après le lemme, g i+1 est orthogonal à di+1 , di et di−1 : Adi étant combinaison linéaire de ces
trois vecteurs, ⟨g k+1 , Adi ⟩ = 0, ce qui montre l’égalité ⟨dk+1 , Adi ⟩. 
Pour terminer nous montrons une formule qui nous sera très utile dans le paragraphe suivant.
∥g k+1 ∥2
Proposition 2.3.2 On a βk = ∥g k ∥2
.

Preuve : On a g k+1 − g k = A(xk+1 − xk ) = λk Adk .

D’où ⟨g k+1 , Adk ⟩ = ⟨g ,gλk −g ⟩ .
k+1 k+1 k

Comme g k = −dk + βk−1 dk−1 , le lemme montre l’égalité ⟨g k+1 , g k ⟩ = 0

D’où : βk = λ1k ⟨g⟨dk ,Ad
k+1 ,g k+1 ⟩
= − ⟨g ⟨gk ,d
k+1 ,g k+1 ⟩
k⟩ k⟩ .
Or ⟨g , d ⟩ = ⟨g , −g + βk−1 d ⟩ = −⟨g k , g k ⟩ d’après le lemme.
k k k k k−1

On en déduit le résultat : βk = ∥g∥gk ∥2∥ .

k+1 2


b) Algorithme du gradient conjugué : cas des fonctions quelconques

L’algorithme de Fletcher et Reeves pour une fonction quelconque est le suivant :
• Choisir un point initial x0 ∈ Rn , poser d0 = −∇f (x0 ) et k = 0 ;
• repéter :
◦ choisir λk minimisant f (xk + λdk ), par rapport à λ
◦ xk+1 = xk + λk dk
◦ βk = ∥g∥gk ∥2∥
k+1 2

◦ dk+1 = −∇f (xk+1 ) + βk dk ◦ k := k + 1.

Cette méthode a deux avantages : elle nécessite le stockage de très peu d’informations et sa
vitesse de convergence est très supérieure à celle des algorithmes de gradient classiques.

2.3.4 Méthode de relaxation

Cette méthode consiste à faire le choix suivant pour les directions de descente :

d0 = e1 , d1 = e2 , · · · , dn−1 = en

ensuite
dn = e1 , dn+1 = e2 , · · · , d2n−1 = en
et ainsi de suite ... On rappelle que {e1 , e2 , · · · , en } sont les vecteurs de la base canonique de Rn .
Donc en général on a
dk = el
si et seulement si l est le reste de la division de k + 1 par n.
On prend ensuite les facteurs λk dans R tels que

f (xk + λk dk ) = min f (xk + λdk ) ∀ k ∈ R.

λ∈R

15
(en supposant que ces minimum existent).
Finalement on pose :
xk+1 = xk + λk dk .
On peut écrire cet algorithme de la manière équivalente suivante :
On suppose connu le vecteur xk = (xk1 , · · · , xkn )T et on calcule xk+1 = (xk+1
1 , · · · , xn ) en n
k+1 T

pas successifs par les formules suivantes :

1 , x2 , · · · , xn ) = miny∈R f (y, x2 , · · · , xn )
f (xk+1 k k k k

f (x1 , x2 , xk3 , · · · , xkn ) = miny∈R f (x1 , y, xk3 , · · · , xkn )

k+1 k+1 k+1

1 , · · · , xn ) = miny∈R f (x1 , · · · , xn−1 , y)

· · · f (xk+1 k+1 k+1 k+1

On a l’algorithme de convergence suivant :

Théorème 2.3.4 Si f est elliptique, alors la méthode de relaxation est bien définie et elle converge
(c’est-à-dire, pour tout point x0 ∈ Rn , la suite {xk } construite par cet algorithme converge vers
l’unique point de minimum de f ).

2.3.5 Méthode de Newton

La méthode de Newton permet de construire un algorithme permettant de résoudre le système
d’équation non linéaire
g(x) = 0
où g : Rn → Rn est différentiable : on se donne x0 ∈ Rn et on fait les itérations

xk+1 = xk − [g ′ (xk )]−1 g(xk ) (2.1)

où g ′ (x) est la dérivée (ou jacobienne) de g au point x.

L’application de cette méthode au problème d’optimisation

α = minn f (x) (P )
x∈R

consiste à l’utiliser pour résoudre le système d’optimalité du problème (P ), c’est-à-dire que l’on
pose g(x) = ∇f (x) dans (2.1). Cela suppose donc que f est deux fois différentiable et que l’on
sait calculer ses dérivées secondes. On obtient les itérations

xk+1 = xk − [∇2 f (xk )]−1 ∇f (xk ) (2.2)

On remarque qu’il est nécessaire qu’en xk , ∇2 f (xk ) soit inversible : ce qui est le cas si ∇2 f (xk )
est défini positif.
La méthode de Newton est intéressante car sa convergence est quadratique au voisinage de la
solution x⋆ si ∇2 f (x⋆ ) est défini positif c’est-à-dire que l’on a

∥xk+1 − x∗ ∥ ≤ γ∥xk − x∗ ∥2 , γ > 0.

Mais cette convergence n’est assurée que si x0 est suffisamment proche de x∗ , ce qui limite l’intérêt.
On pourra éventuellement appliquer d’abord une autre méthode pour s’approcher de x⋆ , puis
appliquer la méthode de Newton.
Pour améliorer la précision de la méthode de Newton, on peut penser à lui ajouter une phase
de recherche linéaire dans la direction dk = −[∇2 f (xk )]−1 ∇f (xk ).

16
 Cela est possible uniquement si dk est une direction de descente pour f en xk , soit

⟨∇f (xk ), dk ⟩ = −⟨∇f (xk ), [∇2 f (xk )]−1 ∇f (xk )⟩ < 0

ce qui sera le cas si ∇2 f (xk ) est une matrice définie positive. L’algorithme s’écrit alors :
0) Choix d’un itéré initial x0 ∈ Rn , initialisation : k := 0 ;
1) Arrêt de l’algorithme si test d’arrêt vérifié ;
2) Prendre dk = −[∇2 f (xk )]−1 ∇f (xk ) ;
3) Déterminer λk > 0 tel que f (xk + λk dk ) = minλ≥0 f (xk + λdk ) ;
4) xk+1 = xk + λk dk , k := k + 1 et aller en 1.

17
Chapitre 3

Optimisation avec contraintes

Dans ce chapitre on s’intéresse au problème

α = inf f (x) (P )
x∈C

où C est une partie de Rn et f : Rn → R ∪ {+∞}.

3.1 Résultats d’existence et d’unicité

On considère d’abord les définitions suivantes.

Définition 3.1.1 la fonction f est p-coercive sur C si

f (x)
lim ∥x∥ p = +∞

∥x∥ → +∞ .
x∈C

Si p = 0 on dit que la fonction f est coercive.

Définition 3.1.2 On appelle suite minimisante de f sur C toute suite {xk } de C telle

lim f (xk ) = inf f (x).

k→+∞ x∈C

Définition 3.1.3 On dit que f est bornée inférieurement sur C si

inf f (x) > −∞.

x∈C

On a le résultat d’existence suivant.

Théorème 3.1.1 Si f est inf compacte, propre, C fermé et C ∩ domf ̸= ∅ alors le problème (P )
admet au moins une solution optimale et α > −∞.

Preuve :
Soit {xk } une suite minimisante de f sur C.
La suite {xk } est bornée. En effet si ça n’était pas le cas, il existerait une sous suite {xkl } de {xk }
telle que ∥xkl ∥ −→ +∞. Comme f est inf compacte, cela impliquerait que α = liml f (xkl ) = +∞.
Ce qui est impossible car f est finie en au moins un point de C (C ∩ domf ̸= ∅).

18
 La suite {xk } étant bornée, il existe une sous suite {xkl } de {xk } qui converge vers un point x̄
de C car C est fermé.
Comme f est inf compacte, elle est sci. Alors on a

α = lim f (xkl ) ≥ f (lim xkl ) = f (x̄).

l l

Donc α = f (x̄) ∈ R. 
On en déduit les résultats suivants :

Corollaire 3.1.1 Si
1) C est fermé et il existe un point de C en lequel f est finie,
2) f est sci sur Rn ,
3) f est coercive sur C,
Alors f est bornée inférieurement sur C et (P ) admet au moins une solution optimale, c’est-
à-dire qu’il existe x̄ ∈ C tel que f (x̄) = inf x∈C f (x).

Corollaire 3.1.2 Si f est sci propre, C fermé, C ∩ domf ̸= ∅, et si f (xk ) −→ +∞ chaque fois
que xk ∈ C, ∥xk ∥ → +∞, alors (P ) admet au moins une solution optimale et α > −∞.

Dans le cas où la fonction f possède des propriétés de convexité, on a les propriétés suivantes

Proposition 3.1.1 Soit

Sopt = {x ∈ C : f (x) = α}
l’ensemble des solutions optimales de (P ).
Si C est convexe non vide et f concave sur C alors
• ou bien Sopt ⊂ Fr(C)
• ou bien f est constante sur C.

Preuve : Supposons f non constante sur C et Sopt ̸= ∅.

Si Sopt ∩ int(C) ̸= ∅, alors soit x∗ ∈ int(C) ∩ Sopt . On a alors f (x∗ ) ≤ f (x) pour tout x ∈ C.
Comme la fonction f est non constante sur C, il existe x̄ ∈ C tel que f (x̄) > f (x∗ ) = α.
On a x∗ ∈ int(C), alors il existe x̃ ∈ C, et t ∈]0, 1[ tels que x∗ = tx̄ + (1 − t)x̃.
La fonction f étant concave, on a α = f (x∗ ) ≥ tf (x̄) + (1 − t)f (x̃) > tα + (1 − t)α = α Ce qui
est contradictoire. Donc Sopt ∩ int(C) = ∅ par suite Sopt ⊂ Fr(C). 

Proposition 3.1.2 Si C est convexe compact non vide et f continue et concave sur C, et si
C ∩ domf ̸= ∅, alors l’ensemble des solutions optimale de (P ) est non vide et contient des points
extrêmes de C.

Preuve : Comme C est compact, f continue et C ∩ domf ̸= ∅, alors (P ) admet au moins une
solution optimale.
On sait que tout convexe compact est égal à l’enveloppe convexe de ses points extrêmes.
Soit x∗ est une solution optimale. Comme x∗ ∈ C alors il existe ai , i = 1, · · · , p des points
extrêmes de C tels que
∑p
∑p
∗
x = λi a avec λi ≥ 0 et
i
λi = 1.
i=1 i=1

19
 Comme f est concave sur C, on a
∑
p
f (x∗ ) ≥ λi f (ai ).
i=1

Or on a f (ai ) ≥ f (x∗ ). Ce qui implique que pour tout i ∈ {1, · · · , p}, on a f (ai ) = f (x∗ ) et par
suite ai est une solution optimale de (P ). 

Proposition 3.1.3 Si C est un polyèdre convexe non vide et f concave et continue sur C et si
α > −∞ alors l’ensemble des solutions optimales de (P ) est non vide et contient au moins un
sommet de C.

Preuve : Comme C est un polyèdre convexe, on peut écrire C = P + D où P est un polytope et
∑
q
D = {d = µj dj , dj ∈ Rn , µj ≥ 0}.
j=1

Soit x̃ fixé, x̃ ∈ P . On a
[ ]
α ≤ inf [f (x̃ + d)] = inf inf f (x̃ + td) .
d∈D d∈D t≥0

Pour tout d ∈ D ; f étant concave et minorée sur l’ensemble {x = x̃ + td : t ≥ 0}, on a

inf [f (x̃ + td)] = f (x̃).

t≥0

En effet, raisonons par l’absurde, sinon il existerait t̄ > 0 tel que

f (x̃ + t̄d) < f (x̃).

Mais alors pour tout t > t̄ on a

f (x̃ + td) − f (x̃) f (x̃ + t̄d) − f (x̃)
≤
t t̄
et donc f (x̃ + td) −→ −∞ si t → +∞ ce qui est impossible car α > −∞.
Il s’ensuit que
inf [f (x̃ + d)] = f (x̃), ∀x̃ ∈ P.
d∈D

Par suite
inf f (x) = inf f (x).
x∈C x∈P

Comme P est un polytope donc compact, le minimum est atteint et il l’est en un des points
extremaux du polytope. 

On a le résultat sur l’unicité de la solution optimale.

Théorème 3.1.2 Si C est convexe et f strictement convexe sur C alors (P ) admet au plus une
solution optimale.

La démonstration est immédiate.

20
3.2 Conditions d’optimalité
3.2.1 Généralités
Dans cette partie on donne des conditions d’optimalité des fonctions différentiables à partir
des cônes tangents. Tout d’abord on a la condition nécessaire d’optimalité suivante.

Théorème 3.2.1 Supposons f différentiable en x̄ ∈ C. Si x̄ est un minimum local de f sur C

alors on a :
⟨∇f (x̄), d⟩ ≥ 0 ∀ d ∈ T (C, x̄).
Preuve : Supposons qu’il existe V ∈ V(x̄) tel que

f (x) ≥ f (x̄) ∀ x ∈ C ∩ V.

Si
∃d ∈ T (C, x̄) = T (C ∩ V, x̄)
tel que ⟨∇f (x̄), d⟩ < 0, alors d ̸= 0, on peut donc sans perdre de généralités supposer que ∥d∥ = 1.
Par défintion du cône tangent, il existe une suite {dk } de Rn tendant vers d, une suite {λk } de
R∗+ tendant vers 0 telles que

xk = x̄ + λk dk ∈ C ∩ V ∀ k ∈ N.

On a alors xk −→ x̄ et donc
f (xk ) − f (x̄) − ⟨∇f (x̄), xk − x̄⟩
lim = 0. (3.1)
k→+∞ ∥xk − x̄∥

Comme xk ∈ C ∩ V , on a f (xk ) ≥ f (x̄) pour tout k. Donc

f (xk ) − f (x̄)
≥ 0. (3.2)
∥xk − x̄∥
Mais comme
⟨∇f (x̄), xk − x̄⟩
lim = ⟨∇f (x̄), d⟩,
k→+∞ ∥xk − x̄∥
alors d’après la condition (3.1), on a

f (xk ) − f (x̄)
lim = ⟨∇f (x̄), d⟩ < 0.
k→+∞ ∥xk − x̄∥
Ce qui est en contradiction avec (3.2). Donc pour tout d ∈ T (C, x̄), on a ⟨∇f (x̄), d⟩ ≥ 0. D’où le
résulatat. 
On en déduit le corollaire suivant.

Corollaire 3.2.1 Si f est différentiable en x̄ ∈ int(C), alors si x̄ est un minimum local de f sur
C, on a ∇f (x̄) = 0.
Preuve : D’après le théorème ci-dessus, on a ⟨∇f (x̄), d⟩ ≥ 0 pour tout d ∈ T (C, x̄). Mais comme
x̄ ∈ int(C), T (C, x̄) = Rn . Il vient alors que ⟨∇f (x̄), d⟩ = 0 pour tout d ∈ Rn . Donc ∇f (x̄) = 0.
Cette condition nécessaire d’optimalité est suffisante dans le cas convexe. Mais avant on
considère le résultat suivant.

21
Proposition 3.2.1 Si C est convexe et f différentiable en x̄ ∈ C, on a les équivalences suivantes :
i) ⟨∇f (x̄), d⟩ ≥ 0 ∀ d ∈ T (C, x̄)
ii) ⟨∇f (x̄), x − x̄⟩ ≥ 0 ∀ x ∈ C.

Preuve : Comme C est convexe on a T (C, x̄) = R∗+ (C − x̄). Donc pour tout x ∈ C, on a
x − x̄ ∈ T (C, x̄). Par suite ⟨∇f (x̄), x − x̄⟩ ≥ 0 ∀ x ∈ C.
Réciproquement supposons que ⟨∇f (x̄), x − x̄⟩ ≥ 0 ∀ x ∈ C et soit d ∈ T (C, x̄). Alors d =
limk dk avec dk ∈ R∗+ (C − x̄) pour tout k. On peut donc écrire dk = λk (xk − x̄) où λk > 0 et xk ∈ C
pour tout k. Par hypothèse, on a ⟨∇f (x̄), x − x̄⟩ ≥ 0 ∀ x ∈ C. Donc on a ⟨∇f (x̄), xk − x̄⟩ ≥ 0
∀ k. Il s’ensuit alors que ⟨∇f (x̄), λk (xk − x̄)⟩ ≥ 0 ∀ k et donc ⟨∇f (x̄), dk ⟩ ≥ 0 ∀ k. Par passage à
la limite, on obtient ⟨∇f (x̄), d⟩ ≥ 0. 

Proposition 3.2.2 Si C est convexe et f convexe sur C et différentiable en x̄ ∈ C alors x̄ réalise

un minimum global de f sur C si et seulement si ⟨∇f (x̄), x − x̄⟩ ≥ 0 ∀ x ∈ C.

Preuve : La condition est nécessaire d’après le théorème (3.2.1) et la proposition (3.2.1).

Réciproquement, comme f est convexe et différentiable en x̄, on a

f (x) ≥ f (x̄) + ⟨∇f (x̄), x − x̄⟩ ≥ f (x̄) ∀ x ∈ C.

C’est-à-dire que x̄ réalise un minimum global de f sur C. 

3.2.2 Cas des contraintes d’égalité

On suppose ici que
C = {x ∈ Rn : hj (x) = 0, j = 1, · · · , q}
où les fonctions hj , j = 1, · · · , q sont définies sur Rn et à valeurs dans R ∪ {+∞}.
Le résultat ci-dessous donne une expression simple du cône tangent.

Théorème 3.2.2 On suppose que les fonctions hj pour tout j = 1, · · · , q sont de classe C 1 dans
un voisinage de x∗ ∈ C et que le système {∇hj (x∗ ), j = 1, · · · , q} est libre. Alors

T (C, x∗ ) = {d ∈ Rn : ⟨∇hj (x∗ ), d⟩ = 0 ∀ j = 1, · · · , q} .

Preuve : Posons

L(C, x∗ ) = {d ∈ Rn : ⟨∇hj (x∗ ), d⟩ = 0 ∀ j = 1, · · · , q} .

Le problème revient à montrer que T (C, x∗ ) = L(C, x∗ ).

Soit d ∈ T (C, x∗ ). Si d = 0 alors d ∈ L(C, x∗ ).
Supposons d ̸= 0. On peut donc considérer que ∥d∥ = 1.
Comme d ∈ T (C, x∗ ) et par définition du cône tangent,

∃ {dk } ⊂ Rn dk −→ d,
: xk = x∗ + tk dk ∈ C ∀ k ∈ N.
∃ {tk } ⊂ R∗+ tk −→ 0,

On a alors pour tout j, hj (xk ) = 0 pour tout k.

On a aussi pour tout j, hj (x∗ ) = 0.
Comme xk −→ x∗ on a pour tout j,

22
 hj (xk ) − hj (x∗ )
0= −→ ⟨∇hj (x∗ ), d⟩.
tk ∥d ∥
k

Donc on a pour tout j,

⟨∇hj (x∗ ), d⟩ = 0
C’est-à-dire que d ∈ L(C, x∗ ). Par suite, on a l’inclusion T (C, x∗ ) ⊂ L(C, x∗ ).
Réciproquement, soit d ∈ L(C, x∗ ). On considère
h : Rn −→ Rq
x 7−→ h(x) = (h1 (x), · · · , hq (x))
et
r : Rq × R −→ Rq [ ]
(u, t) 7−→ r(u, t) = h x∗ + [h′ (x∗ )]T u + td
On a r(0, 0) = h(x∗ ) = 0, ru′ (0, 0) = [h′ (x∗ )][h′ (x∗ )]T ∈ Mq (R) qui est inversible car les lignes
de la matrice [h′ (x∗ )] sont linéairement independantes. On a aussi rt′ (0, 0) = [h′ (x∗ )]d = 0, car
d ∈ L(C, x∗ ). Comme r est de classe C 1 dans un voisinage de (0, 0), alors d’après le théorème des
fonctions implicites, il existe V × W ∈ V(0Rq , 0R ), V ⊂ Rq , W ⊂ R, il existe θ : W −→ V de classe
C 1 tels que :
i) r(θ(t), t) = r(0, 0),
ii) θ(t) est l’unique solution dans V de l’équation r(x, t) = 0,
iii) ru′ (θ(t), t)θ′ (t) + rt′ (θ(t), t) = 0, ∀ t ∈ W.
D’après i) on a θ(0) = 0.
En utilisant iii), et le fait que
ru′ (0, 0) = [h′ (x∗ )][h′ (x∗ )]T et rt′ (0, 0) = [h′ (x∗ )]d = 0,
on obtient
[h′ (x∗ )][h′ (x∗ )]T θ′ (0) = 0.
On tire alors θ′ (0) = 0.
Soit {tk } ⊂ R∗+ tk tendant vers 0. Il existe alors un rang k1 tel que pour tout k ≥ k1 , tk ∈ W .
Donc [ ]
r(θ(tk ), tk ) = h x∗ + [h′ (x∗ )]T θ(tk ) + tk d = 0.
Posons
xk = x∗ + [h′ (x∗ )]T θ(tk ) + tk d pour k ≥ k1 .
On a alors xk = x∗ + tk dk avec dk = [h′ (x∗ )]T θ(ttkk ) + d.
Comme θ′ (0) = θ(0) = 0, on a θ(ttkk ) −→ 0 et donc dk −→ d. On a aussi h(xk ) = 0, pour tout
k ≥ k1 , c’est-à-dire que pour tout j, hj (xk ) = 0 et cela pour tout k ≥ k1 . Il s’ensuit alors que
d ∈ T (C, x∗ ). d’où le théorème 

On a à présent les conditions nécessaires d’optimalité.

Théorème 3.2.3 (Conditions Nécessaires d’optimalité du premier ordre) On suppose que
f est différentiable en x∗ ∈ C, que les fonctions hj , j = 1, · · · , q sont de classe C 1 dans un voisi-
nage de x∗ ∈ C et que le système {∇hj (x∗ ), j = 1, · · · , q} est libre. Alors une condition nécessaire
pour que x∗ soit une solution optimale locale de (P ) est que :
∑
q
∗ ∗
∃!µ ∈ R q
tel que ∇f (x ) + µ∗j ∇hj (x∗ ) = 0.
j=1

23
(le vecteur µ∗ est appelé vecteur multiplicateur de Lagrange)

Preuve : On sait qu’une condition nécessaire pour que x∗ soit une solution optimale locale de
(P ) est que :
⟨∇f (x∗ ), d⟩ ≥ 0 ∀ d ∈ T (C, x∗ ).
C’est-à-dire que : { q }
∑
−∇f (x∗ ) ∈ T (C, x∗ )◦ = µj ∇hj (x∗ ) : µj ∈ R .
j=1

Alors
∑
q
∃ µ∗ ∈ Rq tel que ∇f (x∗ ) + µ∗j ∇hj (x∗ ) = 0.
j=1
∗
L’unicité de µ s’obtient facilement en considérant la condition d’independance linéaire des vec-
teurs ∇hj (x∗ ), j = 1, · · · , q. 

On peut reformuler ces résultats en considérant la fonction de Lagrange.

Définition 3.2.1 On appelle lagrangien associé au problème (P ) avec containtes d’égalité, c’est-
à-dire
min [f (x) : hj (x) = 0, j = 1, · · · , q]
la fonction
L : Rn × Rq −→ R
∑
(x, µ) 7−→ f (x) + qj=1 µj hj (x).

Les conditions nécessaires du premier ordre s’écrivent alors avec la fonction de Lagrange de la
façon suivante.

Proposition 3.2.3 On suppose qu f est différentiable en x∗ ∈ C, que les fonctions hj , j =

1, · · · , q sont de classe C 1 dans un voisinage de x∗ ∈ C et que le système {∇hj (x∗ ), j = 1, · · · , q}
est libre. Alors une condition nécessaire pour que x∗ soit une solution optimale locale de (P ) est
que : {
∗ ∇x L(x∗ , µ∗ ) = 0
∃! µ ∈ R tel que
q
∇µ L(x∗ , µ∗ ) = 0

Y a-t-il des situations où la condition nécessaire du théorème (3.2.3) ci-dessus est suffisante
pour que x∗ minimise f sur C ? Oui.

Théorème 3.2.4 (CNS d’optimalité du premier ordre) Supposons f convexe sur un ouvert
contenant C et les hj affines (i.e. de la forme x 7−→ hj (x) = ⟨aj , x⟩−bj ) linéairement indépendantes.
Alors, un élément x∗ ∈ C pour lequel

∑
q
∗ ∗
∃µ ∈ R q
tel que ∇f (x ) + µ∗j ∇hj (x∗ ) = 0
j=1

est un minimum global de f sur C.

24
 On a aussi des conditions d’optimalité du second ordre.

Théorème 3.2.5 (CN d’optimalité du second ordre) Soit x∗ ∈ C. On suppose que f et les
fonctions hj , j = 1, · · · , q sont de classe C 2 dans un voisinage de x∗ ∈ C et que le système
{∇hj (x∗ ), j = 1, · · · , q} est libre. Alors une condition nécessaire pour que x∗ soit une solution
optimale locale de (P ) est que :


 ∇x L(x∗ , µ∗ ) = 0

 ∇ L(x∗ , µ∗ ) = 0
∗ µ
∃!µ ∈ R tel que
q

 ⟨∇2xx L(x∗ , µ∗ )d, d⟩ ≥ 0


∀ d ∈ {d ∈ Rn : ⟨∇hj (x∗ ), d⟩ = 0 ∀ j = 1, · · · , q} .

Preuve : Soit x∗ une solution optimale locale de (P ). C’est-à-dire qu’il existe un voisinage V de
x∗ tel qu’on ait
f (x) ≥ f (x∗ ), ∀ ∈ C ∩ V.
D’après la proposition (3.2.3)
{
∗ ∇x L(x∗ , µ∗ ) = 0
∃!µ ∈ R q
tel que
∇µ L(x∗ , µ∗ ) = 0

On sait que
T (C, x∗ ) = {d ∈ Rn : ⟨∇hj (x∗ ), d⟩ = 0 ∀ j = 1, · · · , q} .
Soit
d ∈ {d ∈ Rn : ⟨∇hj (x∗ ), d⟩ = 0 ∀ j = 1, · · · , q}
tel que
⟨∇2xx L(x∗ , µ∗ )d, d⟩ < 0.
Alors par définition du cône tangent,

∃ {dk } ⊂ Rn dk −→ d,
: xk = x∗ + λk dk ∈ C ∩ V ∀ k ∈ N.
∃ {λk } ⊂ R∗+ λk −→ 0,

Comme la suite {xk } est contenue dans C et x∗ ∈ C, on a pour tout j, hj (x∗ ) = 0 et hj (xk ) = 0
pour tout k et par suite
L(xk , µ∗ ) = f (xk ), L(x∗ , µ∗ ) = f (x∗ ).
D’autre part on a xk −→ x∗ ; donc pour k assez grand :

L(xk , µ∗ ) = L(x∗ , µ∗ ) + ⟨∇x L(x∗ , µ∗ ), xk − x∗ ⟩

+ 12 ⟨∇2xx L(x∗ , µ∗ )(xk − x∗ ), xk − x∗ ⟩ + ∥xk − x∗ ∥2 ε(xk − x∗ ).

Il vient alors que

f (xk ) − f (x∗ ) 1 d
−→ ⟨∇2xx L(x∗ , µ∗ )d, ⟩ < 0.
∥x − x ∥
k ∗ 2 2 ∥d∥
Donc on aurait pour k assez grand, f (xk ) < f (x∗ ). Ce qui contredit le fait que x∗ est une solution
optimale locale de (P ). 

Le théorème qui suit donne des conditions suffisantes d’optimalité du second ordre.

25
Théorème 3.2.6 (Conditions Suffisantes d’optimalité du second ordre) Soit x∗ ∈ C. On
suppose que f et les fonctions hj , j = 1, · · · , q sont de classe C 2 dans un voisinage de x∗ et que le
système {∇hj (x∗ ), j = 1, · · · , q} est libre. Si


 ∇x L(x∗ , µ∗ ) = 0

 ∇ L(x∗ , µ∗ ) = 0
∃ µ∗ ∈ Rq tel que
µ

 ⟨∇2xx L(x∗ , µ∗ )d, d⟩ > 0


∀ 0 ̸= d ∈ {d ∈ Rn : ⟨∇hj (x∗ ), d⟩ = 0 ∀ j = 1, · · · , q} ,

alors x∗ est une solution optimale locale stricte de (P )

Preuve : Si x∗ n’est pas une solution optimale locale stricte de (P ), pour tout k ∈ N∗ , il existerait
xk ∈ C tel que ∥xk − x∗ ∥ < k1 et f (xk ) ≤ f (x∗ ).
∗
Soit alors dk = ∥xxk −x
k
−x∗ ∥
, alors ∥dk ∥ = 1 pour tout k. La suite {dk } est donc bornée, et on peut
en extraire une sous suite convergente. Supposons que c’est la suite {dk } elle même qui converge
et soit d sa limite. Alors ∥d∥ = 1 et donc d ̸= 0.
On a xk −→ x∗ et pour tout k, hj (xk ) = 0 pour tout j.
Pour tout j on a
xk − x∗ hj (xk ) − hj (x∗ )
⟨∇hj (x∗ ), d⟩ = lim⟨∇hj (x∗ ), ⟩ = lim = 0.
k ∥xk − x∗ ∥ k ∥xk − x∗ ∥

On a L(xk , µ∗ ) = f (xk ), L(x∗ , µ∗ ) = f (x∗ ) et pour k assez grand :

L(xk , µ∗ ) = L(x∗ , µ∗ ) + ⟨∇x L(x∗ , µ∗ ), xk − x∗ ⟩

+ 12 ⟨∇2xx L(x∗ , µ∗ )(xk − x∗ ), xk − x∗ ⟩ + ∥xk − x∗ ∥2 ε(xk − x∗ ).

Ce qui est équivalent à

f (xk ) = f (x∗ ) + 12 ⟨∇2xx L(x∗ , µ∗ )(xk − x∗ ), xk − x∗ ⟩

+∥xk − x∗ ∥2 ε(xk − x∗ ).

Or f (x∗ ) ≥ f (xk ) pour tout k. Alors on peut écrire pour tout k :

f (x∗ ) ≥ f (xk ) = f (x∗ ) + 12 ⟨∇2xx L(x∗ , µ∗ )(xk − x∗ ), xk − x∗ ⟩

+∥xk − x∗ ∥2 ε(xk − x∗ ).
Soit
1 2
⟨∇ L(x∗ , µ∗ )(xk − x∗ ), xk − x∗ ⟩ + ∥xk − x∗ ∥2 ε(xk − x∗ ) ≤ 0.
2 xx
Cela pour tout k. En passant à la limite, on obtient

⟨∇2xx L(x∗ , µ∗ )d, d⟩ ≤ 0.

Ce qui est contradictoire car

0 ̸= d ∈ {d ∈ Rn : ⟨∇hj (x∗ ), d⟩ = 0 ∀ j = 1, · · · , q} .

Ce qui termine la démonstration. 

26
3.2.3 Problème avec contraintes d’inégalité
On suppose ici que
C = {x ∈ Rn : gi (x) ≤ 0, i = 1, · · · , p}
où les fonctions gi , i = 1, · · · , m sont définies sur Rn et à valeurs dans R ∪ {+∞}.
Pour x ∈ C on note I(x) = {i ∈ {1, · · · , p} : gi (x) = 0} l’ensemble des indices des contraintes
actives en x.
On a la proposition suivante :

Proposition 3.2.4 Soit x̄ ∈ C On suppose que les fonctions gi sont continues dans un voisinage
de x̄. Alors, on a T (C, x̄) = T (D, x̄) où

D = {x ∈ Rn : gi (x) ≤ 0, i ∈ I(x̄)} .

Preuve : On a C ⊂ D. D’autre part, pour tout i ∈

/ I(x̄), il existe un voisinage Vi de x̄ tel que :
gi (x̄)
∀ x ∈ Vi , gi (x) < <0
2
Soit
V = ∩i∈I(x̄
/ Vi .
On a C ∩ V = D ∩ V et donc

T (C, x̄) = T (C ∩ V, x̄) = T (D ∩ V, x̄) = T (D, x̄).

D’où la proposition. 

Il ressort de cette proposition que si les fonctions gi sont continues, l’expression du cône tangent
de C en x̄ ne fait intervenir que les contraintes actives en x̄.

Proposition 3.2.5 Soit x̄ ∈ C, On suppose que les fonctions gi sont continues dans un voisinage
de x̄ et que les gi pour i ∈ I(x̄) sont différentiables en x̄.
Alors
T (C, x̄) ⊂ {d ∈ Rn : ⟨∇gi (x̄), d⟩ ≤ 0, ∀ i ∈ I(x̄)} = L(C, x̄).

Preuve : Soit d ∈ T (C, x̄). Si d = 0, alors d ∈ L(C, x̄).

Supposons d ̸= 0 ; on peut considérer que ∥d∥ = 1.
Comme d ∈ T (C, x̄), par définition du cône tangent,

∃ {dk } ⊂ Rn dk −→ d,
: xk = x̄ + tk dk ∈ C ∀ k ∈ N.
∃ {tk } ⊂ R∗+ tk −→ 0,

On a alors pour tout i, gi (xk ) ≤ 0 pour tout k.

On a aussi pour tout i ∈ I(x̄), gi (x̄) = 0.
Comme xk −→ x∗ , on a pour tout i ∈ I(x̄), (les gi pour i ∈ I(x̄) sont différentiables en x̄),

gi (xk ) − gi (x̄) − ⟨∇gi (x̄), xk − x̄⟩

lim = 0. (3.3)
k ∥xk − x̄∥
Mais comme
xk − x̄ dk
⟨∇gi (x̄), ⟩ = ⟨∇g i (x̄), ⟩ −→ ⟨∇gi (x̄), d⟩,
∥xk − x̄∥ ∥dk ∥

27
en utilisant (3.3), on a pour tout i ∈ I(x̄),

gi (xk ) xk − x̄
lim = lim ⟨∇gi (x̄), ⟩ = ⟨∇gi (x̄), d⟩.
k ∥xk − x̄∥ k ∥xk − x̄∥
gi (xk )
Comme pour tout k, ∥xk −x̄∥
≤ 0 (gi (xk ) ≤ 0), on a ⟨∇gi (x̄), d⟩ ≤ 0 ; et cela pour tout i ∈ I(x̄),
donc d ∈ L(C, x̄). 

On remarque que l’ensemble L(C, x̄) est un cône polyédrique convexe fermé.
On définit maintenant la notion de qualification des contraintes en un point.

Définition 3.2.2 Soit x̄ ∈ C. On suppose que les fonctions gi sont continues dans un voisinage
de x̄ et que les gi pour i ∈ I(x̄) sont différentiables en x̄.
On dit que les contraintes sont qualifiées en x̄ ou que le point x̄ est qualifié, si T (C, x̄) =
L(C, x̄). C’est-à-dire

T (C, x̄) = {d ∈ Rn : ⟨∇gi (x̄), d⟩ ≤ 0, ∀ i ∈ I(x̄)} .

Remarque 3.2.1 La vérification directe de la qualification des contraintes en un point est très
difficile en pratique. C’est pourquoi on recherche des conditions suffisantes pour avoir la qualifica-
tion.

Proposition 3.2.6 (Condition de qualification de Karlin)

Si toutes les fonctions gi sont affines et C non vide alors tout point de C est qualifié.

Preuve : Soit x̄ ∈ C. On peut écrire

gi (x) = gi (x̄) + ⟨∇gi (x̄), x − x̄⟩ ∀ i.

On a T (C, x̄) = T (D, x̄) avec

D = {x ∈ Rn : gi (x) ≤ 0, ∀ i ∈ I(x̄)} .

On a D qui est convexe et donc

T (D, x̄) = {d : ∃λ > 0, x̄ + λd ∈ D}

= {d : ∃λ > 0, λ⟨∇gi (x̄), d⟩ ≤ 0 ∀ i ∈ I(x̄)}

= {d : ⟨∇gi (x̄), d⟩ ≤ 0 ∀ i ∈ I(x̄)}

= {d : ⟨∇gi (x̄), d⟩ ≤ 0 ∀ i ∈ I(x̄)}

Donc T (C, x̄) = T (D, x̄) = L(C, x̄). 

Proposition 3.2.7 (Condition de qualification de Slater)

Si toutes les fonctions gi sont convexes et différentiables sur un ouvert contenant C, et si ∃ x̃ ∈ C
tel que gi (x̃) < 0 pour tout i, c’est-à-dire que C est d’intérieur non vide, alors tout point de C est
qualifié.

28
Preuve : Soit x̄ ∈ C : on sait que

T (C, x̄) ⊂ {d : ⟨∇gi (x̄), d⟩ ≤ 0 ∀ i ∈ I(x̄)} = L(C, x̄).

Il reste donc à montrer l’inclusion inverse, c’est-à-dire que L(C, x̄) ⊂ T (C, x̄).
Posons
K = {d : ⟨∇gi (x̄), d⟩ < 0 ∀ i ∈ I(x̄)}
On a K ̸= ∅ : en effet on a pour tout i ∈ I(x̄),

0 > gi (x̃) = gi (x̃) − gi (x̄) ≥ ⟨∇gi (x̄), x̃ − x̄⟩.

(car les fonctions gi sont convexes et différentiables) : donc x̃ − x̄ ∈ K.

Soit d ∈ K. Considérons la suite {tk } ⊂ R∗+ tendant vers 0 et dk = d pour tout k.
On a pour tout i ∈ I(x̄)

gi (x̄ + tk dk ) = gi (x̄ + tk d) = gi (x̄) + tk ⟨∇gi (x̄), d⟩ + tk ε(tk )

= tk ⟨∇gi (x̄), d⟩ + tk ε(tk ).

Pour k assez grand on a gi (x̄ + tk dk ) ≤ 0, cela pour tout i ∈ I(x̄). Donc d ∈ T (D, x̄) où

D = D = {x ∈ Rn : gi (x) ≤ 0, ∀ i ∈ I(x̄)} .

Il s’ensuit alors que d ∈ T (D, x̄) = T (C, x̄). C’est-à-dire que K ⊂ T (C, x̄).
On a
K = {d : ⟨∇gi (x̄), d⟩ ≤ 0 ∀ i ∈ I(x̄)} .
Comme T (C, x̄) est fermé, on a
L(C, x̄) = K ⊂ T (C, x̄).
D’où l’inclusion inverse 

Proposition 3.2.8 (Condition de Fiacco-Mc Cormick)

Soit x̄ ∈ C, on suppose que les fonctions gi sont continues dans un voisinage de x̄ et que les gi
pour i ∈ I(x̄) sont différentiables en x̄. Si le système {∇gi (x̄) : i ∈ I(x̄)} est libre alors le point x̄
est qualifié.

Preuve : Considérons q = cardI(x̄) et A la q × n matrice dont la iieme ligne est la transposée de

∇gi (x̄) pour i ∈ I(x̄). Alors

K = {d : ⟨∇gi (x̄), d⟩ < 0 ∀ i ∈ I(x̄)} = {d : Ad < 0}

Montrons que K ̸= ∅.
Si K = ∅ alors les ensembles convexes {Ad : d ∈ Rn } et R∗q
− sont disjoints.
Il existe donc a ̸= 0 tel que

sup [⟨a, Ad⟩ : d ∈ Rn ] ≤ ⟨a, y⟩, ∀ y ∈ R∗q

−.

On a nécessairement
⟨a, Ad⟩ ≤ 0 ∀ d ∈ Rn .
Ce qui implique que AT a = 0, c’est-à-dire que
∑
ai ∇gi (x̄) = 0.
i∈I(x̄)

29
Ce qui est contradictoire car le système {∇gi (x̄) : i ∈ I(x̄)} est libre et a ̸= 0. En conclusion on a
K ̸= ∅.
Soit d ∈ K. Considérons la suite {tk } ⊂ R∗+ tendant vers 0 et dk = d pour tout k.
On a pour tout i ∈ I(x̄)

gi (x̄ + tk dk ) = gi (x̄ + tk d) = gi (x̄) + tk ⟨∇gi (x̄), d⟩ + tk ε(tk )

= tk ⟨∇gi (x̄), d⟩ + tk ε(tk ).

Pour k assez grand on a gi (x̄ + tk dk ) ≤ 0, cela pour tout i ∈ I(x̄). Donc d ∈ T (D, x̄) où

D = D = {x ∈ Rn : gi (x) ≤ 0, ∀ i ∈ I(x̄)} .

Il s’ensuit alors que d ∈ T (D, x̄) = T (C, x̄). C’est-à-dire que K ⊂ T (C, x̄).
On a
K = {d : ⟨∇gi (x̄), d⟩ ≤ 0 ∀ i ∈ I(x̄)} .
Comme T (C, x̄) est fermé, on a
L(C, x̄) = K ⊂ T (C, x̄).
D’où l’inclusion inverse 
On peut donner maintenant les conditions d’optimalité.

Théorème 3.2.7 (CN d’optimalité de Kuhn- Tucker)

Soit x∗ ∈ C, on suppose que les fonctions gi sont continues dans un voisinage de x∗ et que f et
les gi i ∈ I(x∗ ) sont différentiables en x∗ .
Si x∗ est un point qualifié alors une condition nécessaire pour qu’il soit une solution optimale
locale de (P ) est : ∑
∃ λi ≥ 0, i ∈ I(x∗ ) : ∇f (x∗ ) + λi ∇gi (x∗ ) = 0.
i∈I(x∗ )

(les λi sont appelés multiplicateurs de Kuhn-Tucker).

Preuve : D’après le theoème (3.2.1), si x∗ est une solution optimale locale, on a :

⟨∇f (x∗ ), d⟩ ≥ 0 ∀ d ∈ T (C, x∗ ).

c’est-à-dire que
−∇f (x∗ ) ∈ T (C, x∗ )◦ .
Or le point x∗ étant qualifié on a

T (C, x∗ ) = {d : ⟨∇gi (x∗ ), d⟩ ≤ 0 ∀ i ∈ I(x∗ )} .

Donc ∑
−∇f (x∗ ) ∈ T (C, x∗ )◦ ⇐⇒ ∃ λi ≥ 0, i ∈ I(x∗ ) : −∇f (x∗ ) = λi ∇gi (x∗ )
i∈I(x∗ )

D’où le résultat 

Remarque 3.2.2 Si le système {∇gi (x∗ ), i ∈ I(x∗ )} est libre, alors le vecteur multiplicateur de
Kuhn Tucker λ est unique.

30
Proposition 3.2.9 Si toutes les fonctions gi sont différentiables en x∗ , la condition d’optimalité
de Kuhn-Tucker s’écrit : 

 ∃ λ ∈ R+ tel
p
que :
∑p
∇f (x ) + i=1 λi ∇gi (x∗ ) = 0
∗

 λ g (x∗ ) = 0, ∀ i ∈ {1, · · · , p}.
i i

Preuve : Il suffit de prendre λi = 0 pour les contraintes non actives en x∗ . 

Dans le cas où le problème (P ) est convexe, la condition nécessaire d’optimalité de Kuhn-Tucker
est aussi suffisante.

Théorème 3.2.8 (CNS d’optimalité de Kuhn Tucker)

Soit x∗ ∈ C, on suppose que les fonctions gi sont continues dans un voisinage de x∗ et que f et
les gi i ∈ I(x∗ ) sont différentiables en x∗ . Si les fonctions f et les gi sont convexes, et si x∗ est un
point qualifié, alors x∗ est une solution optimale globale de (P ) si et seulement si :
∑
∃ λi ≥ 0, i ∈ I(x∗ ) : ∇f (x∗ ) + λi ∇gi (x∗ ) = 0.
i∈I(x∗ )

(les λi sont appelés multiplicateurs de Kuhn-Tucker).

Preuve : La condition est nécessaire.

Réciproquement, supposons que ces conditions sont réalisées en x∗ et soit x ∈ C. On a gi (x) ≤ 0
et gi (x∗ ) = 0 pour tout i ∈ I(x∗ ). Donc

0 ≥ gi (x) = gi (x) − gi (x∗ ) ≥ ⟨∇gi (x∗ ), x − x∗ ⟩ ∀ i ∈ I(x∗ ).

Par suite on a
⟨∇gi (x∗ ), x − x∗ ⟩ ≤ 0 ∀ i ∈ I(x∗ ).
Comme par hypothèse on a ∑
∇f (x∗ ) = − λi ∇gi (x∗ ),
i∈I(x∗ )

il vient ∑
⟨∇f (x∗ ), x − x∗ ⟩ = − λi ⟨∇gi (x∗ ), x − x∗ ⟩ ≥ 0.
i∈I(x∗ )

Comme f est convexe, on a

f (x) − f (x∗ ) ≥ ⟨∇f (x∗ ), x − x∗ ⟩ ≥ 0.

Soit alors
f (x) ≥ f (x∗ )
et donc x∗ est un minimum de f sur C. 
Comme dans le cas des contraintes d’égalité, on peut écrire les conditions d’optimalité à l’aide
du lagrangien défini comme suit.

31
Définition 3.2.3 On appelle lagrangien associé au problème (P ) avec containtes d’inégalité, c’est-
à-dire
min [f (x) : gi (x) ≤ 0, i = 1, · · · , p]
la fonction
L : Rn × Rp+ −→ R
∑
(x, λ) 7−→ f (x) + pi=1 λi gi (x).

On montre alors

Proposition 3.2.10 Soit x∗ ∈ C, on suppose que les fonctions f et les gi sont différentiables en
x∗ .
Si x∗ est un point qualifié alors une condition nécessaire pour qu’il soit une solution optimale
locale de (P ) est : 
 ∗
 ∃ λ ∈ R+ tel que :
p

∇x L(x∗ , λ∗ ) = 0

 λ∗ g (x∗ ) = 0, ∀ i ∈ {1, · · · , p}.
i i

On obtient à l’aide du lagrangien les conditions du second ordre.

Théorème 3.2.9 (CN d’optimalité du second ordre)

Soit x∗ ∈ C ; on suppose que les fonctions f et les gi sont deux fois différentiables dans un voisinage
de x∗ et que le système {∇gi (x∗ ), i ∈ I(x∗ )} est libre. Alors une condition nécessaire pour qu’il
soit une solution optimale locale de (P ) est :


 ∃ λ∗ ∈ Rp+ tel que :


 ∗ ∗
 ∇x L(x , λ ) = 0
λ∗i gi (x∗ ) = 0, ∀ i ∈ {1, · · · , p},



 ⟨∇2xx L(x∗ , λ∗ )d, d⟩ ≥ 0,


∀ d ∈ {d : ⟨∇gi (x∗ ), d⟩ = 0, i ∈ I(x∗ )}

Preuve : D’après les résultats précédents, on sait que :


 ∃ λ∗ ∈ R+ tel que :
p

∇x L(x∗ , λ∗ ) = 0
 ∗
λi gi (x∗ ) = 0, ∀ i ∈ {1, · · · , p}.

Supposons que

∃ d ∈ {d : ⟨∇gi (x∗ ), d⟩ = 0, i ∈ I(x∗ )} : ⟨∇2xx L(x∗ , λ∗ )d, d⟩ < 0.

Supposons que les contraintes actives en x∗ sont g1 , · · · , gm .

On considère
g : Rn −→ Rm
x 7−→ g(x) = (g1 (x), · · · , gm (x))
et
r : Rm × R −→ Rm [ ]
(u, t) 7−→ r(u, t) = g x∗ + [g ′ (x∗ )]T u + td

32
On a
r(0, 0) = g(x∗ ) = 0, ru′ (0, 0) = [g ′ (x∗ )][g ′ (x∗ )]T ∈ Mm (R)
qui est inversible car les lignes de la matrice [g ′ (x∗ )] sont linéairement independantes. On a aussi

rt′ (0, 0) = [g ′ (x∗ )]d = 0

car d ∈ L(C, x∗ ). Comme r est de classe C 1 dans un voisinage de (0, 0), alors d’après le théorème
des fonctions implicites, il existe V × W ∈ V(0Rm , 0R ), V ⊂ Rm , W ⊂ R, il existe θ : W −→ V de
classe C 1 tels que :
i) r(θ(t), t) = r(0, 0),
ii) θ(t) est l’unique solution dans V de l’équation r(x, t) = 0,
iii) ru′ (θ(t), t)θ′ (t) + rt′ (θ(t), t) = 0, ∀ t ∈ W.
D’après i) on a θ(0) = 0.
En utilisant iii), et le fait que

ru′ (0, 0) = [g ′ (x∗ )][g ′ (x∗ )]T et rt′ (0, 0) = [g ′ (x∗ )]d = 0,

on obtient
[g ′ (x∗ )][g ′ (x∗ )]T θ′ (0) = 0.
On tire alors θ′ (0) = 0.
Soit {tk } ⊂ R∗+ , tk tendant vers 0. Il existe alors un rang k1 tel que pour tout k ≥ k1 , tk ∈ W .
Donc pour tout k ≥ k1 , on a r(θ(tk ), tk ) = 0. c’est-à-dire
[ ]
g x∗ + [g ′ (x∗ )]T θ(tk ) + tk d = 0.

Posons
xk = x∗ + [g ′ (x∗ )]T θ(tk ) + tk d pour k ≥ k1 .
On a alors
θ(tk )
xk = x∗ + tk dk avec dk = [g ′ (x∗ )]T + d.
tk
Comme
θ′ (0) = θ(0) = 0,
on a
θ(tk )
−→ 0.
tk
Donc dk −→ d et xk −→ x∗ .
D’autre part, on a pour tout k, gi (xk ) = 0 pour tout i ∈ I(x∗ ). Mais auusi xk −→ x∗ et les gi
/ I(x∗ ) sont continues en x∗ ; il existe alors k2 tel que gi (xk ) < 0 pour tout k ≥ k2 et cela
pour i ∈
/ I(x∗ ). Il vient donc que xk ∈ C pour tout k ≥ k2 .
pour tout i ∈
On a
L(xk , λ∗ ) = L(x∗ , λ∗ ) + ⟨∇x L(x∗ , λ∗ ), xk − x∗ ⟩

+ 12 ⟨∇2xx L(x∗ , λ∗ )(xk − x∗ ), xk − x∗ ⟩ + ∥xk − x∗ ∥2 ε(xk − x∗ ).

Mais comme
∇x L(x∗ , λ∗ ) = 0, il reste

33
 1
L(xk , λ∗ ) = L(x∗ , λ∗ ) + ⟨∇2xx L(x∗ , λ∗ )(xk − x∗ ), xk − x∗ ⟩ + ∥xk − x∗ ∥2 ε(xk − x∗ ).
2
On a L(xk , λ∗ ) = f (xk ) et L(x∗ , λ∗ ) = f (x∗ ). Il s’ensuit alors

f (xk ) − f (x∗ ) 1 d
−→ ⟨∇2xx L(x∗ , λ∗ )d, ⟩ < 0.
∥x − x ∥
k ∗ 2 2 ∥d∥2

Donc f (xk ) < f (x∗ ) pour k assez grand. Ce qui contredit le fait que x∗ est un minimum local de
f sur C. 

Théorème 3.2.10 (CS d’optimalité du second ordre)

Soit x∗ ∈ C. On suppose que f et les fonctions gi , i = 1, · · · , p sont de classe C 2 dans un voisinage
de x∗ ∈ C et que le système {∇gi (x∗ ), i ∈ I(x∗ )} est libre. Si


 ∇x L(x∗ , λ∗ ) = 0

 λ∗ g (x∗ ) = 0, ∀ i ∈ {1, · · · , p},
∗ i i
∃ λ ∈ R+ tel que :
p

 ⟨∇2xx L(x∗ , λ∗ )d, d⟩ > 0


∀ 0 ̸= d ∈ {d ∈ Rn : λ∗i ⟨∇gi (x∗ ), d⟩ = 0 ∀ i ∈ I(x∗ )} ,

alors x∗ est une solution optimale locale stricte de (P )

Preuve : Si x∗ n’est pas une solution optimale locale stricte de (P ), pour tout k ∈ N∗ , il existe
xk ∈ C tel que ∥xk − x∗ ∥ < k1 et f (xk ) ≤ f (x∗ ).
∗
Soit alors dk = ∥xxk −x
k
−x∗ ∥
, alors ∥dk ∥ = 1 pour tout k. La suite {dk } est donc bornée, et on peut
en extraire une sous suite convergente. Supposons que c’est la suite {dk } elle même qui converge
et soit d sa limite. Alors ∥d∥ = 1 et donc d ̸= 0.
On a xk −→ x∗ et pour tout k, gi (xk ) ≤ 0 pour tout i.
On a aussi
L(xk , λ∗ ) ≤ f (xk ) ≤ f (x∗ ) = L(x∗ , λ∗ ),
∀ i ∈ I(x∗ ), gi (xk ) ≤ 0 = gi (x∗ )
et donc ⟨∇gi (x∗ ), d⟩ ≤ 0. D’autre part on a f (xk ) ≤ f (x∗ ). On en déduit alors que ⟨∇f (x∗ ), d⟩ ≤ 0.
Or ∇x L(x∗ , λ∗ ) = 0. Ce qui implique que

⟨∇x L(x∗ , λ∗ ), d⟩ = 0,

c’est-à-dire ∑
⟨∇f (x∗ ), d⟩ + λ∗i ⟨∇gi (x∗ ), d⟩ = 0.
i∈I(x∗ )

Dans le premier membre de cette égalité, chaque terme est négatif ou nulle il vient donc que
chaque terme est nulle. On obtient alors

λ∗i ⟨∇gi (x∗ ), d⟩ = 0 ∀ i ∈ I(x∗ ).

Donc
0 ̸= d ∈ {d ∈ Rn : λ∗i ⟨∇gi (x∗ ), d⟩ = 0 ∀ i ∈ I(x∗ )} .

34
 Par ailleurs on a
L(xk , λ∗ ) = L(x∗ , λ∗ ) + ⟨∇x L(x∗ , λ∗ ), xk − x∗ ⟩

+ 12 ⟨∇2xx L(x∗ , λ∗ )(xk − x∗ ), xk − x∗ ⟩ + ∥xk − x∗ ∥2 ε(xk − x∗ ),

ce qui implique que
f (x∗ ) > f (xk ) ≥ L(xk , λ∗ ) = f (x∗ ) + 21 ⟨∇2xx L(x∗ , λ∗ )(xk − x∗ ), xk − x∗ ⟩

+∥xk − x∗ ∥2 ε(xk − x∗ ),
qui est équivalent à
1
0 > ⟨∇2xx L(x∗ , λ∗ )(xk − x∗ ), xk − x∗ ⟩ + ∥xk − x∗ ∥2 ε(xk − x∗ ),
2
Donc
⟨∇2xx L(x∗ , λ∗ )d, d⟩ ≤ 0.
Ce qui n’est pas . 

3.2.4 Problème avec contraintes d’égalité et d’inégalité

On s’intéresse ici au
{ }
g (x) ≤ 0, i = 1, · · · , p,
C= x∈R : i
n
hj (x) = 0, j = 1, · · · , q
où les fonctions gi , i = 1, · · · , p et hj , j = 1, · · · , q sont définies sur Rn et à valeurs dans R ∪{+∞}.
Pour x ∈ C on note I(x) = {i ∈ {1, · · · , p} : gi (x) = 0} l’ensemble des indices des contraintes
actives en x.
Comme précédemment, on veut obtenir une expression du cône tangent en fonction des fonc-
tions gi et hj .
La proposition ci-dessous est semblable au cas du problème avec contraintes d’égalité.

Proposition 3.2.11 Soit x̄ ∈ C. On suppose que les fonctions gi sont continues dans un voisinage
de x̄. Alors, on a T (C, x̄) = T (D, x̄) où
{ }
gi (x) ≤ 0, i ∈ I(x̄),
D = x ∈ Rn : .
hj (x) = 0, j = 1, · · · , q.

Preuve : pour tout i ∈

/ I(x̄), il existe un voisinage Vi de x̄ tel que :
gi (x̄)
∀ x ∈ Vi , gi (x) < <0
2
Soit
V = ∩i∈I(x̄
/ Vi .
On a C ∩ V = D ∩ V et donc
T (C, x̄) = T (C ∩ V, x̄) = T (D ∩ V, x̄) = T (D, x̄).
D’où la proposition. 
On a la proposition suivante

35
Proposition 3.2.12 Soit x̄ ∈ C. On suppose que les fonctions gi i = 1, · · · , p sont continues dans
un voisinage de x̄, et que les fonctions gi , i ∈ I(x̄) sont différentiables en x̄ et les hj , j = 1, · · · , q
sont continûment différentiables dans un voisinage de x̄. Alors
{ }
⟨∇gi (x̄), d⟩ ≤ 0, ∀ i ∈ I(x̄)
T (C, x̄) ⊂ d∈R : n
= L(C, x̄).
⟨∇hj (x̄), d⟩ = 0, ∀ j = 1, · · · , q

Preuve : Soit d ∈ T (C, x̄). Si d = 0, alors d ∈ L(C, x̄).

Supposons d ̸= 0 ; on peut supposer sans perdre de généralités que ∥d∥ = 1.
Comme d ∈ T (C, x̄),

∃ {dk } ⊂ Rn , dk −→ d,
: xk = x̄ + tk dk ∈ C ∀ k ∈ N.
∃ {tk } ⊂ R∗+ , tk −→ 0,

On a alors pour tout i, gi (xk ) ≤ 0 pour tout k.

On a aussi pour tout i ∈ I(x̄), gi (x̄) = 0.
Comme xk −→ x̄, on a pour tout i ∈ I(x̄), (les gi pour i ∈ I(x̄) sont différentiables en x̄),

gi (xk ) − gi (x̄) − ⟨∇gi (x̄), xk − x̄⟩

lim = 0. (3.4)
k ∥xk − x̄∥

Mais comme
xk − x̄ dk
⟨∇gi (x̄), ⟩ = ⟨∇g i (x̄), ⟩ −→ ⟨∇gi (x̄), d⟩,
∥xk − x̄∥ ∥dk ∥
en utilisant (3.4), on a pour tout i ∈ I(x̄),

gi (xk ) xk − x̄
lim = lim ⟨∇gi (x̄), ⟩ = ⟨∇gi (x̄), d⟩.
k ∥xk − x̄∥ k ∥xk − x̄∥
k
Comme pour tout k, ∥xgik(x−x̄∥
)
≤ 0 (gi (xk ) ≤ 0), on a ⟨∇gi (x̄), d⟩ ≤ 0 ; et cela pour tout i ∈ I(x̄).
D’autre part pour tout j ∈ {1, · · · , q}, hj (x̄) = hj (xk ) = 0. Donc ⟨∇hj (x̄), d⟩ = 0. Il s’ensuit que
d ∈ L(C, x̄). 
On définit

Définition 3.2.4 Soit x̄ ∈ C. On suppose que les fonctions gi i = 1, · · · , p sont continues dans
un voisinage de x̄, et que les fonctions gi , i ∈ I(x̄) sont différentiables en x̄ et les hj , j = 1, · · · , q
sont continûment différentiables dans un voisinage de x̄.
On dit que les contraintes sont qualifiées en x̄ ou que le point x̄ est qualifié, si T (C, x̄) =
L(C, x̄). C’est-à-dire
{ }
⟨∇gi (x̄), d⟩ ≤ 0, ∀ i ∈ I(x̄)
T (C, x̄) = d ∈ Rn : .
⟨∇hj (x̄), d⟩ = 0, ∀ j = 1, · · · , q

Proposition 3.2.13 (Condition de qualification de Karlin)

Si toutes les fonctions gi et hj sont affines et C non vide alors tout point de C est qualifié.

36
Théorème 3.2.11 (Qualification de Mangasarian-Fromovitz)
Soit x̄ ∈ C. On suppose que les fonctions gi i ∈ / I(x̄) sont continues dans un voisinage de x̄, les
fonctions gi , i ∈ I(x̄) et les hj , j = 1, · · · , q sont continûment différentiables dans un voisinage
de x̄. Si
a) ∃ d ∈ Rn tel que

⟨∇gi (x̄), d⟩ < 0, ∀ i ∈ I(x̄) et ⟨∇hj (x̄), d⟩ = 0, ∀ j = 1, · · · , q

b) les vecteurs ∇hj (x̄) j = 1, · · · , q sont linéairement independants,

alors le point x̄ est qualifié.

Preuve : Posons
{ }
⟨∇gi (x̄), d⟩ < 0, ∀ i ∈ I(x̄)
L̂(C, x̄) = d ∈ R :
n
.
⟨∇hj (x̄), d⟩ = 0, ∀ j = 1, · · · , q

Montrons d’abord que L̂(C, x̄) = L(C, x̄).

On a bien sûr L̂(C, x̄) ⊂ L(C, x̄).
Réciproquement l’hypothèse a) du théorème implique que L̂(C, x̄) ̸= ∅. Soit dˆ ∈ L̂(C, x̄) et soit
d ∈ L(C, x̄). On a alors
ˆ < 0, ⟨∇gi (x̄), d⟩ ≤ 0 ∀ i ∈ I(x̄),
⟨∇gi (x̄), d⟩
ˆ = 0, ⟨∇hj (x̄), d⟩ = 0 ∀ j = 1, · · · , q.
⟨∇hj (x̄), d⟩

Considérons dk = d + k1 dˆ : alors dk ∈ L̂(C, x̄) et comme dk −→ d, on a d ∈ L̂(C, x̄).

Soit d ∈ L̂(C, x̄). On considère

h : Rn −→ Rq
x 7−→ h(x) = (h1 (x), · · · , hq (x))

et
r : Rq × R −→ Rq [ ]
(u, t) 7−→ r(u, t) = h x̄ + [h′ (x̄)]T u + td
On a r(0, 0) = h(x̄) = 0, ru′ (0, 0) = [h′ (x̄)][h′ (x̄)]T ∈ Mq (R) qui est inversible car les lignes de la
matrice [h′ (x̄)] sont linéairement independantes. On a aussi rt′ (0, 0) = [h′ (x̄)]d = 0, car d ∈ L̂(C, x̄).
En outre r est de classe C 1 dans un voisinage de (0, 0), alors d’après le théorème des fonctions
implicites, il existe V × W ∈ V(0Rq , 0R ), V ⊂ Rq , W ⊂ R, il existe θ : W −→ V de classe C 1 tels
que :
i) r(θ(t), t) = r(0, 0),
ii) θ(t) est l’unique solution dans V de l’équation r(x, t) = 0,
iii) ru′ (θ(t), t)θ′ (t) + rt′ (θ(t), t) = 0, ∀ t ∈ W.
D’après i) on a θ(0) = 0.
En utilisant iii), et le fait que

ru′ (0, 0) = [h′ (x̄)][h′ (x̄)]Tm boxetrt′ (0, 0) = [h′ (x∗ )]d = 0,

on obtient
[h′ (x̄)][h′ (x̄)]T θ′ (0) = 0.

37
On tire alors θ′ (0) = 0.
Donnons nous une suite {tk } ⊂ R∗+ tk tendant vers 0. Il existe alors un rang k1 tel que pour
tout k ≥ k1 , tk ∈ W .
Donc [ ]
r(θ(tk ), tk ) = h x̄ + [h′ (x̄)]T θ(tk ) + tk d = 0.
On considère
xk = x̄ + [h′ (x̄)]T θ(tk ) + tk d pour k ≥ k1 .
On a alors xk = x̄ + tk dk avec dk = [h′ (x̄)]T θ(ttkk ) + d.
Comme θ′ (0) = θ(0) = 0, on a θ(ttkk ) −→ 0 et donc dk −→ d. On a aussi h(xk ) = 0, pour tout
k ≥ k1 , c’est-à-dire que pour tout j, hj (xk ) = 0 et cela pour tout k ≥ k1 .
D’autre part puisque d ∈ L̂(C, x̄) on a
ˆ < 0 ∀ i ∈ I(x̄)
⟨∇gi (x̄), d⟩
Or tk −→ 0 dk −→ d, gi (x̄) = 0 ∀ i ∈ I(x̄) et xk = x̄ + tk dk ,
gi (xk ) ˆ < 0.
−→ ⟨∇gi (x̄), d⟩
tk
Donc gi (xk ) < 0 pour k assez grand.
En outre on a xk −→ x̄, ce qui implique que gi (xk ) < 0 si i ∈
/ I(x̄) pour k assez grand. On a
donc xk ∈ C pour k assez grand.
En résumé on a
xk = x̄ + tk dk ∈ C, pour k assez grand tk −→ 0, dk −→ d.
Il s’ensuit alors que d ∈ T (C, x̄). 
On montre que

Proposition 3.2.14 Soit x̄ ∈ C. On suppose que les fonctions gi i ∈ / I(x̄) sont continues dans un
voisinage de x̄, les fonctions gi , i ∈ I(x̄) et les hj , j = 1, · · · , q sont continûment différentiables
dans un voisinage de x̄. Si la condition d’indépendance linéaire c’est-à-dire le système {∇gi (x̄), i ∈
I(x̄), ∇hj (x̄) j = 1, · · · , q} est libre, alors la condition de Mangasarian-Fromovitz est satisfaite
en x̄. Donc c’est un point qualifié
Dans le cas convexe, on définit la condition de Slater suivante.
Définition 3.2.5 On suppose que les fonctions hj sont affines et que les gi sont convexes et
différentiables sur un ouvert contenant C. On dira que la condition de Slater est satisfaite si
gi (x̃) < 0, ∀ i = 1, · · · , p
∃ x̃ ∈ Rn :
hj (x̃) = 0, ∀ j = 1, · · · , q
On a la proposition

Proposition 3.2.15 On suppose que les gi sont convexes et différentiables sur un ouvert conte-
nant C et que les fonctions hj sont affines et linéairement independantes. Alors
a) Si la condition de Slater est satisfaite en un point x̄ de C, la condition de Mangasarian-
Fromovitz est satisfaite en tout point de C.
b) Si la condition de Mangasarian-Fromovitz est satisfaite en un point x̄ de C alors la condition
de Slater est satisfaite.

38
 On en déduit alors

Corollaire 3.2.2 Si les gi sont convexes et différentiables sur un ouvert contenant C et les fonc-
tions hj sont affines et linéairement independantes alors :
a) Si la condition de Slater est satisfaite alors tout point de C est qualifié.
b) Si la condition de Mangasarian-Fromovitz est satisfaite en un point de C, alors tout point
de C est qualifié

On peut maintenant donner les conditions d’optimalité.

Théorème 3.2.12 (CN d’optimalité de Kuhn-Tucker)

Soit x∗ ∈ C. On suppose que les fonctions gi i ∈ / I(x∗ ) sont continues dans un voisinage de x∗ , les
fonctions f , gi , i ∈ I(x∗ ) les hj , j = 1, · · · , q sont continûment différentiables dans un voisinage
de x∗ et qu’il est qualifié. Alors une condition nécessaire pour qu’il soit une solution optimale
locale de (P ) est que :


 ∃ λ∗i ≥ 0, ∀ i ∈ I(x∗ ), µ∗j ∈ R, j = 1, · · · , q




tels que





 ∑ ∑
∇f (x∗ ) + i∈I(x∗ ) λ∗i ∇gi (x∗ ) + qj=1 µ∗j ∇hj (x∗ ) = 0.

on dit alors que x∗ est un point de Kuhn-Tucker

Une version plus facile à manipuler en pratique est donnée dans le corollaire ci-dessous

Corollaire 3.2.3 Soit x∗ ∈ C. On suppose que les fonctions f , gi et les hj sont continûment
différentiables dans un voisinage de x∗ et que les contraintes sont qualifiées en x∗ . Alors une
condition nécessaire pour qu’il soit une solution optimale locale de (P ) est que :


 ∃ λ∗i ≥ 0, i = 1, · · · , p, µ∗j ∈ R, j = 1, · · · , q








 tels que

 ∑ ∑

 ∇f (x∗ ) + pi=1 λ∗i ∇gi (x∗ ) + qj=1 µ∗j ∇hj (x∗ ) = 0,






 ∗
λi gi (x∗ ) = 0, i = 1, · · · , p.

Dans le cas convexe la condition nécessaire devient aussi suffisante.

Théorème 3.2.13 (CNS d’optimalité de Kuhn-Tucker)

Soit x∗ ∈ C. On suppose que les fonctions f , gi sont convexes et continûment différentiables
dans un voisinage de x∗ , les hj sont affines linéairement independantes et que les contraintes sont

39
qualifiées en x∗ . Alors x∗ est une solution optimale globale de (P ) si et seulement si :


 ∃ λ∗i ≥ 0, i = 1, · · · , p, µ∗j ∈ R, j = 1, · · · , q








 tels que

 ∑p ∑q

 ∇f (x ∗
) + λ ∗
∇g (x ∗
) + ∗ ∗
j=1 µj ∇hj (x ) = 0,

 i=1 i i




 ∗
λi gi (x∗ ) = 0, i = 1, · · · , p.

Comme dans les cas précédents, on définit la fonction de Lagrange.

Définition 3.2.6 On appelle lagrangien associé au problème (P ) avec containtes d’égalité et

d’inégalité, c’est-à-dire

min [f (x) : gi (x) ≤ 0, i = 1, · · · , p, hj (x) = 0, j = 1, · · · , q]

la fonction
L : Rn × Rp+ × Rq −→ R
∑ ∑
(x, λ, µ) 7−→ f (x) + pi=1 λi gi (x) + qj=1 µj hj (x).

On montre alors

Proposition 3.2.16 Soit x∗ ∈ C, on suppose que les fonctions f , les gi et les hj sont continûment
différentiables dans un voisinage de x∗ et que les contraintes sont qualifiées en x∗ . Alors une
condition nécessaire pour qu’il soit une solution optimale locale de (P ) est :

 ∗ ∗
 ∃ λ ∈ R+ , µj ∈ R, j = 1, · · · , q tel que :
p

∇x L(x∗ , λ∗ , µ∗ ) = 0

 λ∗ g (x∗ ) = 0, ∀ i ∈ {1, · · · , p}.
i i

On obtient aussi à l’aide du lagrangien des conditions du second ordre.

40