CM Optimisation .pdf



Nom original: CM_Optimisation.pdfTitre: PA NumériqueAuteur: Pauline LOUIS

Ce document au format PDF 1.7 a été généré par Microsoft® PowerPoint® 2019, et a été envoyé sur fichier-pdf.fr le 20/10/2021 à 13:34, depuis l'adresse IP 194.167.x.x. La présente page de téléchargement du fichier a été vue 4 fois.
Taille du document: 2.1 Mo (28 pages).
Confidentialité: fichier public


Aperçu du document


Machine Learning
Optimisation Numérique et Algorithmique
Arnaud COUTU

1

Organisation et Contenu
1 CM, 3 TD de 1h30
Contrôle continu au format projet en lien avec le PA

A la fin de ces 6h, vous devrez être en mesure :
• De connaître les différentes optimisations numériques possibles
• De maîtriser les 3 principales techniques d’optimisation linéaire sans
contrainte
• D’appliquer ces différentes méthodes sur n’importe quel problème

2

Programme
• L’optimisation, c’est quoi ?
• L’optimisation continue sans contraintes
• Problème général d’optimisation continue
• Caractérisation des points optimaux
• Méthodes de descente et minimisation en une dimension
• Algorithmes de minimisation sans contraintes
• Méthode de descente du gradient
• Méthode de Newton
• Méthode du gradient conjugué

3

L’optimisation c’est quoi ?
« Branche des mathématiques permettant de modéliser, analyser et résoudre
numériquement les problèmes consistant à minimiser ou maximiser une fonction sur
un ensemble »

Prérequis mathématiques : algèbre linéaire, fonctions à plusieurs variables et
opérateurs différentiels
• Nouvelles problématiques par rapport aux mathématiques usuels :
• Stabilité du problème : l’impact de la perturbation du paramètre implique une
faible variation de la solution
• Erreurs d’approximation : Erreur de discrétisation d’un problème continu en
problème discret. L’erreur est alors liée au pas de discrétisation.
• Erreurs d’arrondi : Erreur due à la précision machine.
4

Quelques exemples
Optimiser le coût de mes
courses tout en m’assurant de
manger équilibrer
Aller au travail avec le chemin
le plus court ou le plus rapide
(GPS)

Acheter le moins de matières
premières pour produire le
plus de produits finis
5

Programme
• L’optimisation, c’est quoi ?
• L’optimisation continue sans contraintes
• Problème général d’optimisation continue
• Caractérisation des points optimaux
• Méthodes de descente et minimisation en une dimension
• Algorithmes de minimisation sans contraintes
• Méthode de descente du gradient
• Méthode de Newton
• Méthode du gradient conjugué

6

L’optimisation continue
sans contraintes
Problématique générale : un problème d’optimisation se présente sous sa
forme standard :

𝑀𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 𝑓(𝑥)

𝑆𝑜𝑢𝑠 𝑙𝑎 𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛 𝑥 ∈ 𝐶 = 𝑥 ∈ 𝐷|𝑔 𝑥 > 0, ℎ 𝑥 > 0
La fonction f est appelée fonction objectif ou coût ou critère
C est l’ensemble des contraintes. Si x est compris dans C, il est admissible ou réalisable
Lorsque C = D, le problème est dit sans contraintes. Le problème devient alors :

𝑀𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 𝑓 𝑥 𝑠𝑜𝑢𝑠 𝑙𝑎 𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛 𝑥 ∈ 𝐷
7

Quelques notations

Une valeur optimale de x est définie par 𝒙
ഥ = 𝒇ത
Une valeur optimale de f est définie par 𝒇 𝒙

L’ensemble des points optimaux vérifient 𝒙 =

𝒂𝒓𝒈𝒎𝒊𝒏 𝒇(𝒙)
𝑥∈𝐷

ഥ ∈ 𝐃 est un minimum local s’il existe un voisinage V de tel
Un point 𝒙
ഥ ≤ 𝒇(𝒙)
que : 𝒇 𝒙

8

L’optimisation continue
sans contraintes
Caractérisation des points optimaux : le principe est d’assurer la présence et
l’unicité d’un minimum (local, global ou strict)
Quelques rappels de mathématiques : soit une fonction 𝒇 𝐱, 𝐲
Le gradient de f : 𝛁𝒇 =

𝝏𝒇
𝝏𝒙
𝝏𝒇
𝝏𝒚

La matrice Hessienne :

𝑯𝒇 =

𝝏²𝒇
𝝏𝒙²
𝝏²𝒇
𝝏𝒚𝝏𝒙

𝝏²𝒇
𝝏𝒙𝝏𝒚
𝝏²𝒇
𝝏𝒚²

A ne pas confondre avec le divergent et le laplacien qui sont des scalaires !
Une fonction convexe à une variable est une fonction au-dessus de sa tangente
Une fonction concave à une variable est une fonction au-dessous de sa tangente
9

L’optimisation continue
sans contraintes
Méthode de descente et vitesse de convergence : la méthode utilisée suit le
principe des suites et doit vérifier 3 conditions :

𝒇 𝒙𝒊

𝒙𝒊+𝟏 − 𝒙𝒊 → 𝟎 𝒑𝒐𝒖𝒓 𝒊 → +∞
𝛁𝒇(𝒙𝒊 ) → 𝟎 𝒑𝒐𝒖𝒓 𝒊 → +∞
≤ 𝒇 𝒙𝒊−𝟏 ≤, ⋯ ≤ 𝒇 𝒙𝟎 𝒑𝒐𝒖𝒓 𝒊 → +∞

Pour l’algorithme de descente, 2 paramètres sont importants : la direction de
descente et le pas. La direction de descente se note d et se détermine à l’aide
de la dérivée directionnelle. Le pas se note 𝝈 et représente la vitesse de
convergence optimale.
10

L’optimisation continue
sans contraintes
Algorithme de descente :

Initialisation : choisir 𝒙𝟎 et poser 𝒊 = 𝟎
Choisir un seuil de tolérance ε
Tant que 𝛁𝒇(𝒙𝒊 ) > ε
Déterminer une direction 𝒅𝒊 telle que pour tout pas 𝝈 > 𝟎, 𝒇 𝒙𝒊 + 𝝈𝒅𝒊 < 𝒇 𝒙𝒊
Déterminer le pas 𝝈𝒊 > 𝟎
Poser 𝒙𝒊+𝟏 = 𝒙𝒊 + 𝝈𝒅𝒊 et 𝒊 = 𝒊 + 𝟏
Fin du tant que
11

L’optimisation continue
sans contraintes
Vitesse de convergence : pour une méthode itérative convergente, la méthode
est dite d’ordre 𝒓 ≥ 𝟏 s’il existe une constante C telle que pour i suffisamment
grand :

𝒙𝒊+𝟏 − 𝒙
≤𝑪
𝒊
𝒓

𝒙 −𝒙

Si 𝒓 = 𝟏 , 𝐂 ∈ 𝟎, 𝟏 pour avoir convergence : la convergence est dite linéaire
Si 𝒓 = 𝟐 ,la convergence est dite quadratique
12

L’optimisation continue
sans contraintes
Pour la détermination du pas optimal, on considère les conditions de WOLFE
(W1) et (W2) ci-dessous :
𝒇 𝒙𝒊 + 𝝈𝒅𝒊 ≤ 𝒇 𝒙𝒊 + 𝒄𝟏 𝝈(𝛁𝒇 𝒙𝒊 . 𝒅𝒊 )
(𝛁𝒇 𝒙𝒊 + 𝝈𝒅𝒊 . 𝒅𝒊 ) ≥ 𝒄𝟐 (𝛁𝒇 𝒙𝒊 . 𝒅𝒊 )

(W1)
(W2)

avec 𝟎 < 𝒄𝟏 < 𝒄𝟐 < 𝟏
La condition (W1) impose une valeur maximale de 𝝈 pour
garantir une convergence possible.
La condition (W2) permet d’augmenter 𝝈 lorsque la descente
de gradient est forte. Cela permet de ne pas avoir un pas trop
petit et gagner en temps de calcul.
13

L’optimisation continue
sans contraintes
Algorithme de backtracking / recherche rétrograde : méthode classique
donnant souvent de bons résultats
Initialisation : choisir 𝝈𝟎 , 𝝆, 𝐂 ∈ 𝟎, 𝟏
𝝈 = 𝝈𝟎

𝝈

Tant que 𝒇 𝒙𝒊 + 𝝈𝒅𝒊 > 𝒇 𝒙𝒊 + 𝑪𝝈(𝛁𝒇 𝒙𝒊 . 𝒅𝒊 )
𝝈 = 𝝆𝝈
Fin du tant que
𝝈𝒊 = 𝝈
A partir d’une grande valeur de 𝝈𝟎 , on détermine 𝝈𝒊 en diminuant à chaque
itération la valeur de 𝝈 jusqu’à ce que 𝝈 vérifie (W1). En partant loin de 0, (W2)
sera également respectée
14

Programme
• L’optimisation, c’est quoi ?
• L’optimisation continue sans contraintes
• Problème général d’optimisation continue
• Caractérisation des points optimaux
• Méthodes de descente et minimisation en une dimension
• Algorithmes de minimisation sans contraintes
• Méthode de descente du gradient
• Méthode de Newton
• Méthode du gradient conjugué

15

Descente du gradient
Algorithme de descente du gradient :
Initialisation : choisir 𝒙𝟎 et poser 𝒊 = 𝟎

𝝈

Choisir un seuil de tolérance ε

Tant que 𝛁𝒇(𝒙𝒊 ) > ε
𝒅𝒊 = −𝛁𝒇(𝒙𝒊 )
Déterminer le pas 𝝈𝒊 > 𝟎
Poser 𝒙𝒊+𝟏 = 𝒙𝒊 + 𝝈𝒊 𝒅𝒊 et 𝒊 = 𝒊 + 𝟏
Fin du tant que

16

Descente du gradient
Exemple : trouver le minimum de la fonction suivante : 𝒇 𝒙, 𝒚 = 𝒙𝟐 + 𝒚𝟐
Initialisation : on choisit 𝒙𝟎 , 𝒚𝟎 = (𝟓, 𝟏𝟎) et 𝒊 = 𝟎
On choisit un seuil de tolérance ε = 0,001
2𝑥 𝑖
𝒊) =
=
,
𝛁𝒇(𝒙
2𝑦 𝑖

On calcule le gradient : 𝛁𝒇

𝒙𝒊 , 𝒚i

Tant que

> 0,001

𝟐𝒙𝒊

𝟐

On pose le pas

𝝈𝒊

+ 𝟐𝒚𝒊

𝟐

𝟐𝒙𝒊

déterminé par backtracking et on calcule

On pose 𝒙𝒊+𝟏 , 𝒚𝒊+𝟏 = 𝒙𝒊 , 𝒚𝒊 + 𝝈𝒊 𝒅𝒊 et 𝒊 = 𝒊 + 𝟏

𝟐

𝒅𝒊

+ 𝟐𝒚𝒊

𝟐

2𝑥 𝑖
=−
2𝑦 𝑖

Fin du tant que
17

Descente du gradient
Algorithme complet :

𝒇 𝒙, 𝒚 = 𝒙𝟐 + 𝒚𝟐

Initialisation

𝒙𝟎 , 𝒚𝟎 = (𝟓, 𝟏𝟎) et 𝒊 = 𝟎, ε = 0,001
Tant que
𝒅𝒊

2𝑥 𝑖
=−
2𝑦 𝑖

𝟐𝒙𝒊

𝟐

+ 𝟐𝒚𝒊

𝟐

> 0,001

𝝈𝟎 = 𝟎, 𝟏, 𝝆 = 𝟎, 𝟗𝟓, 𝐂 = 𝟎, 𝟓

Calcul de la direction de descente
Calcul du pas optimal

Tant que 𝒇 𝒙𝒊 , 𝒚𝒊 + 𝝈𝒅𝒊 > 𝒇 𝒙𝒊 , 𝒚𝒊 + 𝟎, 𝟓𝝈(𝛁𝒇 𝒙𝒊 , 𝒚𝒊 . 𝒅𝒊 )
𝝈 = 𝟎, 𝟗𝟓𝝈
Fin du tant que
𝝈𝒊 = 𝝈
𝒙𝒊+𝟏 , 𝒚𝒊+𝟏 = 𝒙𝒊 , 𝒚𝒊 + 𝝈𝒊 𝒅𝒊 et 𝒊 = 𝒊 + 𝟏

Fin du tant que

Passage à l’itération suivante
18

Descente du gradient
Résultat :

19

Programme
• L’optimisation, c’est quoi ?
• L’optimisation continue sans contraintes
• Problème général d’optimisation continue
• Caractérisation des points optimaux
• Méthodes de descente et minimisation en une dimension
• Algorithmes de minimisation sans contraintes
• Méthode de descente du gradient
• Méthode de Newton
• Méthode du gradient conjugué

20

Méthode de Newton
Algorithme de la méthode de Newton : La méthode de Newton s’appuie sur la
formule de Taylor-Young avec un développement limité d’ordre 2.
𝟏 𝒕
𝒊
𝒊
𝒊
𝒊
𝒕
𝒇 𝒙 + 𝒅 ~𝒇 𝒅 = 𝒇 𝒙 + 𝛁𝒇(𝒙 ) 𝒅 + 𝒅 𝑯𝒇 𝒙𝒊 𝒅
𝟐
Si 𝑯𝒇 𝒙𝒊 est positive, 𝒅𝒊 sera le minimum de 𝒇𝒊 :
𝒅𝒊

= − 𝑯𝒇

𝒙𝒊

−𝟏

𝛁𝒇(𝒙𝒊 )

𝒊

𝛁𝒇 𝒙 . 𝒅

𝒊

𝒊𝒕

= −𝒅 𝑯𝒇 𝒙𝒊 𝒅𝒊 ≤ 𝟎

On obtient donc bien une direction de descente. L’algorithme est le même que pour
la descente du gradient excepté pour le calcul de la direction de descente
Remarque : la convergence est très rapide avec cet algorithme lorsque la matrice
Hessienne est définie positive. Si elle est négative il y a un risque de divergence. Par
contre le coût de cette méthode est grand en nombre d’opérations par itérations.
21

Méthode de Newton
Exemple : trouver le minimum de la fonction suivante : 𝒇 𝒙, 𝒚 = 𝒙𝟐 + 𝒚𝟐
Initialisation : on choisit 𝒙𝟎 , 𝒚𝟎 = (𝟓, 𝟏𝟎) et 𝒊 = 𝟎
On choisit un seuil de tolérance ε = 0,001
2𝑥 𝑖
𝒊) =
On calcule le gradient : 𝛁𝒇
=
,
𝛁𝒇(𝒙
2𝑦 𝑖
2 0
On calcule la matrice Hessienne : 𝑯𝒇 𝒙𝒊 , 𝒚i =
0 2
Tant que 𝟐𝒙𝒊 𝟐 + 𝟐𝒚𝒊 𝟐 > 0,001
𝒙𝒊 , 𝒚i

𝟐𝒙𝒊

𝟐

+ 𝟐𝒚𝒊

𝟐

On pose le pas 𝝈𝒊 déterminé par backtracking et on calcule
−𝟏
𝒊
𝒊
𝒅 = − 𝑯𝒇 𝒙
𝛁𝒇(𝒙𝒊 )

On pose 𝒙𝒊+𝟏 , 𝒚𝒊+𝟏 = 𝒙𝒊 , 𝒚𝒊 + 𝝈𝒊 𝒅𝒊 et 𝒊 = 𝒊 + 𝟏
Fin du tant que

22

Méthode de Newton
Résultat : on remarque bien le plus grand coût en nombre de calculs

23

Programme
• L’optimisation, c’est quoi ?
• L’optimisation continue sans contraintes
• Problème général d’optimisation continue
• Caractérisation des points optimaux
• Méthodes de descente et minimisation en une dimension
• Algorithmes de minimisation sans contraintes
• Méthode de descente du gradient
• Méthode de Newton
• Méthode du gradient conjugué

24

Gradient conjugué
Algorithme du gradient conjugué (Fletcher-Reeves 1964) :
Initialisation : choisir 𝒙𝟎 et poser 𝒊 = 𝟎
𝝈

Calculer 𝒇𝟎 = 𝒇(𝒙𝟎 ) et 𝛁𝒇𝟎 = 𝛁𝒇(𝒙𝟎 )

Calculer 𝒅𝟎 = −𝛁𝒇𝟎 et choisir un seuil de tolérance ε
Tant que 𝛁𝒇(𝒙𝒊 ) > ε
Déterminer le pas 𝝈𝒊 > 𝟎 et poser 𝒙𝒊+𝟏 = 𝒙𝒊 + 𝝈𝒊 𝒅𝒊
Calculer 𝛁𝒇𝒊+𝟏 = 𝛁𝒇(𝒙𝒊+𝟏 ) et 𝜷𝒊+𝟏 =
Calculer 𝒅𝒊+𝟏 = −𝛁𝒇𝒊+𝟏 + 𝜷𝒊+𝟏 𝒅𝒊

𝒕

𝛁𝒇𝒊+𝟏 𝛁𝒇𝒊+𝟏
𝒕

𝛁𝒇𝒊 𝛁𝒇𝒊

𝒊=𝒊+𝟏
Fin du tant que
25

Gradient conjugué
Remarques :
Le principe est d’intégrer un coefficient 𝜷 pour déterminer la direction de
descente en considérant les directions de descentes comme un ensemble de
vecteurs conjugués.
𝒅𝒊 peut ne pas être une direction de descente. Il faut alors vérifier que les
𝟏
conditions de WOLFE sont bien vérifiées pour 𝝈𝒊 avec 𝟎 < 𝒄𝟏 < 𝒄𝟐 < . Alors 𝒅𝒊
𝟐
est bien une direction de descente.
Il existe des expressions de 𝜷 équivalentes dans le cas d’une fonction
fortement convexe quadratique, comme celle de Polak-Ribière (1969),
généralement plus performante mais avec un risque de divergence plus élevé :

𝜷𝒊+𝟏 =

𝒕
𝒊+𝟏
𝛁𝒇
(𝛁𝒇𝒊+𝟏

− 𝛁𝒇𝒊 )

𝒕
𝒊
𝛁𝒇 𝛁𝒇𝒊
26

Gradient conjugué
Résultat : on remarque bien le plus grand coût en nombre de calculs

27

Merci de vore attention
Optimisation Numérique et Algorithmique
Arnaud COUTU

28


Aperçu du document CM_Optimisation.pdf - page 1/28

 
CM_Optimisation.pdf - page 3/28
CM_Optimisation.pdf - page 4/28
CM_Optimisation.pdf - page 5/28
CM_Optimisation.pdf - page 6/28
 




Télécharger le fichier (PDF)


CM_Optimisation.pdf (PDF, 2.1 Mo)

Télécharger
Formats alternatifs: ZIP Texte



Documents similaires


professeur benzine rachid optimisation sans contraintes tome1
gradient conjugue cas quadratique et non quadratique
tp n7
cmoptimisation 1
14 problemes ouverts sur le gradient conjugue sujets de theses de doctorat
anamat

Sur le même sujet..




🚀  Page générée en 0.011s