Faculté des Sciences Économiques et Sociales - Université de Lille

Licence 3 MISEG
Optimisation

Optimisation des fonctions de plusieurs variables

V. Ledda

23 juin 2018

Table des matières

FT
1 Rappels sur les fonctions différentiables de n variables

2 Optimisation libre
2.1 Condition nécessaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Conditions du second ordre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2

4
4
4
RA
3 Optimisation d’une fonction sous contrainte d’égalités 5
3.1 Présentation du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.2 Condition du premier ordre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.3 Conditions du second ordre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

4 Optimisation d’une fonction sous contrainte d’inégalités 8

4.1 Vocabulaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.2 Conditions nécessaires pour un optimum local . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.3 Condition suffisante d’optimalité globale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.4 Conditions du second ordre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
D
 Optimisation des fonctions de plusieurs variables Chapitre 3

Le cas de d’un optimum libre d’une fonction de deux variables et le cas d’un optimum d’une fonction de
deux variables soumis à une contrainte a été précédemment. Dans ce chapitre on généralise les résultats
obtenus au chapitre 2. La généralisation se fait sans problème au prix d’un alourdissement des notations
et du remplacement des conditions de non nullité de la différentielle par des conditions sur le rang de la
matrice jacobienne des contraintes.

1 Rappels sur les fonctions différentiables de n variables

q
Rn : ||X|| = x12 + x22 + · · · + xn2 .

FT
On travaille avec la norme euclidienne sur

Définition 1. Soit f une fonction réelle de n variables réelles définie sur l’ensemble D à valeur réelle et A un
point de Rn .
On dit que f tend vers ` lorsque X tend vers A, (X restant dans D) si :

lim |f (X) − `| = 0 ou lim |f (X) − `| = 0

d(X,A)→0 kX−Ak→0
X∈D X∈D
RA
Définition 2. Soit f une fonction définie sur un sous-ensemble D de Rn et A ∈ D.
On dit que f est continue en A si f (X) tend vers f (A) quand X tend vers A, soit encore lim f (X) = f (A).
X→A
X∈D
On dit que f est continue sur D si f est continue en tout point de D.

Définition 3. Soit f une fonction définie sur un ensemble D de Rn et A ∈ D.

f est différentiable en A si il existe une forme linéaire sur Rn , L, telle que :

D

∀H ∈ Rn tel que A + H ∈ D, f (A + H) = f (A) + L · H + kHkε(H) où lim ε(H) = 0

kHk→0

La forme linéaire L est appelée “différentielle de f en A”. On la note dfA .

On a donc f (A + H) = f (A)+ dfA (H) + kHkε(H) où lim ε(H) = 0.

kHk→0

Définition 4. Soit f une fonction de D ⊂ Rn dans R.

€f f (a ,a ,··· ,a +h,··· ,an )−f (A)
Pour tout indice i ∈ ~1; n, on note, sous réserve d’existence, €x (A) = limh→0 1 2 i h . Ce nombre
i
est la différentielle partielle de f en A suivant la variable xi . Lorsque les n dérivées partielles existent en A (f
est alors dérivable en A), on appelle gradient de f en A le vecteur colonne formé par les n dérivées partielles en
A.
 €f 
 €x (A)
 1 
 €f
 €x (A)

−−−−→
grad fA =  2 . 

 .. 
 
 €f 
€xn
(A)

2 V. Ledda
 Optimisation des fonctions de plusieurs variables Chapitre 3

Proposition 1. Soit f une fonction différentiable en A ∈ D ⊂ Rn .

dfA : Rn −→ R
−−−−→
H 7−→ grad fA · t H

Définition 5. On dit qu’une fonction f est de classe C 1 sur D ⊂ Rn si l’application

FT
df : D −→ R
X 7−→ dfX

est continue.

n
O Théorème 1. Soit f une application de D ⊂ R dans R et A ∈ D . Si toutes les dérivées partielles de f en
RA
existent et sont continues en A alors f est de classe C 1 en A.

Définition 6. Soit f une fonction définie sur un ensemble D de Rn .

Si f admet des dérivées partielles secondes continues en un point A de D, on dit que f est deux fois continûment
différentiable en A ou encore que f est de classe C2 en A.

O Théorème 2 (Théorème de Schwartz). Soit f une fonction de classe C 2 en A.

D

€2 f €2 f
∀(i; j) ∈ ~1; n2 ; i , j; (A) = (X)
€xi €xj €xj €xi

Définition 7. Soit f une fonction de classe C 2 en A. La matrice carrée de Mn de terme général :

€2 f
(A)
€xi €xj
est appelée la matrice hessienne de f en A. On la note D2f (A). D’après le théorème de Schwartz cette matrice
est symétrique.

3 V. Ledda
 Optimisation des fonctions de plusieurs variables Chapitre 3

 
€2 f €2 f
 
 

2
(A) ··· ··· (A) 

 €x 1
€x1 €xn 
 
 
 
 .. .. 
. .
 
 
 

FT
 
 
.. €2 f ..
 
i 
 . (A) .  = D2 (A)

f

 €xi €xj 

 
 
 
 .. .. 

 . . 

 
 
€2 f €2 f
 
 
 €x €x (A) ··· ··· (A) 

2
 n 1 €xn 
RA
Remarque 1. Les définitions et résultats précédents ont été donnés localement en A. Ils s’étendent de
manière naturelle à un sous ensemble de D.

Proposition 2.
— Le caractère continue, C 1 , C 2 , etc. se conserve par somme, produit, quotient et composée.
— Toutes les fonctions polynômes et quotients de polynômes sont de classe C2 sur leur domaine de définition.

O Théorème 3 (Formule de Taylor à l’ordre 2 pour une fonction de n variables). Soit f une fonction définie
un ensemble D de Rn et A un point de D. Si f est de classe C2 en A, alors pour tout H ∈ Rn , tel que A + H ∈ D,
D

on a :
1t
f (A + H) = f (A)+ dfA · H + H · D2f (A) · H + ||H||2 ε(H)
2
avec lim ε (H) = 0
H→0

2 Optimisation libre
2.1 Condition nécessaire
n
O Théorème 4. Soit f une fonction différentiable sur ouvert D ⊂ R et A un élément de D.
Si f admet un extremum en A alors dfA = 0. On dit que A est un point critique de f .

2.2 Conditions du second ordre

O Théorème 5. Soit f une fonction de classe C 2 sur un ouvert D ⊂ Rn et A ∈ D un point critique de f .

1. Si f admet un maximum en A alors ∀H ∈ Rn , t H · D2 (A) · H 60
f

2. Si ∀H ∈ Rn \{0}, t H · D2 (A) · H < 0 alors f admet un maximum local strict en A.

f

4 V. Ledda
 Optimisation des fonctions de plusieurs variables Chapitre 3

Remarque 2. Le théorème peut s’écrire dans les mêmes conditions pour un minimum local en renversant
les inégalités.
Le théorème (55) indique que l’étude du point critique A de f peut se ramener à l’étude de la forme
quadratique :
Q : Rn −→ R
H 7−→ t
H · D2f (A) · H

FT
L’algèbre linéaire permet de répondre de la manière suivante :
— Si les valeurs propres de D2f (A) sont toutes strictement positives alors f admet un minimum strict en
A
— Si les valeurs propres de D2f (A) sont toutes strictement négatives alors f admet un maximum strict en
A
— Si D2f (A) admet deux valeurs propres de signe opposés alors f admet un point selle en A.
— Si les valeurs propres sont toutes de même signe mais qu’au moins une est nulle alors dans le cas où il
existe H0 tel que H0 · D2f (A) · H0 les conditions du second ordre ne permettent pas de conclure.
RA
Définition 8. Soit M = (ai,j ) un éléments de Mn et i ∈ ~1; n. On note Mi la matrice carrée formée des i
premières lignes de M et des i premières colonnes de M. On appelle mineurs principaux de M la suite des n
déterminants suivants :
|M1 |, |M2 |, · · · , |Mn |

On peut alors reformuler le théorème (5

5) de la manière suivante :

Proposition 3. Soit f une fonction de classe C 2 sur un ouvert D ⊂ Rn et A ∈ D un point critique de f . On

note m1 , m2 , · · · , mn les mineurs principaux de D2f (A).
D

1. (a) Si f admet un minimum en A alors ∀i ∈ ~1; n, mi > 0

(b) Si f admet un maximum en A alors m1 6 0, m2 > 0, · · · , (−1)n mn > 0.
2. (a) Si m1 < 0, m2 > 0, · · · , (−1)n mn > 0 alors f admet un maximum local strict en A.
(b) Si ∀i ∈ ~1; n, mi > 0 alors f admet un minimum local strict en A.

3 Optimisation d’une fonction sous contrainte d’égalités

3.1 Présentation du problème
Dans cette partie on s’intéresse aux programmes de la forme :
(
ext f (X)
s.c. ∀i ∈ ~1 ; k gi (X) = 0
où les fonctions f , g1 , g2 , · · · , gk sont de classe C 1 sur un ouvert D ⊂ Rn .
On pose
L : Rn+k −→ R
k
X
(x1 ; x2 ; · · · ; xn ; λ1 ; λ2 ; · · · ; λk ) 7−→ f (x1 ; x2 ; · · · ; xk ) + λi g(x1 ; x2 ; · · · ; xk ) = f (X) + t Λ · G(X)
i=1

5 V. Ledda
 Optimisation des fonctions de plusieurs variables Chapitre 3

où Λ = t (λ1 , λ2 , · · · λk ) et

G : Rn −→ Rk
 
g1 (X)
g2 (X)
 
X 7−→  . 

 .. 
 
gk (X)

La fonction L est appelée le lagrangien de f et de G. Notons €G(A) la jacobienne de G en un point A de D.

FT
 €g1 €g1 
 €x (A) · · · ··· €xn
(A)
 1 
 . ..
 ..

 . 

 €gi 
€G(A) =  €xj
(A) 


 . .. 
 .. . 

 €gk €gk 
€x
(A) · · · ··· €xn
(A)
1
RA
3.2 Condition du premier ordre

O Théorème 6 (Théorème de Lagrange). Soit f une fonction de classe C 1 sur un ouvert D de Rn . Soit G une
application de classe C 1 de D vers Rk . On pose

L : Rn × Rk −→ R
(X; Λ) 7−→ f (X) + t Λ · G(X)

On suppose qu’il existe un point A ∈ D tel que :

D

— G(A) = 0
— rang(€G(A)) = k
Si f admet un extremum sous la contrainte G(X) = 0 en A alors il existe un élément ΛA ∈ Rk tel que
dL(A;ΛA ) = 0

3.3 Conditions du second ordre

6 V. Ledda
 Optimisation des fonctions de plusieurs variables Chapitre 3

O Théorème 7. Soit f une fonction de classe C 2 sur un ouvert D de Rn . Soit G une application de classe C 2 de
D vers Rk . On pose

L : Rn × Rk −→ R
(X; Λ) 7−→ f (X) + t Λ · G(X)

On suppose qu’il existe un point A ∈ D et un élément ΛA dans Rk tels que :

FT
— rang(€G(A)) = k
— dL(A;ΛA ) = 0
Dans ces conditions, en notant LA : X 7−→ L(X, ΛA ) on a les résultats suivants :
1. Si f admet un maximum local en A sous la contrainte G(X) = 0 alors

∀H ∈ Rk ; €G(A) · H = 0 ⇒ t H · D2LA · H 6 0 (1)

2. Si
∀H ∈ Rk \{0}; €G(A) · H = 0 ⇒ t H · D2LA · H < 0
RA
(2)
alors f admet un maximum local strict en A sous la contrainte G(X) = 0

En notant LΛ : X 7−→ L(X, Λ) posons

B : Rk × D −→ Rn+k
 
(Λ; X) 7−→ (G(X); dLΛ (X)) = t g1 (X), g2 (X), · · · gk (X) , fx01 (X) + t ΛG0x1 (X), · · · , fx0n (X) + t ΛG0xn (X)

Sous les hypothèse du théorème (7 7), l’application B est de classe C 1 et sa matrice jacobienne en (A; ΛA ) à la
D

forme suivante :
 
 0 0 
 0 ··· 0 g1 x 1 ··· g1 xn 
 
 
 .
.. .
.. .
.. .
.


 €G(A) . 

 
 0 0

 0 ··· 0 gk x1 ··· gk xn 

 
0 0 00 t 00 00 t 00
 
Hb (L, €G) =  g1 x1  ··· gk x1 fx2 (A) + ΛGx2 (A) ··· fx1 xn (A) + ΛGx1 xn (A) 
 1 1 

. .
 

 .
. .
.


 
.. t ..
 
 2 t 2

 . €G(A) . Df (A) + ΛD g (A) 

 


 .
.. .
..


 
 
 
00 00
 g 0
 1 xn ··· gk 0xn fx2 (A) + t ΛGx2 (A) ··· fx001 xn (A) + t ΛG00x1 xn (A) 
1 1

Cette matrice est la hessienne bordée de L en A.

7 V. Ledda
 Optimisation des fonctions de plusieurs variables Chapitre 3

Proposition 4. Sous les hypothèses du théorème (7 7), en notant mi les n − k derniers mineurs principaux de la
hessienne bordée de L en A, pour i ∈ ~k + 1 ; n.
1. Conditions suffisantes
(a) Si ∀i ∈ ~k + 1 ; n, (−1)k mi > 0 alors f admet un maximum local strict en A.
(b) Si∀i ∈ ~k + 1 ; n, (−1)i mi > 0 alors f admet un maximum local strict en A sous la contrainte
g(X) = 0.
2. Conditions nécessaires

FT
(a) Si f admet un minimum local en A sous la contrainte G(X) = 0 alors ∀i ∈ ~k +1 ; n, (−1)k mi > 0
(les n − k derniers mineurs sont du même signe que (−1)k .)
(b) Si f admet un maximum local en A sous la contrainte G(X) = 0 alors ∀i ∈ ~k +1 ; n, (−1)i mi > 0
(les n − k derniers mineurs sont de signes alternés et le dernier est du signe de (−1)n )

Remarque 3.
mk+1 = |H2k+1 |, mk+2 = |H2k+2 |, · · · , mn = |Hn+k |
Par exemple pour k = 3 et m = 5, il y a deux mineurs principaux à calculer.
RA
0 €G

t €G D2f + t ΛD2g
D

4 Optimisation d’une fonction sous contrainte d’inégalités

Dans cette partie on s’intéresse aux programmes de la forme :
(
ext f (X)
(3)
s.c. ∀i ∈ ~1 ; k gi (X) > 0
où les fonctions f , g1 , g2 , · · · , gk sont de classe C 1 sur un ouvert D ⊂ Rn .

4.1 Vocabulaire
L’ensemble des valeurs admissibles est l’ensemble des points de Rn où G(X) > 0. On cherchera donc des
solutions dans l’ensemble E = D ∩ {(x; y) ∈ Rn |G(X) > 0}.

Définition 9. La contrainte g(X) > 0 est dite serrée, ou effective ou encore active au point A ∈ D si g(A) = 0.
Lorsque g(A) > 0, on dit que la contrainte est relâchée en A. Enfin, la contrainte G(X) > 0 est dite qualifiée en
A si :
— soit G(A) > 0
— soit G(A) = 0 et rang(€G)(A) = k

8 V. Ledda
 Optimisation des fonctions de plusieurs variables Chapitre 3

4.2 Conditions nécessaires pour un optimum local

O Théorème 8 (Kuhn et Tucker). On considère le programme (3 3). Si f admet un maximum local en A sur E et
si la contrainte est qualifiée en A alors il existe un élément ΛA ∈ Rk tel que :
1. ΛA > 0
2. ∀i ∈ ~1 ; k, (ΛA )i × gi (A) = 0 dites relations d’exclusion
3. dfA + ΛA dGA = 0

FT
Remarque 4. Lorsque l’on cherche un minimum local la condition (1.) devient : ΛA 6 0.

Remarque 5.
1. Si (ΛA )i , 0 la relation d’exclusion implique que gi (A) = 0 donc la contrainte est serrée en A.
2. Si gi (A) > 0 alors (ΛA )i = 0 donc dans ΛA dGA seules interviennent les contraintes serrées.

4.3 Condition suffisante d’optimalité globale

Dans cette partie on suppose que les fonctions gi (i ∈ ~1 ; k) sont concaves sur D un ouvert convexe de Rn .
RA
Si de plus f est convexe (resp. concave) sur D les conditions du théorème (8 8) sont suffisantes pour montrer
que f admet un minimum (resp. un maximum) sous la contrainte G(X) > 0.

Proposition 5. Soit le programme

(
min f (X)
(4)
s.c. G(X) > 0
où f est une fonction convexe et de classe C 1 sur un ouvert convexe, D, de Rn et g est une fonction concave et
de classe C 1 sur D. S’il existe un point A de D et un vecteur ΛA ∈ Rk tel que
— la contrainte soit qualifiée en A
D

— ΛA 6 0
— ∀i ∈ ~1 ; k, (ΛA )i × gi (A) = 0
— dfA + ΛA · dGA = 0
alors f admet un minimum global sous la contrainte g(X) > 0 en A.

Proposition 6. Soit le programme

(
max f (x; y)
(5)
s.c. g(x; y) > 0
où f est une fonction concave et de classe C 1 sur un ouvert convexe, D, de Rn et les fonctions gi sont des
fonctions concaves et de classe C 1 sur D. S’il existe un point A de D et un vecteur ΛA ∈ Rk tel que
— la contrainte soit qualifiée en A
— ΛA > 0
— ∀i ∈ ~1 ; k, (ΛA )i × gi (A) = 0
— dfA + ΛA dgA = 0
alors f admet un maximum global sous la contrainte g(x; y) > 0 en A.

9 V. Ledda
 Optimisation des fonctions de plusieurs variables Chapitre 3

Exemple 1. 


max ln(x) + ln(y + 5)

s.c. x + y 6 4




y>0



Exemple 2. n o
max −(x − 4)2 − (y − 4)2





 (
 x+y 6 4
s.c.


FT


x + 3y 6 9


4.4 Conditions du second ordre

O Théorème 9. On considère le programme (3

3). Si la contrainte est qualifiée en A et qu’il existe un élément
k
ΛA ∈ R tel que :
1. ΛA > 0
RA
2. ∀i ∈ ~1 ; k, (ΛA )i × gi (A) = 0 dites relations d’exclusion
3. dfA + ΛA dGA = 0
On suppose en outre, sans perte de généralité, qu’uniquement les s premières contraintes sont serrées (s ∈
~1 ; k).
On désigne par H la matrice hessienne du lagrangien bordée par les dérivées premières des seules contraintes
saturées évaluée en (A; ΛA ). Cette matrice est symétrique d’ordre s + n. Et l’on note mi les n − s derniers mineurs
principaux de H, i ∈ ~s + 1 ; n.
1. Conditions suffisantes
(a) Si (−1)i mi > 0 pour i ∈ ~s + 1 ; n alors f admet un maximum local sous la contrainte G(X) > 0.
D

(b) Si (−1)s mi > 0 pour i ∈ ~s + 1 ; n alors f admet un minimum local sous la contrainte G(X) > 0.
2. Conditions nécessaires
(a) Si f admet un maximum local sous la contrainte G(X) > 0 alors (−1)i mi > 0 pour i ∈ ~s + 1 ; n.
(b) Si f admet un minimum local sous la contrainte G(X) > 0 alors (−1)s mi > 0 pour i ∈ ~s + 1 ; n.

Exemple 3.
Les points A( 13 ; 13 ) et B(0; −1) sont-ils des solutions du programme ci-dessous :

ext x2 + 2y 2





x2 + y 2 6 1
 (

s.c.



1 + x − 2y > 0
Exemple 4. Résoudre le programme suivant :



 ext xy + zt
 
2 2

x + y 6 2
 
 

s.c.
 z2 + t2 > 8

 



10 V. Ledda