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 / 19

 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
-inf -f(x)

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

 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 / 19

 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 / 19

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 / 19

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 / 19

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 / 19

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 / 19

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 / 19

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 / 19
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 / 19

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 / 19

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 / 19

Existence et unicité de minimum Application : Solution Analytique

Exemple : Chercher les points critiques des fonctions suivantes, et étudier

leurs natures :
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 / 19

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
~x ~y

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

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 / 19

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

[Link]
Exemple 10:00

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 / 19

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 / 19