OPTIMISATION

I. Rappels sur les matrices

1 .Mineurs principaux Soit A  ai j  une matrice carrée d’ordre n.

 Les 2n-1 mineurs principaux de A sont les déterminants des sous-matrices Mp , où Mp est une
matrice obtenue en supprimant n-p lignes et n-p colonnes de A.
 Les mineurs diagonaux principaux de A sont les déterminants de A p, pour p=1,2,…….,n.
Ap est obtenue en supprimant les n-p lignes et les n-p colonnes de A.

 a11 a12 a13 

  a a 
Exemple : Les mineurs diagonaux principaux de A   a21 a22 a23  sont : a11 , dét 11 12  et détA
a a a   a21 a22 
 31 32 33 
2. Définition et notation Soit 𝑓 une fonction de Rn vers R de classe C2, notons :

f
 ( x0 ) pour i=1,……,n les dérivées partielles de f en x0.
xi

 f ( x0 ) la matrice colonne du gradient de f en x0, vecteur des dérivées partielles en x0.

 Df ( x0 ) , la jacobienne de f en x0, matrice ligne des dérivées partielles en x 0.
 D f ( x0 ) ,
2
la hessienne de f en x0, matrice ligne des dérivées partielles secondes en x 0.

II. Optimisation sans contrainte

1. Optimisation de fonctions d’une variable réelle
a. Extrémum Considérons la représentation graphique d’une fonction 𝑓 définie sur [𝑎, 𝑒]

a b c d e

La fonction 𝑓 admet un minimum local en c, elle admet un maximum local en b et en d.

𝑓 admet un minimum absolu en c et un maximum absolu en d.
On appelle extrémum un minimum ou un maximum.

b. Détermination d’un extrémum

Soit une fonction f : R  R . On considère le problème suivant : ( P) : max f ( x)
xR

i. Condition du premier ordre.

Si x0 est une solution de (P) alors f ' ( x0 )  0 .
ii. Condition du second ordre pour un optimum local.

Supposons que x0 vérifie la condition du premier ordre c'est-à-dire f ' ( x0 )  0 .

 Si x0 est un maximum local alors f ' ' ( x0 )  0 .

 Si f ' ' ( x0 )  0 alors x0 est un maximum local.
 Si x0 est un minimum local alors f ' ' ( x0 )  0 .
 Si f ' ' ( x0 )  0 alors x0 est un minimum local.
iii. condition suffisante du second ordre pour un optimum global

1
 Supposons que x0 vérifie les conditions du premier ordre, alors :

 Si pour tout x, f ' ' ( x)  0 ( est concave) alors x0 est un maximum global.
 Si pour tout x, f ' ' ( x)  0 (𝑓 est convexe) alors x0 est un minimum global.
c. Exercices :
Exercice 1
1) soit 𝑓 la fonction définie sur ℝ par 𝑓 (𝑥) = 𝑥 3 − 3𝑥 2 − 9𝑥 + 5.
Déterminer les extréma de 𝑓.
2) On considère la fonction 𝑔 définie par 𝑔(𝑥) = 𝑥 4 + 4𝑥 − 5.
Démontrer que 𝑔 admet un minimum global.

Exercice 2 Un fabricant de postes de télévision produit q postes par semaine à un coût total de
𝐶 = 6𝑞2 + 80𝑞 + 200. C’est un monopoleur et son prix s’exprime par la relation 𝑝 = 1080 − 4𝑞.
Montrons que le bénéfice net maximum est atteint lorsque la production est de 50 postes par semaine .
2. Optimisation d’une fonction à plusieurs variables.

a. Cas d’une fonction à deux variables

Soit U un ouvert contenu dans ℝ2 et 𝑓: 𝑈 → ℝ, de classe C2 telle que ∇𝑓(𝑥0 , 𝑦0 ) = 0 avec (𝑥0 , 𝑦0 ) ∈ 𝑈.
𝜕2 𝑓 𝜕2 𝑓 𝜕2 𝑓
Posons : 𝑟 = 𝜕𝑥 2 (𝑥0 , 𝑦0 ) , 𝑡 = 𝜕𝑦2 (𝑥0 , 𝑦0 ) et 𝑠 = 𝜕𝑥𝜕𝑦 (𝑥0 , 𝑦0 ).

Propriété
 Si 𝑟𝑡 − 𝑠 2 > 0 𝑒𝑡 𝑟 > 0 , 𝑓 admet un minimum local en (𝑥0 , 𝑦0 ).
 Si 𝑟𝑡 − 𝑠 2 > 0 𝑒𝑡 𝑟 < 0 , 𝑓 admet un maximum local en (𝑥0 , 𝑦0 ).
 Si 𝑟𝑡 − 𝑠 2 < 0, 𝑓 n’admet ni maximum ni minimum en (𝑥0 , 𝑦0 ), on dit qu’on a un point selle.
 Si 𝑟𝑡 − 𝑠 2 = 0, on ne peut pas conclure.
Exercice
Soit 𝑓 la fonction définie sur ℝ2 par 𝑓(𝑥, 𝑦) = 4𝑥 2 − 𝑥𝑦 + 𝑦 2 − 𝑥 3 .
Déterminer les points critiques de 𝑓 puis préciser leurs natures.
b. Cas général
Soit une fonction 𝑓: ℝ → ℝ. 𝑓: ℝ𝑛 → ℝ
On considère le problème suivant : ( P) : max f ( x)
xRn

i. Condition du premier ordre.

Si 𝑥 ∗ est une solution de (P) , alors x * vérifie : f ( x* )  0
ii. Condition du second ordre pour un optimum local.
Supposons que 𝑥 ∗ vérifie la condition du premier ordre c'est-à-dire f ( x* )  0 .
 Si 𝐷2 𝑓 (𝑥 ∗ ) est définie négative alors 𝑥 ∗ est un maximum local .
 Si 𝑥 ∗ est un maximum local alors est semi-définie négative.
 Si 𝐷2 𝑓 (𝑥 ∗ ) est définie positive alors 𝑥 ∗ est un minimum local .
 Si 𝑥 ∗ est un minimum local alors 𝐷2 𝑓 (𝑥 ∗ ) est semi-définie positive.
iii. condition suffisante du second ordre pour un optimum global
Supposons qu’il existe 𝑥 ∗ qui vérifie les conditions du premier ordre, alors :

2
Si D f ( x) est semi-définie négative pour tout x (f est concave) alors 𝑥 ∗ est un maximum
global.

2
Si D f ( x) est semi-définie positive pour tout x (f est convexe) alors 𝑥 ∗ est un minimum
global.
Exemple : On considère la fonction définie par 𝑓 (𝑥1 , 𝑥2 ) = 3𝑥1 𝑥2 − 𝑥13 − 𝑥23 .

Déterminer les extréma de 𝑓.

2
III. Optimisation sous contrainte prenant la forme d’égalités

On se propose de déterminer les extréma de la fonction 𝑓: ℝ𝑛 → ℝ sous la contrainte (𝑥) = 𝑐 , 𝑔 étant

une fonction de ℝ𝑛 → ℝ. (P)

1. Cas d’une contrainte d’égalité :

a. Lagrangien

On appelle lagrangien, la fonction notée L, définie par : L( x,  )  f ( x)   ( g ( x)  c) .

 est le multiplicateur de Lagrange associé à la contrainte.

b. Condition de qualification de la contrainte.

Pour utiliser le Lagrangien, pour résoudre un problème d’optimisation sous une contrainte en équation, il
suffit que l’une des deux conditions suivantes soit vérifiée.

f
(1) Les dérivées partielles de g, évaluées à l’optimum x * ne soient pas simultanément nuls ( x* )  0
xi
pour au moins un i.
(2) La fonction contrainte g est linéaire.
c. Condition du premier ordre.

On suppose que la contrainte de qualification est vérifiée. Si x * est une solution du problème (P) ,

alors il existe un unique  tel que :

*

 L * *
 x i ( x ,  )  0, i  1,........,n
 .
 L  0
 *

d. Matrice hersienne bordée du Lagrangien

On appelle matrice hessienne bordée du Lagrangien évalué au point x *, la matrice notée H L ( x* ) définie
 g g 
0 ........................................... 
 x1 xn 
 
 g  L  L 
2 2
..........
...............................
 x1 x12 x1 n 
 
. . 
H L ( x)   . . 
par :  
 
 
 . . 
 g L 2L 
 ......................................... 2 
 xn xn x1 xn 
 
 

e. Condition suffisantes du second ordre pour un optimum local.

Supposons qu’il existe un x * qui vérifie les c.p.o.
 Les n-1 derniers mineurs principaux diagonaux de H L ( x ,  ) évalués à l’optimum sont
* *

n *
alternativement >0 et <0, le dernier d’entre eux étant du signe de (1) , alors x est un
maximum local.

3
  Les n-1 derniers mineurs principaux diagonaux de H L ( x ,  ) évalués à l’optimum sont tous<0,
* *

*
alors x est un minimum local.
f. Condition suffisantes du second ordre pour un optimum global.
Supposons qu’il existe un x * qui vérifie les c.p.o.

*
Si le Lagrangien L est une fonction convexe alors x est un minimum global.
 Si le Lagrangien L est une fonction concave alors x est un maximum global.
*

g. Exemples
Exemple 1 On veut optimiser f ( x, y)  xy  3xy sous la contrainte
2

g ( x, y)  x  y  3  0
1. Ecrire le Lagrangien L associé à ce problème d’optimisation.
2. Ecrire les contraintes du premier ordre associées à ce problème.
3. Trouver le ou les points critiques.
4. Déterminer la nature du ou des points critiques.

Exemple 2 On veut optimiser la fonction

𝑓(𝑥1 , 𝑥2 , 𝑥3 ) = 4𝑥12 + 2𝑥22 + 𝑥32 − 2𝑥1 𝑥2 + 𝑥2 𝑥3 − 30𝑥2 − 30𝑥3

sous la contrainte 𝑥1 + 𝑥2 + 𝑥3 = 100.

a) Ecrire le lagrangien associé à ce problème d’optimisation.

b) Ecrire les conditions du premier ordre associées à ce problème d’optimisation,

c) Montrer que nous avons un seul point critique dont les composantes sont

𝑥1 = 20, 𝑥2 = 30 𝑒𝑡 𝑥3 = 50
d) Déterminer la nature de ce point critique.

2. Cas de m contraintes
max 𝑓(𝑥)
Considérons le problème (𝑃 ) { 𝑥∈ℝ𝑛
𝑠. 𝑐. 𝑔𝑗 (𝑥) = 𝑐𝑗 , 𝑗=1,2,…,𝑚
m
Le lagrangien est L ( x,  )  f ( x )   ( g j ( x )  c j ) avec   (1 ,..........,  j )
j 1

a. Condition de qualification de la contrainte.

Pour pouvoir utiliser le Lagrangien, l’une des conditions suivantes doit être vérifiée.

 La matrice jacobienne des fonctions contraintes gj, j=1, ,m de taille (m,n) est de rang m
lorsqu’elle est évaluée à l’optimum x * .
 Les fonctions contraintes sont toutes linéaires.
b. Condition du premier ordre.

On suppose que la contrainte de qualification est vérifiée. Si x*  ( x1* ,...........xn* ) est une solution du
alors il existe un unique  tel q
*
problème (P) ,

 L * *
 x ( x ,  )  0, i  1,........,n
 i
ue :  .
 L( x ,  )  0 j  1,.........., n.
* *

 *j

4
 c. Matrice hersienne bordée du Lagrangien

On appelle matrice hessienne bordée du Lagrangien évalué au point ( x* , * ) , notée H L ( x* , * ) est définie
par :
 g1 g1 g 
 0.............................................0 ............................................. 1 
  x1  x 2  xn 
. 
 
. 
 
. 
 g m g m g 
 0..............................................0 ........................................... m 
 x1  x 2 xn 
 
g g 2  L
2
2L
H L ( x)   1 ......................................... ..........
....................................... 
 x1 x1 x12 x1xn 
 
. . 
. . 
 
 
 
 . . 
 g g 2L 2L 
 1 2 ............................................. ............................................. 2 
 xn xn x1xn xn 
 
 

d. Condition suffisantes du second ordre pour un optimum local.

Supposons qu’il existe un x * qui vérifie les c.p.o.
 Les n-m derniers mineurs principaux diagonaux de H L ( x ,  ) évalués à l’optimum sont
* *

n *
alternativement >0 et <0, le dernier d’entre eux étant du signe de (1) , alors x est un
maximum local.
 Les n-m derniers mineurs principaux diagonaux de H L ( x ,  ) évalués à l’optimum sont tous du
* *

*
signe de (-1)m, alors x est un minimum local.
e. Condition suffisantes du second ordre pour un optimum global.
Supposons qu’il existe un x * qui vérifie les c.p.o.

*
Si le Lagrangien L est une fonction convexe alors x est un minimum global.
 Si le Lagrangien L est une fonction concave alors x est un maximum global.
*

Exemple Résoudre le programme de minimisation :

min Z  x1  x2  x3
 2
 x1  x2  3
 x  3x  2 x  7
 1 2 3

f.