Ecole nationale des sciences et des technologies avancée Borj Cedria
Chapitre 1 : Optimisation sans contraintes
H. Ben Majdouba
Janvier 2023
Introduction :
L'optimisation est une branche des mathématiques, dont le but est de
trouver analytiquement ou numériquement, la meilleur solution
(l'optimale) à un problème donné.
De nos jours, l'optimisation joue un rôle très important dans différents
domaines de la vie.
• Transport et livraisons.
• Fabrication et production.
• Agriculture et génie civil.
• Finance, vente et marketing
• Gestion de stock
• Recherche et gestion des bases de données.
En optimisation, on parle de la fonction coût (objectif). C'est
la fonction à minimiser/maximiser, après formulation
mathématique du problème. On distingue deux grandes
familles de techniques d'optimisation, et cela suivant le
problème posé :
• Techniques d'optimisation sans contraintes.
• Techniques d'optimisation sous contraintes.
Définition :
Un problème d’optimisation s’écrit généralement sous la forme
suivante :
trouver x *
tel que
f x *
f x , x
Autrement dit, f x min f x
*
x
Avec f : IR n
IR une fonction continue
f est appelée fonction objectif
Condition nécessaire d’optimalité
Théorème :
n
Soit la fonction f : IR IR différentiable sur IR si f a un minimum local
n
( ou maximum local ) au point x * alors :
f x * 0
Rappel : le gradient d’une fonction f x1 , x2 , ... , xn à plusieurs
f
Variables est le vecteurs de composantes les dérivées partielles x i 1, 2,..., n
i
f
x
1
C’est-à-dire , f
f
xn
Points critiques
Définition :
Soit f : IR n IR différentiable. Tout point x IR n vérifiant :
f x 0
est appelé point critique de f .
Exemples :
• La fonction x x 2 admet un point critique en x = 0 qui est aussi un
minimum local.
• La fonction x x 1 admet un point critique en x = 1 qui est aussi un
2
maximum local.
• La fonction x x 3 admet un point critique en x = 0 qui n’est ni un
minimum local, ni un maximum local.
Exemple 1
On considère la fonction f x, y 1 x 2 y 2 définie sur IR²
Il est facile à deviner que f admet un minimum global en x0 , y0 0,0
Vérifions le théorème en montrant que ce point est un point critique de f.
On calcule donc les dérivées partielles :
f f
x, y 2 x , x, y 2 y
x y
f f
Donc : 0, 0 0 et 0, 0 0 ce qui confirme le théorème !
x y
Exemple 2
Cet exemple démontre qu’un point critique n’est pas toujours un extremum.
Soit f x, y 1 x 2 y 2 définie sur IR²
f f
On a : x, y 2 x et x, y 2 y
x y
f f
Donc : 0, 0 0 et 0, 0 0
x y
D’où x0 , y0 0,0 est un point critique de f.
Cependant, on voit clairement que ce point
ne correspond pas à un extremum.
On dit que 0, 0 est un point selle de f
Existence et unicité du minimum
Théorème : ( Existence )
Soit f : IR n IR une application et soit le problème P : minn f x
xIR
Si f est continue et coercive ( c’est-à-dire f x quand x )
Alors P admet au moins une solution .
Théorème : ( unicité )
Soit f : IR n IR une application et soit le problème P : minn f x
xIR
Si f est strictement convexe alors P admet au plus une solution.
Existence et unicité du minimum
Théorème (existence et unicité )
Soit f : IR IR et le problème
n
P : minn f x
xIR
Si f est continue, coercive et strictement convexe
Alors le problème P admet une unique solution.
Rappel ( convexité ) soit f : E IR n IR
• f est convexe ssi :
x, y E 2 , 0,1 , f x 1 y f x 1 f y
• f est strictement convexe ssi :
x, y E 2 , x y , 0,1 , f x 1 y f x 1 f y
Convexité
Théorème: ( caractérisation différentielle de la convexité)
Soit f : IR n IR de classe C 2 . On note H f sa matrice hessienne.
• Si H f est semi-définie positive pour tout x IR n , alors f est convexe.
• Si H f est définie positive pour tout x IR n , alors f est strictement
convexe.
La matrice hessienne de la fonction f est une matrice de dimension n n
dont les éléments sont les dérivées partielles d’ordre 2 de f .
2 f 2 f
x 2 x1xn
1
Hf
2
f f
2
x x xn 2
n 1
Exemple
• Soit f x, y x xy y et le problème
2 2
P : xmin
, y IR
2
f x, y
Montrer que le problème (P) admet une unique solution et déterminer
cette solution.
• f est continue est coercive car :
1
1
x, y
2
2 xy x 2 y 2 xy x 2
y 2
donc f x , y
2 2
d’où l’existence de la solution de (P)
2 1
• La matrice hessienne de f est H f qui est définie positive car ses
1 2
valeurs propres sont 1 et 3 d’où l’unicité de la solution de (P)
• La solution de (P) vérifie l’équation :
2 x y 0
f x, y 0 x, y 0,0
2 y x 0
Problème d’optimisation quadratique
Définition :
n
On appelle fonction quadratique une fonction de IR dans IR définie par :
1
f x Ax, x b, x c
2
Où A M n IR , b IR n et c IR
1 2 1 2 3 2
Exemple : f x, y , z x y z xz yz x y z
2 2 2
1 0 1 x x 1 x
1
f x, y, z 0 1 1 y , y 1 , y
2 1 1 3 z z 1 z
1 0 1 1
Donc f est quadratique avec A 0 1 1 et b 1
1 1 3 1
Problème de minimisation quadratique
Proposition :
1
Soit f une fonction quadratique tel que f x Ax, x b, x c
2
Si A est symétrique définie et positive alors le problème quadratique
P : min
xIR
n
f x admet une unique solution x * vérifiant : A x* b
Exemple : Soit f x, y, z x y z xy yz 3x y 2 z
2 2 2
3
Montre que f admet un unique minimum sur IR . Calculer le minimum de f
2 1 0 x x 3 x
1
f x, y , z 1 2 1 y , y 1 , y
2 2 z
0 1 2 z z
Donc f est quadratique avec :
2 1 0 3
A 1 2 1 et b 1
0 1 2 2
Problème de minimisation quadratique
2 1 0
2 1 1 1
det A I 3 1 2 1 2
1 2 0 2
0 1 2
2 2 1 2 2 2 2 2 2
2
Donc les valeurs propres de A sont : 1 2 , 2 2 2 et 3 2 2
Qui sont toutes strictement positives donc A est symétrique définie positive
D’où f admet un unique minimum solution de l’équation :
x 2x y 3 2 x y 3
A y b x 2 y z 1 x 2 y z 1
z y 2z 2 y 2 z 2
5
Donc le minimum de f est atteint au point : 4
1
2
5
4
Algorithmes de descente
Définition : soit f : IR n IR une fonction, et soit x IR .
n
On dit que d IR n \ 0 est une direction de descente de f en x s’il existe 0 0
tel que :
f x d f x , 0, 0
Ainsi une méthode de descente pour la recherche de x * solution du problème
P : min
xIR
n
f x consiste à construire x
k
kIN
de la manière suivante :
(1) Initialisation de x 0 IR n
(2) Itération k ( k 0 )
k
(i) On cherche d direction de descente en x k
(ii) On calcule x
k 1
x k k d k avec k 0 ( le pas de descente )
Caractérisation des directions de descente
Proposition : Soit f : IR IR une fonction différentiable ,
n
x IR n et d IR n \ 0 .
(1) Si d est une direction de descente en x alors : f x , d 0
(2) Si f x 0 alors d f x est une direction de descente en x.
Algorithme du gradient à pas fixe
La méthode du gradient à pas fixe 0 consiste à choisir comme direction à
l’étape k+1 , d
k 1
f x k ainsi l’algorithme s’écrit comme suit :
Initialisation : x 0 IR n
Pour k 0 : x k 1
x k
f x k
Exemple : f x, y ln x 2 y 2 1
En prenant x0 , y0 1,1 donner trois itérations de l’algorithme du gradient
à pas fixe 0,5
2x xk
x2 y 2 1 x 2 y 2 1
x
f x , y donc X k 1 X k f X k k k k
2y yk yk
x2 y 2 1 2
k
x y k
2
1
Algorithme du gradient à pas fixe
1
x
k (1 )
xk 2 yk 2 1
D’où X k 1
1
yk (1 x 2 y 2 1)
k k
1
x (1 )
0 x0 2 y0 2 1 3
2
Et par suite : X 1
1 2
0
y (1 ) 3
x0
2
y 0
2
1
1
x12 y12 1 51
x
1 (1 ) 16
X 2
1 16
1
y (1 ) 51
x1
2
y 1
2
1
1
x (1 )
x2 y2 1 0.05
2 2 2
X 3
1 0.05
y2 (1 x 2 y 2 1)
2 2
Algorithme du gradient à pas fixe
0
Données : Un point initial x , un seuil de tolérance 0 et un pas fixe 0
Résultat : Un point x IR n proche de x*
Initialiser x :
x x 0
k 0
tant que f x faire
Mettre à jour x avec le pas fixe dans la direction de descente f x
k
x x f x
k k 1
Fin
Remarques : les conditions d’arrêt qu’on peut définir sont :
(1) f x k où est le seuil de tolérance
(2) x k 1 x k précision tolérée
Algorithme du gradient à pas optimal
L’idée de l’algorithme du gradient à pas optimal est d’essayer de calculer à
chaque itération le pas k qui minimise la fonction
f x k d k
Donc le calcul du pas k revient à chercher tel que :
f x d f x r d , r IR
Initialisation : x 0 IR n
Pour k 0 : On cherche k qui min imise la fonction
f x k f x k
x k 1
x k
k
f x k
Algorithme du gradient à pas optimal
Exemple : f x, y 4 x 2 6 y 2 6 xy 3x 4 y 6
En prenant X 0 0, 0 donner la première itération de l’algorithme du
gradient à pas optimal,
8x 6 y 3
f x , y
12 y 6 x 4
3 0
X 1
X 0
0 f X 0
4 0
où 0 minimise la fonction
f 3 , 4 204 2 25 6
25
' 408 25 0 0, 0613
408
0,1838
D’où X 1
0, 245
Algorithmes du gradient pour une fonction quadratique
1
Proposition : Si f x Ax, x b, x c où A est une matrice
2
symétrique définie positive, alors la méthode du gradient à pas fixe
converge ssi le pas 0, 2 où A Sup i
A Sp A
i
Exemple : f x, y 4 x 2 6 y 2 6 xy 3x 4 y 6
Pour quelles valeurs du pas on a convergence de l’algorithme du gradient à
pas fixe ?
1 x 8 6 3
f x, y AX , X b, X c où X , A , b et c 6
2 y 6 12 4
8 6
det A I 2 8 12 36 2 20 60
6 12
Donc
Sp A 10 2 10 , 10 2 10
2
D’où l’algorithme du gradient à pas fixe converge ssi 0,
10 2 10
Algorithmes du gradient pour une fonction quadratique
1
Proposition : Si f x Ax, x b, x c où A est une matrice
2
symétrique définie positive, alors le pas optimal k à l’itération k pour
l’algorithme du gradient à pas optimal est donné par :
Ax k b , d k
k k
Ad , d k
où d k f x k
Exemple : f x, y 3 x 2 3 y 2 2 xy x y
2 2
En prenant X 0, 0 donner la première itération de l’algorithme du
0
gradient à pas optimal,
3 2 1
f est une fonction quadratique avec A et b
2 3 1
3 x 2 y 1 1
f x , y donc d f 0, 0
0
3 y 2 x 1 1
Algorithmes du gradient pour une fonction quadratique
Ax 0 b , d 0
Donc 0
Ad 0 , d 0
3 2 0 1 1
Ax 0
b donc Ax 0 b , d 0 2
2 3 0 1 1
0 3 2 1 5
et Ad donc Ad 0 , d 0 10
2 3 1 5
2
d ' où 0 0, 2
10
0, 2
1
x x 0
0 f x 0
0, 2
Algorithme de Newton
Généralement, les méthodes de gradient ne sont pas très performantes parce
qu'elles ne tiennent pas compte de la courbure ( ou de la Hessienne ) qui est
une information de second ordre.
Méthode de Newton :
Initialisation : x 0 IR n
1
k 1 k k
Pour k 0 : x x H f ( x ) f x k
En pratique, lorsque la matrice Hessienne est de très grande taille et mal
conditionnée, le calcul de son inverse est un peut difficile, donc on peut
utiliser la méthode suivante :
x k 1 x k d k
où d k est l'unique solution du système linéaire : H f ( x k ) d k f x k
d k est appelée direction de Newton
Algorithme de descente de gradient à pas fixe
