Optimisation pour le ML

Introduction à Machine Learning & notions de base

Optimisation pour le ML 5 DS A.U. 2023/2024

 Plan

1 Notions de base pour l’optimisation

2 Analyse matricielle

3 Calcul différentiel

4 Fonctions convexes

2 / 17
 Notions de base pour l’optimisation
Normes et produit scalaire

Soit E un espace vectoriel sur R. Soit u un vecteur de E , on dit que

l’application
∥·∥: E → R
u 7→ ∥u∥
est une norme sur E si les propriétés suivantes sont vérifiées :
1 ∀λ ∈ R, ∀u ∈ E , ∥λu∥ = |λ|∥u∥.
2 ∀(u, v ) ∈ E × E , ∥u + v ∥ ≤ ∥u∥ + ∥v ∥.
3 ∥u∥ = 0 ⇔ u = 0
Dans ce cas, on dit que (E , ∥ · ∥) est un espace vectoriel normé.

3 / 17
 Notions de base pour l’optimisation
Normes et produit scalaire

Soit E un espace vectoriel sur R. Soit u un vecteur de E , on dit que

l’application
∥·∥: E → R
u 7→ ∥u∥
est une norme sur E si les propriétés suivantes sont vérifiées :
1 ∀λ ∈ R, ∀u ∈ E , ∥λu∥ = |λ|∥u∥.
2 ∀(u, v ) ∈ E × E , ∥u + v ∥ ≤ ∥u∥ + ∥v ∥.
3 ∥u∥ = 0 ⇔ u = 0
Dans ce cas, on dit que (E , ∥ · ∥) est un espace vectoriel normé.
Remarque : Normes usuelles sur Rn
Soit u = (x1 , · · · , xn ) ∈ Rn , on a
1 La norme 1 : ∥u∥ =
Pn
1 i=1 |xi |

2 La norme 2 (ou norme euclidienne) : ∥u∥ =

Pn 2 1/2


2 i=1 xi
3 La norme ∞ : ∥u∥∞ = max(|x1 |, |x2 |, · · · , |xn |)

3 / 17
 Notions de base pour l’optimisation
Normes et produit scalaire

Soit E un espace vectoriel sur R. Soit u un vecteur de E , on dit que

l’application
∥·∥: E → R
u 7→ ∥u∥
est une norme sur E si les propriétés suivantes sont vérifiées :
1 ∀λ ∈ R, ∀u ∈ E , ∥λu∥ = |λ|∥u∥.
2 ∀(u, v ) ∈ E × E , ∥u + v ∥ ≤ ∥u∥ + ∥v ∥.
3 ∥u∥ = 0 ⇔ u = 0
Dans ce cas, on dit que (E , ∥ · ∥) est un espace vectoriel normé.
Remarque : Normes usuelles sur Rn
Soit u = (x1 , · · · , xn ) ∈ Rn , on a
1 La norme 1 : ∥u∥ =
Pn
1 i=1 |xi |

2 La norme 2 (ou norme euclidienne) : ∥u∥ =

Pn 2 1/2


2 i=1 xi
3 La norme ∞ : ∥u∥∞ = max(|x1 |, |x2 |, · · · , |xn |)
Exercice : Soit u = (1, −2, 3), calculer ∥u∥1 , ∥u∥2 et ∥u∥∞ .

3 / 17
Soit E un espace vectoriel sur R. Soient u et v deux vecteurs de E , on dit que
l’application
⟨·, ·⟩ E × E → R
(u, v ) 7→ ⟨u, v ⟩
est un un produit scalaire sur E si c’est une forme bilinéaire symétrique définie
positive sur E :
forme : ∀(u, v ) ∈ E 2 , ⟨u, v ⟩ ∈ R
symétrique : ∀u, v ∈ E ⟨u, v ⟩ = ⟨v , u⟩
bilinéaire : linéaire par rapport à ses deux variables

∀λ ∈ R ∀u, v , w ∈ E ⟨u, λv + w ⟩ = ⟨u, w ⟩ + λ⟨u, v ⟩

définie positive : ∀u ∈ E u ̸= 0 ⇒ ⟨u, u⟩ > 0

4 / 17
Soit E un espace vectoriel sur R. Soient u et v deux vecteurs de E , on dit que
l’application
⟨·, ·⟩ E × E → R
(u, v ) 7→ ⟨u, v ⟩
est un un produit scalaire sur E si c’est une forme bilinéaire symétrique définie
positive sur E :
forme : ∀(u, v ) ∈ E 2 , ⟨u, v ⟩ ∈ R
symétrique : ∀u, v ∈ E ⟨u, v ⟩ = ⟨v , u⟩
bilinéaire : linéaire par rapport à ses deux variables

∀λ ∈ R ∀u, v , w ∈ E ⟨u, λv + w ⟩ = ⟨u, w ⟩ + λ⟨u, v ⟩

définie positive : ∀u ∈ E u ̸= 0 ⇒ ⟨u, u⟩ > 0

Remarque : produit scalaire et norme dans Rn
Si E = Rn . Soient x = (x1 , · · · , xn ) ∈ Rn et y = (y1 , · · · , yn ) ∈ Rn , on a :
n
X
1 ⟨x, y ⟩ = xi yi .
i=1
p
2 ∥x∥2 = ⟨x, x⟩
3 On dit que x et y sont orthogonaux si ⟨x, y ⟩ = 0.

4 / 17
Soit E un espace vectoriel sur R. Soient u et v deux vecteurs de E , on dit que
l’application
⟨·, ·⟩ E × E → R
(u, v ) 7→ ⟨u, v ⟩
est un un produit scalaire sur E si c’est une forme bilinéaire symétrique définie
positive sur E :
forme : ∀(u, v ) ∈ E 2 , ⟨u, v ⟩ ∈ R
symétrique : ∀u, v ∈ E ⟨u, v ⟩ = ⟨v , u⟩
bilinéaire : linéaire par rapport à ses deux variables

∀λ ∈ R ∀u, v , w ∈ E ⟨u, λv + w ⟩ = ⟨u, w ⟩ + λ⟨u, v ⟩

définie positive : ∀u ∈ E u ̸= 0 ⇒ ⟨u, u⟩ > 0

Remarque : produit scalaire et norme dans Rn
Si E = Rn . Soient x = (x1 , · · · , xn ) ∈ Rn et y = (y1 , · · · , yn ) ∈ Rn , on a :
n
X
1 ⟨x, y ⟩ = xi yi .
i=1
p
2 ∥x∥2 = ⟨x, x⟩
3 On dit que x et y sont orthogonaux si ⟨x, y ⟩ = 0.
Exemple : Soient x = (1, −2, 3) et y = (−1, 1, 2), calculer ⟨x, y ⟩. Que peut-on
dire pour x et z avec z = (1, 2, 1).
4 / 17
 Analyse matricielle

Soit Mm,n (R) l’ensemble de matrices de m lignes et n colonnes à coefficients

dans R. Mm,n (R) est un espace vectoriel sur R.
Définitions :
• Soit A ∈ Mm,n (R), la matrice transposée AT ∈ Mn,m (R) vérifie :

∀(x, y ) ∈ Rn × Rm , ⟨Ax, y ⟩Rm = ⟨x, AT y ⟩Rn ,

avec ⟨x, AT y ⟩E est le produit scalaire définie sur E .

• Soit A ∈ Mn (R) est dit symétrique si et seulement si A = AT .

On note Sn (R) par l’ensemble des matrices symétriques réelles.

• Soit A ∈ Sn (R). A est dite

semi-définie positive (ou positive) : si ⟨Ax, x⟩ ≥ 0 pour tout x ∈ Rn .
définie positive : si ⟨Ax, x⟩ > 0 pour tout x ∈ Rn \ {0}
• λ ∈ R est une valeur propre de A s’il existe x ∈ Rn non nul tel que Ax = λx.
On note sp(A) l’ensemble de toutes les valeurs propres de A. sp(A) appelé le
spectre de A.

5 / 17
 Analyse matricielle
Proposition :
Soit A ∈ Sn (R), A est semi-définie positive (resp. définie positive) si l’une des
conditions suivantes est vérifiée
Le déterminant des mineurs principaux est positif (resp. strictement
positif).
le spectre de A est positif (resp. strictement positif)

6 / 17
 Analyse matricielle
Proposition :
Soit A ∈ Sn (R), A est semi-définie positive (resp. définie positive) si l’une des
conditions suivantes est vérifiée
Le déterminant des mineurs principaux est positif (resp. strictement
positif).
le spectre de A est positif (resp. strictement positif)
2
 
−1 −1
Exercice : Soit la matrice A = −1 2 −1
−1 −1 2
1. A est-elle symétrique ?
2. Vérifier que A semi-définie positive. A est-elle définie positive ?

6 / 17
 Analyse matricielle
Proposition :
Soit A ∈ Sn (R), A est semi-définie positive (resp. définie positive) si l’une des
conditions suivantes est vérifiée
Le déterminant des mineurs principaux est positif (resp. strictement
positif).
le spectre de A est positif (resp. strictement positif)
2
 
−1 −1
Exercice : Soit la matrice A = −1 2 −1
−1 −1 2
1. A est-elle symétrique ?
2. Vérifier que A semi-définie positive. A est-elle définie positive ?
Correction :
1. On a AT = A, donc A est symétrique
2. Calculons les déterminants de mineurs principaux :
2
 
−1
|2| = 2 > 0, det = 3 > 0, detA = 0
−1 2
Donc, A est semi-définie positive et non définie positive.
6 / 17
 Analyse matricielle
Théorème spectral

Théorème :
Une matrice symétrique réelle est diagonalisable(1) dans une base orthonormée
à valeurs propres réelles
diagonalisable(1) : Il existe une base orthonormée B = (V1 , · · · , Vn) formée par
les vecteurs propres Vi ; i = {1, · · · , n} telle que la matrice A est semblable à
une matrice diagonale dans cette base B c-à-d A = PDP −1 avec P matrice
inversible et D matrice diagonale.
Proposition :
Soient A ∈ Sn (R) définie positive, et sp(A) = {λ1 , λ2 , · · · , λn }. Si on suppose
que λ1 ≤ λ2 ≤ · · · λn . Alors

∀x ∈ Rn , λ1 ∥x∥22 ≤ ⟨Ax, x⟩ ≤ λn ∥x∥22

7 / 17
 Analyse matricielle
Norme d’une matrice

La norme (subordonnée à la norme euclidienne) d’une matrice A ∈ Mm,n (R)

est le nombre positif

∥Ax∥
∥A∥ = max .
x̸=0 ∥x∥
Cette norme vérifie :
∀A ∈ Mm,n (R), ∀x ∈ Rn , ∥Ax∥ ≤ ∥A∥∥x∥
∀A ∈ Mm,n (R), B ∈ Mn,p (R), ∥AB∥ ≤ ∥A∥∥B∥

8 / 17
 Calcul différentiel
Définitions :
Soient f : E ⊂ Rn −→ R et a ∈ E . Pour i = 1, · · · , n, on appelle dérivée
partielle par rapport à xi de f en a = (a1 , · · · , an ), et on note (s’il existe) ∂x
∂f
i
(a)
la dérivée de la fonction partielle de f prise en a

∂f f (a1 , · · · , ai − h, · · · , an ) − f (a1 , · · · , ai , · · · , an )
(a) = lim .
∂xi h→0 h
Remarque : Le calcul de ∂x ∂f
i
consiste à ne dériver l’expression de f que par
rapport à xi . Les fonctions dérivées partielle ∂x ∂f
i
sont aussi des fonctions de n
variables à valeurs dans R.
Exemple
1 On considère la fonction g : R2 −→ R définie par :

∀(x, y ) ∈ R2 ; g (x, y ) = x 2 + y 2 + xy .

Calculer les dérivées partielles de g par rapport aux variables x et y .

2 On considère la fonction f : R3 −→ R définie par :

∀(x, y , z) ∈ R3 ; f (x, y , z) = x 2 + y 2 + z 2 − xy − xz − yz.

Calculer les dérivées partielles de f par rapport aux variables x, y et z.

9 / 17
 Calcul différentiel

Définitions :
Soit f : E ⊂ Rn −→ R et a ∈ E . Supposons que f admet sur E une
∂f
dérivée partielle ∂x i
.
∂f
Si la fonction ∂xi admet une dérivée partielle par rapport à la j-ième
∂ ∂f ∂ ∂f
variable au point a noté ∂x j ∂xi
. On dit que ∂x j ∂xi
(a) est une dérivée
partielle d’ordre 2 au point a par rapport à la i-ième et j-ième variables
prises dans cette ordre.
Remarque : A partir des dérivées partielles d’ordre 2, on définit les
dérivées partielles d’ordre 3 lorsqu’elles existent. De proche en proche, on
définit les dérivées partielle d’ordre k lorsqu’elles existe.
Exemple
Cherhcer les dérivées partielles d’ordre 2 de la fonction f : R2 −→ R
définie par :
f (x, y ) = x + y − x 2 y 3 .

10 / 17
 Calcul différentiel
Définitions :
On dit que f est différentiable en a s’il existe une application linéaire Da f
de Rn dans R telle que pour tout h ∈ Rn on a :

f (a + h) = f (a) + Da f (h) + ∥h∥ε(h).

avec ε −→ 0
h→0
Remarque : La quantité Da f (h) est appellée communément dérivée
directionnelle de f au point a dans la direction h. On la note aussi
Da f (h) = Df (a)(h) = L(a)(h).

Théorème
Soit f : Ω ⊂ Rn −→ R
Si toutes les dérivées partielles de f existent sur Ω et si elles sont
continues en un point a ∈ Ω, alors f est différentiable en a et on a :
n
X ∂f
Da f (h) = Df (a)(h) = (a)hi ; ∀h = (h1 , · · · , hn ).
∂xi
i=1
11 / 17
 Calcul différentiel

Exercice :
On considère la fonction f : Rn −→ R définie par :

∀X ∈ Rn , f (X ) = ⟨b, X ⟩,

où ⟨, ⟩ est un produit scalaire sur Rn et b ∈ Rn .

Montrer que f est différentiable en tout point X ∈ Rn et donner DX f .

12 / 17
 Calcul différentiel

Exercice :
On considère la fonction f : Rn −→ R définie par :

∀X ∈ Rn , f (X ) = ⟨b, X ⟩,

où ⟨, ⟩ est un produit scalaire sur Rn et b ∈ Rn .

Montrer que f est différentiable en tout point X ∈ Rn et donner DX f .
solution :
Soit X , h ∈ Rn ;

f (X + h) = ⟨b, X + h⟩
= ⟨b, X ⟩ + ⟨b, h⟩
= f (X ) + ⟨b, h⟩

Donc f est différentiable en tout point X ∈ Rn et DX f (h) = ⟨b, h⟩

12 / 17
 Calcul différentiel
Soit f : (x1 , · · · , xn ) ∈ Ω −→ R avec Ω ouvert de Rn et on note C k (Ω)
l’ensemble des fonctions dont les dérivées partielles d’ordre inférieur ou
égal à k sont toutes continues sur Ω.

Définition : Gradient, matrice hessienne

(i) Le gradient d’une fonction f ∈ C 1 (Ω) est défini par :
 ∂f 
∂x1 (x)
∇f (x) =  .. n
∈R
 
.
∂f
∂xn (x)

(ii) La matrice Hessienne d’une fonction f ∈ C 2 (Ω) au point x ∈ Ω,

notée indifféremment ∇2 f (x) ou Hess f (x) est définie par :
∂f ∂f
···
 
∂x1 ∂x1 (x) ∂x1 ∂xn (x)
∇2 f (x) =  .. ..
 ∈ Mn (R)
 
. .
∂f ∂f
∂xn ∂x1 (x) ··· ∂xn ∂xn (x)

13 / 17
 Calcul différentiel

Théorème :
Soit f : Ω ⊂ Rn −→ R.
Si f est de classe C 2 sur alors les “dérivées partielles commutent”. c-à-d :

∂2f ∂2f
=
∂xi ∂xj ∂xj ∂xi

Théorème : Formule de Taylor-Young

Soit x, h ∈ Ω ⊂ Rn
(i) Si f ∈ C 1 (Ω) alors :

f (x + h) = f (x) + ⟨∇f (x), h⟩ + o(∥h∥)

(ii) Si f ∈ C 2 (Ω) alors :

1
f (x + h) = f (x) + ⟨∇f (x), h⟩ + ⟨∇2 f (x)h, h⟩ + o(∥h∥2 )
2
14 / 17
 Fonctions convexes

Définitions : Fonction convexe

Soit K ⊂ Rn un ensemble convexe non vide.

Une fonction f : K −→ R est dite convexe si

∀x, y ∈ K , ∀λ ∈ [0, 1], f (λx + (1 − λ)y ) ≤ λf (x) + (1 − λ)f (y ).

f est dite strictement convexe si l’inégalité est stricte dès que x ̸= y et

λ ∈]0; 1[. Autrement dit :

∀x, y ∈ K , (x ̸= y ); ∀λ ∈]0, 1[, f (λx + (1 − λ)y ) < λf (x) + (1 − λ)f (y ).

Exemple
x 7−→ x 2 est convexe (sur R).
les fonctions affines sont convexes

15 / 17
 Fonctions convexes

Proposition
Soit U, un ouvert convexe de Rn et f : U ⊂ Rn −→ R de classe C 1 .
On a équivalence entre
(i) f est convexe sur U
(ii) ∀(x; y ) ∈ U 2 ; f (y ) ≥ f (x) + ⟨∇f (x), y − x⟩
(iii) ∀(x; y ) ∈ U 2 ; ⟨∇f (y ) − ∇f (x); y − x⟩ ≥ 0;
On a les mêmes équivalences avec inégalité stricte si x ̸= y dans le
cas strictement convexe.

Théorème
Si f : Rn −→ R est de C 2 , alors on a :
(i) (∀x ∈ Rn ; ∇2 f (x) est semi-définie positive) ⇐⇒ f est convexe,
(ii) (∀x ∈ Rn ; ∇2 f (x) est définie positive) =⇒ f est strictement convexe.

16 / 17
 Fonctions convexes

Exercice :
Soit a ∈ R. On définit fa : (x, y ) ∈ R2 7−→ x 2 + y 2 + axy − 2x − 2y .
1 Tracer sous Python la fonction fa (avec a au choix) en utilisant la
sous bibliothèque "[Link] objects"
2 Pour quelles valeurs de a, la fonction fa est-elle convexe ?

17 / 17