Résumé note de cours de mathématiques , et optimisation,modélisation, apprentissage

Optimisation
Notes de cours

Master 1 Mathématiques, Modélisation, Apprentissage (MMA)
2021-2022




Quentin D ENOYELLE
Bureau 812-D


,Table des matières

1 Rappels et compléments de calculs différentiels 5
1.1 Cadre et notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Différentielle et gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.1 Différentielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.2 Gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.3 Dérivation des fonctions composées . . . . . . . . . . . . . . . . . . . 8
1.3 Différentielle seconde et matrice hessienne . . . . . . . . . . . . . . . . . . . . 8
1.4 Formules de Taylor .................................................................................................... 10

2 Problèmes d’optimisation : Existence et unicité des solutions 11
2.1 Cadre et vocabulaire .................................................................................................. 11
2.2 Généralités sur l’existence de solutions ..................................................................... 12
2.2.1 Existence d’une suite minimisante ................................................................ 12
2.2.2 Coercivité et existence d’une solution........................................................... 12
2.3 Extrema locaux et différentiabilité............................................................................. 13
2.3.1 Définitions ..................................................................................................... 13
2.3.2 Extrema locaux et condition d’ordre un ........................................................ 14
2.3.3 Extrema locaux et conditions d’ordre deux................................................... 14
2.4 Ensembles convexes .................................................................................................. 16
2.5 Fonctions convexes .................................................................................................... 18
2.5.1 Définition et exemples .................................................................................. 18
2.5.2 Caractérisation des fonctions convexes différentiables ................................. 19
2.5.3 Caractérisation des fonctions convexes deux fois différentiables ................. 20
2.5.4 Problèmes d’optimisation convexes .............................................................. 22
2.6 Etude des fonctionnelles quadratiques ....................................................................... 23

3 Algorithmes de descente de gradient pour les problèmes sans contraintes 25
3.1 Méthode de descente .................................................................................................. 25
3.2 Algorithme de descente de gradient à pas optimal..................................................... 26
3.2.1 Définition de l’algorithme et premières propriétés ....................................... 26
3.2.2 Forte convexité .............................................................................................. 27
3.2.3 Convergence de l’algorithme du gradient à pas optimal ............................... 29
3.3 Descente de gradient préconditionné à rebroussement d’Armijo .............................. 32
3.3.1 Choix du pas par rebroussement d’Armijo ................................................... 32
3.3.2 Algorithme de descente de gradient préconditionné ..................................... 33
3.3.3 Convergence de l’algorithme de descente de gradient préconditionné à
rebroussement d’Armijo ............................................................................... 33


2

,4 Méthode de Newton Amortie 37
4.1 Méthode de Newton amortie...................................................................................... 37
4.1.1 Définition et premières propriétés ................................................................. 37
4.1.2 Critère d’arrêt de la méthode de Newton amortie ......................................... 39
4.2 Convergence de la méthode de Newton amortie ....................................................... 40




3

, Introduction

Ce cours est une introduction aux problèmes d’optimisation. Le cours se focalise sur des
problèmes d’optimisation sans contrainte pour les fonctions suffisamment différentiables en di-
mension finie. Après une introduction des différentes notions mathématiques nécessaires (rap-
pels de calcul différentiel, conditions d’optimalité, convexité, etc.), une part importante est don-
née à l’exposition des différents algorithmes classiques d’optimisation, l’étude théorique de leur
convergence, ainsi que leur mise en œuvre pratique. Le langage Python sera utilisé en séance
de Travaux Pratiques (TP).
L’auteur remercie Bruno Galerne qui est à l’origine de ce poly, Joan Glaunès pour ses nom-
breux conseils, et enfin Quentin Mérigot car le Chapitre 3 de ce poly est fortement inspiré de
ses notes de cours http://quentin.mrgt.fr/cours/m315/.

Les principaux ouvrages de référence pour ce cours sont :

[ROUVIÈRE] François ROUVIÈRE, Petit guide de calcul différentiel à l’usage de la license
et de l’agrégation, troisième édition, Cassini, 2009
[CIARLET] Philippe G. CIARLET, Introduction à l’analyse numérique matricielle et à l’op-
timisation, cinquième édition, Dunod, 1998
[BOYD & VANDENBERGHE] Stephen BOYD and Lieven VANDENBERGHE Convex Opti-
mization, Cambridge University Press, 2004.
Ouvrage téléchargeable gratuitement ici :
http://stanford.edu/~boyd/cvxbook/
[ALLAIRE & KABER] Grégoire A LLAIRE et Sidi Mahmoud KABER, Algèbre linéaire nu-
mérique, Ellipses, 2002

La page web dédiée à ce cours est ici :
https://qdenoyelle.github.io/M1_Optim/




4