Optimisation

AMAL Youssef

ENSAT
Google Classroom: kzgrskw
yamal@[Link]

1445/2023
 Plan du Cours

Introduction
Existence et unicité de minimum
Algorithmes de minimisation sans contraintes
Algorithmes de minimisation avec contraintes
Calculs par le logiciel R
Référence Recommandée :
Numerical Optimization by Jorge Nocedal et Stephen Wright.

AMAL Youssef Statistique pour Ingénieurs 1445/2023 2 / 30

 Introduction Généralités

L’optimisation consiste en la recherche du minimum (ou du maximum)

d’une certaine quantité sans ou avec contraintes :

(P ) inf f (x)
x∈C

On dit que problème (P ) admet une solution s’il existe x0 ∈ C tel que

∀x ∈ C, f (x0 ) ≤ f (x)

Dans ce cas, f (x0 ) = inf f (x) est un minimum de f sur C.

x∈C
Les valeurs maximales de fonctions f sont obtenues en remplacant f par
−f :
sup f (x) = inf f (x)
x∈C x∈C

AMAL Youssef Statistique pour Ingénieurs 1445/2023 3 / 30

 Introduction Généralités

Exemple : Une entreprise de production d’ordinateurs de types : laptops

et ordinateurs de bureau. Les laptops se vendent à 10M Dhs chacun, tan-
dis que les ordinateurs de bureau se vendent à 16M Dhs chacun. Cepen-
dant, la production de ces ordinateurs nécessite des ressources limitées
en composants techniques.


 max(10M x1 + 16M x2 )

contraintes :




Modèle Mathématique : x1 + x2 ≤ 400

x1 + 2x2 ≤ 600





x1 , x2 > 0

où x1 et x2 sont les quantités respectives de laptops et d’ordinateurs de
bureau à produire.
Objectif : Maximiser les revenus de la production d’ordinateurs porta-
bles et de bureau, en respectant les limitations des ressources disponibles.

AMAL Youssef Statistique pour Ingénieurs 1445/2023 4 / 30

 Introduction Contexte

Existence et Unicité du minimum,

liée à la continuité,
liée à la convexité (stricte).
Résolution du problème :
Étude analytique,
Étude approchée par méthodes numériques.

AMAL Youssef Statistique pour Ingénieurs 1445/2023 5 / 30

Existence et unicité de minimum Rappels de calculs différentiels

On se place dans RN muni de la norme euclidienne ∥.∥ et du produit

scalaire ⟨., .⟩ avec ⟨x, x⟩ = ∥x∥2 .
Soit U ⊂ RN un ouvert et f : U → R une application scalaire. Soit
a ∈ U.
On dit que f est différentiable au point a s’il existe une application
linéaire dfa ∈ L(RN , R) tels que ∃α > 0, ∀∥h∥ ≤ α,

f (a + h) = f (a) + dfa (h) + ∥h∥ε(h)

avec lim ε(h) = 0.

h→0

AMAL Youssef Statistique pour Ingénieurs 1445/2023 6 / 30

Existence et unicité de minimum Rappels de calculs différentiels

Formule de Taylor - Young à l’ordre 2 :

n n X n
X ∂f X ∂2f
f (a + h) = f (a) + hi (a) + hi hj (a) + o(∥h∥2 )
i=1
∂xi i=1 j=1
∂xi ∂xj

Pn ∂f
où ⟨∇f (a), h⟩ = i=1 hi (a)
∂xi
Pn Pn ∂2f
et i=1 j=1 hi hj (a) =t [Link] (a).h
∂xi ∂xj

AMAL Youssef Statistique pour Ingénieurs 1445/2023 7 / 30

Existence et unicité de minimum Minimum local / global

Soit x0 ∈ K. On dit que la fonction f admet

un minimum global sur K au point x0 , si

∀x ∈ K, f (x0 ) ≤ f (x)

un minimum local sur K au point x0 , si

∃r > 0, x ∈ B(x0 , r) ∩ K, f (x0 ) ≤ f (x).

AMAL Youssef Statistique pour Ingénieurs 1445/2023 8 / 30

Existence et unicité de minimum Existence de minimum liée à la continuité

Soit K un compact de RN et f : K → R une application continue sur

K. Alors f est bornée et atteint ses bornes :

∃x0 ∈ K tel que inf f (x) = f (x0 )

x∈K

Contre-exemples:
Soient X = R et f (x) = x2 + 1 sur R∗ et f (0) = 3, on a inf f (x) =?
x∈R
Soient X =]0; 1] et f (x) = x2 + 1, on a inf f (x) =?
x∈R

AMAL Youssef Statistique pour Ingénieurs 1445/2023 9 / 30

Existence et unicité de minimum Existence de minimum liée à la continuité

Fonctions coercives : Une fonction f : Rn → R est dite coercive si

lim f (x) = +∞.
∥x∥→+∞

Soient U une partie non vide fermée non bornée de Rn et f : Rn → R

une fonction coercive et continue. Alors il existe au moins un élément
x0 ∈ U tel que inf f (x) = f (x0 ).
x∈U
[Link] : Soit X = R et f (x) = −x2 , alors inf f (x) =?
x∈R

AMAL Youssef Statistique pour Ingénieurs 1445/2023 10 / 30

Existence et unicité de minimum Critère de convexité

Soit K ⊂ RN . L’ensemble X est dite convexe si :

∀(x, y) ∈ K 2 , ∀t ∈ [0, 1] tels que tx + (1 − t)y ∈ K

Exemple : RN est un convexe.

Soit K ⊂ RN convexe et f : K → R.
f est dite convexe si :

∀(x, y) ∈ K 2 , ∀t ∈]0, 1[, f (tx + (1 − t)y) ≤ tf (x) + (1 − t)f (y)

f est dite strictement convexe si :

∀(x, y) ∈ K 2 , x ̸= y, ∀t ∈]0, 1[, f (tx+(1−t)y) < tf (x)+(1−t)f (y)

Exemple : toute fonction affine, f (x) = ax + b, est convexe mais non

strictement convexe.
AMAL Youssef Statistique pour Ingénieurs 1445/2023 11 / 30
Existence et unicité de minimum Critère de convexité

Critéres de convexité : On suppose que f est deux fois différentiable

en tout point de K. On a équivalence entre :
1 f convexe sur K.
2 ∀(u, v) ∈ K 2 , t (v − u).Hf (u).(v − u) ≥ 0 (Hf (u) est semi-définie
positive).
Critéres de convexité stricte : :
Si ∀(u, v) ∈ K 2 , u ̸= v, t (v − u).Hf (u).(v − u) > 0 (Hf (u) est définie
positive), alors f est strictement convexe sur K.

Théorème (critère de Sylvester) : Pour qu’une matrice Hf = (aij )1≤i,j≤n

réelle symétrique soit définie positive, il faut et suffit que les n sous ma-
trices mineurs principaux Hfp = (aij )1≤i,j≤p de Hf aient leur détermi-
nant strictement positif pour tout p = 1, . . . , n.

AMAL Youssef Statistique pour Ingénieurs 1445/2023 12 / 30

Existence et unicité de minimum Existence de minimum local liée à la convexité

Soient K un ouvert de RN et f : K → R différentiable en a,

On dit qu’un point a est un point critique de f si ∇f (a) = 0.
Soit f une fonction de classe C 2 sur un voisinage de a. Hf (a) est alors
une matrice symétrique réelle dont les valeurs propres, nécessairement
réelles, sont ordonnées comme suit: λmin = λ1 ≤ λ2 ≤ ... ≤ λn . On a
alors :
Hf (a) est semi-définie positive si et seulement si λmin ≥ 0.
Hf (a) est définie positive si et seulement si λmin > 0 .

Si λmin > 0 alors f admet un minimum local en a.

AMAL Youssef Statistique pour Ingénieurs 1445/2023 13 / 30

Existence et unicité de minimum Existence de minimum global liée à la convexité

Si f est convexe sur K et si elle admet un point critique en a ∈ K vérifiant

∇f (a) = 0, alors f admet un minimum local et global en a sur K.
C. Exemple : fonctions affines.
Soit K ⊂ RN un ensemble non vide et convexe. Si f : K → R admet
un minimum local en u sur K. Alors,
Si f est convexe alors f admet un minimum global en u sur K.
Si f est strictement convexe alors alors u est l’unique point de minimum
global de f sur K.

C. Exemple : f (x) = ex .

AMAL Youssef Statistique pour Ingénieurs 1445/2023 14 / 30

Existence et unicité de minimum Application : Solution Analytique

Exemple : Étudier le problème de minimisation des fonctions suivantes

:
1 f (x, y) = x2 + y 2 + 3xy − y.
2 g(x, y) = x2 + y 3 − 2xy − y.

AMAL Youssef Statistique pour Ingénieurs 1445/2023 15 / 30

Existence et unicité de minimum Application : Modèle de Régression Linéaire

Considérons un ensemble de données expérimentales représentant le temps

nécessaire à l’exécution d’un algorithme en fonction de la taille de l’entrée.
Modéliser cette relation à l’aide de la régression linéaire afin de prédire
le temps d’exécution pour de nouvelles tailles d’entrée :
Tailles d’entrée Temps d’exécution
10 5
20 12
30 21
40 35
50 48

AMAL Youssef Statistique pour Ingénieurs 1445/2023 16 / 30

Existence et unicité de minimum Application : Modèle de Régression Linéaire

Objectif : Trouver une droite de régression y = ax + b pour un ensemble de

données {(x1 , y1 ), (x2 , y2 ), . . . , (xn , yn )}.
Pn
Fonction Objectif : f (a, b) = i=1 (yi − (axi + b))2
Le problème est la minimisation de la fonction f : inf f (a, b),
(a,b)∈R2

AMAL Youssef Statistique pour Ingénieurs 1445/2023 17 / 30

Existence et unicité de minimum Application : Modèle de Régression Linéaire

Point critique solution de ∇f (a, b) = (0, 0) :

xy − x.y Cov(x, y)
a0 = 2
= , b0 = y − ax
x2 −x V (x)
!
2x2 2x
On a Hf (a, b) = qui est définie positive
2x 2
pour tout (a, b) ∈ R2 avec a ̸= b.
(a0 , b0 ) est l’unique point de minimum global de f sur R2 .

AMAL Youssef Statistique pour Ingénieurs 1445/2023 18 / 30

Existence et unicité de minimum Application : Modèle de Régression Linéaire

Exemple : Le calcul donne a = 1.09 et b = −8.5.

AMAL Youssef Statistique pour Ingénieurs 1445/2023 19 / 30

Algorithmes de minimisation sans contraintes Contexte

Hypothèses : f : Rn → Rn strictement convexe, de classe C 2 .

Objectif : Trouver numériquement x∗ ∈ Rn tel que f (x∗ ) = minn f (x).
x∈R
Le problème se ramène à résoudre le système ∇f (x) = 0 Rn .

AMAL Youssef Statistique pour Ingénieurs 1445/2023 20 / 30

Algorithmes de minimisation sans contraintes Algorithmes de descente

Il ne faut pas oublier les hypothèses ! P:20

Rappel (Dérivée directionnelle) :

f (x + t.d) − f (x)
lim = Dd f (x),
t→0 t
Dd f (x) = ⟨∇f (x), d⟩.
Direction de descente : Une direction de descente de f en x est un
vecteur d ∈ Rn tel que

Dd f (x) < 0 ou encore ⟨∇f (x), d⟩ < 0

c.à.d : ∃α > 0, ∀0 < t < α : f (x + td) < f (x).

AMAL Youssef Statistique pour Ingénieurs 1445/2023 21 / 30

Algorithmes de minimisation sans contraintes Algorithmes de descente

Construction d’une suite (xk )k∈N vérifiant

f (xk+1 ) ≤ f (xk )

Pour x0 choisi arbitrairement, on a : xk+1 = xk + ρk dk , avec

dk : la direction descente. d = - Grad (f) !!!
ρk : le pas de la k-ième itération. Pas de mvmt (tjrs >0)

|
|
|
|
|x_1
AMAL Youssef Statistique pour Ingénieurs 1445/2023 22 / 30
Algorithmes de minimisation sans contraintes Algorithme de gradient

Remarque : d = −∇f (x) est la direction de plus forte descente.

AMAL Youssef Statistique pour Ingénieurs 1445/2023 23 / 30

Algorithmes de minimisation sans contraintes Algorithme de gradient

Algorithme de gradient :
1 Choisir x0 , tol > 0, k ≤ kmax
2 Calculer xk+1 = xk − ρk ∇f (xk ), et k = k + 1,
tant que ∥xk+1 − xk ∥ > tol (ou ∥∇f (xk )∥ > tol) et k ≤ kmax .
Reste à préciser ρk :
Algorithme de gradient à pas fixe : ρk = ρ
Algorithme de gradient à pas optimal :

f (xk − ρk ∇f (xk )) = min f (xk − t∇f (xk )).

t>0

AMAL Youssef Statistique pour Ingénieurs 1445/2023 24 / 30

Algorithmes de minimisation sans contraintes Algorithme de gradient à pas fixe

Théoriquement, pour un pas ρk > 0 assez petit, la suite (xk )k converge

et la convergence est au moins géométrique, c.à.d :

∃β ∈]0, 1[ tel que ∥xk − x∗ ∥ ≤ β k ∥x0 − x∗ ∥, ∀k ∈ N

Si le pas est trop grand, la descente vers le minimum est rapide mais le
risque d’osciller autour du minimum sans converger est élevé.
Le pas devrait être assez petit pour converger vers le minimum mais pas
trop petit sinon le coût numérique sera très élevé.
Le choix du pas fixe convenable est obtenu par le test de plusieurs valeurs.

AMAL Youssef Statistique pour Ingénieurs 1445/2023 25 / 30

Algorithmes de minimisation sans contraintes Algorithme de gradient à pas optimal

Recherche exacte de pas optimal ρk solution de :

min f (xk − t∇f (xk ))
t>0
Exemple : Soit f (x, y) = 12 x2 + 72 y 2 .
∇f (xk , yk ) = (xk , 7yk )
x2 + 49yk2
ρk = 2k
xk + 343yk2
xk+1 = xk − ρk xk
yk+1 = yk − ρk yk

AMAL Youssef Statistique pour Ingénieurs 1445/2023 26 / 30

Algorithmes de minimisation sans contraintes Exemple 2

Résoudre le problème d’optimisation suivant :

inf f (x)
x∈R2

où
1
f (x, y) = x4 − 2x3 + y 2 − 3x − xy
6

AMAL Youssef Statistique pour Ingénieurs 1445/2023 27 / 30

Algorithmes de minimisation sans contraintes Algorithme du gradient conjugué

[Link]

Considérons la Fonction objectif de forme quadratique :

On a particulièrement choisi cette fonction 1

car c'est pour Gradf = 0 on aura AX=b f (x) = ⟨Ax, x⟩ − ⟨b, x⟩
2 la formule d'une fonction quadratique ax^2+bx +c
avec c = 0
oú A est une matrice symétrique définie positive.
La fonction f est strictement convexe et de classe C +∞ ,
Le minimum global de f est atteint en x∗ tel que Ax∗ = b, en effet :
∇f (x) = Ax − b et Hf (x) = A.
La méthode du gradient conjugué est une méthode itérative directe pour
résoudre l’équation Ax = b.

AMAL Youssef Statistique pour Ingénieurs 1445/2023 28 / 30

Algorithmes de minimisation sans contraintes Algorithme du gradient conjugué

[Link]

Algorithme du gradient conjugué : Pour tout k ≥ 0, rk = −∇f (xk ) =

rk est tjrs la direction perpond. à
b − Axk , la direction actuelle

1 Choisir un vecteur initial x0 , poser d−1 = 0 ∈ Rn et calculer r0 =

b − Ax0 ,
alpha(k-1)d(k-1) est une
2 Pour k = 0, 1, . . . , n ou jusqu’à la convergence : sorte de rotation qui
∗ permet de tourner la
3 Si rk > tol alors xk = x arrêt. Sinon, direction de rk avec un
angle, la nvelle direct.
4 dk = rk + αk−1 dk−1 avec αk−1 tel que ⟨Adk , dk−1 ⟩ = 0,obtenue est d(k)
5 xk+1 = xk + tk dk où tk est tel que f (xk + tk dk ) = min f (xk + tdk ).
t≥0

Il en résulte que :
tk signifie la distance qu'on doit parcourir en
⟨Ark , dk ⟩ ⟨rk , dk ⟩ suivant la direction dk de tel maniere que d(k+1)
αk = − et tk = . sera A-orthog avec d(k)
⟨Adk , dk ⟩ ⟨Adk , dk ⟩
La méthode consiste à construire une suite (dk )k A-orthogonale formant
une base de Rn dans le cas où la convergence est atteint en n itérations.

AMAL Youssef Statistique pour Ingénieurs 1445/2023 29 / 30

Algorithmes de minimisation sans contraintes Exemple 3

Minimiser la fonction suivante, en utilisant la méthode des gradients

conjugués :
f (x, y) = x2 + 4xy + y 2 − 4x − 4y

AMAL Youssef Statistique pour Ingénieurs 1445/2023 30 / 30