Lecture zen
\(df(x)(h)\leq 0\) car \(\frac{f(x+th)-f(x)}{t} \leq 0\) si \(t\leq 0\)
et donc \(f(x+tv)-f(x)\) est alors négatif pour ces valeurs de \(t\) (à part pour \(t=0\)).
Une fonction strictement convexe définie sur une partie convexe admet au plus un minimum et si un tel minimum existe il est strict.
A propos des extrema...
A propos des extrema...
Extrema
Les extrema sont l’exemple naturel de mathématiques directement utiles. Si vous avez un processus industriel dont les paramètres \(\theta\) entrainent un coût \(f(\theta)\), alors vous pouvez naturellement être intéressés par minimiser \(f(\theta)\); vous cherchez donc des extremas de \(f\). Après quelques généralités ([ext1]), nous nous pencherons sur la compacité ([ext2]), utile pour garantir l’existence d’extremas, puis sur le calcul différentiel ([ext3]) qui nous permettra de caractériser les extremas, et enfin sur la notion de convexité ([ext4]), qui permet de montrer qu’un optimum local est global, sans oublier une section pour ceux qui veulent aller plus loin ([ext5]). Quelques éléments plus pratiques sur la recherche d’extremas sont donnés en section [ananume].
Cadre et définitions
Pour ce chapitre, on travaillera sur une application \(f\) continue d’un ouvert \(U\) d’un espace de Banach \(E\) dans \(\mathbb{R}\).
(minimum relatif).
On définit de même les notions de maximum relatif, maximum relatif strict, maximum global, maximum global strict, en remplaçant les \(\leq\) par des \(\geq\) et les \(<\) par des \(>\).
On dit que \(f\) admet un minimum relatif ou minimum local en \(x\in U\) si il existe un voisinage \(V\) de \(x\) tel que pour tout \(v\) dans \(V\) \(f(x)\leq f(v)\).
On dit que \(f\) admet un minimum relatif strict ou minimum local strict en \(x\in U\) si il existe un voisinage \(V\) de \(x\) tel que pour tout \(v\neq x\) dans \(V\) \(f(x) < f(v)\).
On dit que \(f\) admet un minimum global en \(x\in U\) si pour tout \(v\) dans \(U\) \(f(x)\leq f(v)\).
On dit que \(f\) admet un minimum global strict en \(x\in U\) si pour tout \(v\neq x\) dans \(U\) \(f(x) < f(v)\).
Résultats liés à la compacité
Soit \(E\) un espace vectoriel normé de dimension finie et \(f\) \(C^0\) de \(E\) dans \(\mathbb{R}\) telle que \[lim_{{\parallel}x {\parallel}\to \infty} f(x) = \infty \] Alors \(f\) est minorée et atteint son minimum.
On se donne \(A>0\) tel que \({\parallel}x {\parallel}> A\) implique \(f(x)>f(0)\). On considère alors \(K=\overline B(0,A)\). \(K\) est fermé car on est en dimension finie (les compacts d’un espace vectoriel normé de dimension finie sont les fermés bornés). \(f\) atteint donc sa borne inf (voir corollaire [bornatt]).
La condition [coercitive] et d’autres conditions s’y rapportant sont parfois qualifiés de coercitivité.
Quelques applications:
\(\bullet\)La distance d’un point à un fermé non vide est minorée et le minimum est atteint.
Voir le corollaire [kkboudin] sur la trigonalisation de matrices complexes, ou la partie [srl] sur les suites récurrentes linéaires.
Résultats de calcul différentiel
Quand une fonction est dérivable, chercher un minimum local revient à chercher un point en lequel les dérivées (1ère et/ou seconde) vérifient certaines conditions; d’où l’importance de caractérisations locales (par calcul différentiel) des minima ou maxima d’une fonction.
Il est à noter que l’optimisation sous contraintes (cf section [ananume] pour quelques mots sur ce sujet) donne lieu à des conditions bien différentes.
Résultats au premier ordre
(Condition nécessaire du premier ordre).
Si \(x\) est un minimum relatif de \(f\) et si \(f\) est différentiable en \(x\), alors la différentielle de \(f\) en \(x\) est nulle.
\(df(x)(h)\geq 0\) car \(\frac{f(x+th)-f(x)}{t} \geq 0\) si \(t\geq 0\)
Pas de réciproque; par exemple \(x\mapsto x^3\) de \(\mathbb{R}\) dans \(\mathbb{R}\) a une différentielle nulle en \(0\) et n’a ni maximum ni minimum en zéro.
Si \(df(x)=0\), on dit que \(x\) est un point critique.
Pour aller plus loin on peut s’intéresser aux extréma liés; voir pour cela [CIA].
Résultats du second ordre
(Condition nécessaire du second ordre).
Alors si \(f\) admet un minimum local en \(x\), \(f''(x)\) est positive.
Soit \(f\) deux fois différentiable en \(x\).
Supposons \(f''(x)\) non positive; alors il existe \(v\) tel que \(f''(x)(v,v)\) soit \(<0\). On se donne un voisinage \(V\) de \(x\) sur lequel \(f\leq f(x)\) et sur lequel la formule de Taylor-Young [young] donne
\[f(x+t.v)\leq f(x) + \frac14 f''(x) (t v,t v)\] (rappelons que par le résultat précédent \(f'(x)\) est nul)
on peut toujours choisir un tel voisinage \(V\) car \[f(x+t.v) = f(x)+\frac12 f''(x) (t v,t v) + o(t^2)\]
pour \(t\) assez petit
(Condition suffisante du second ordre).
Supposons \(E\) de dimension finie. Soit \(f\) deux fois différentiables en \(x\), \(f'(x)=0\), et \(f''(x)\) définie positive. Alors \(f\) admet un minimum relatif strict en \(x\).
On considère simplement un minimum de \(f''(x)(u,u)\) pour \({\parallel}u {\parallel}=1\) et la conclusion vient rapidement.
Intuition On peut se passer d’hypothèse de dimension finie à condition d’imposer que \(f''(x)\) vérifie \(\exists \alpha>0 ; f''(x)(u,u)>\alpha {\parallel}u {\parallel}^2\).
La convexité
Pour une introduction à la convexité, voir la partie [convex].
Les résultats liés à la convexité sont très intuitifs, et se justifient rigoureusement sans trop de difficulté: on pourra consulter [CIA] pour moultes développements. Le théorème suivant est très naturel:
Un minimum local d’une fonction convexe définie sur une partie convexe est en fait un minimum global.
Bien sûr, cela ne nous dit pas comment traiter de problèmes non-convexes. Divers algorithmes permettent de trouver des minima de fonctions en très grande dimension et en temps raisonnable, lorsque le problème est très convexe; le cas général, non convexe, est bien sûr beaucoup plus délicat. Il est facile de montrer que l’algorithme consistant à simplement tirer au sort \(n\) points dans \(\mathbb{R}^d\) suivant une distribution gaussienne et à sélectionner le meilleur de ces points trouve l’essentiel minimum de toute fonction mesurable à mesure que \(n\to \infty\) (au sens où \(\inf_{i\in [[1,n]]} f(X_i)\) où les \(X_i\) sont aléatoires simples tend presque sûrement vers le minimum essentiel de \(f\), quelle que soit la fonction\(f\)). L’inconvénient de cet algorithme est bien sûr sa lenteur. Une façon de concilier cet algorithme et des méthodes plus usuelles de descente de gradient ou de Newton est d’effectuer plusieurs algorithmes de Newton (ou quasi-Newton) à partir de points initiaux différents. On peut aussi se référer à l’important champ des algorithmes évolutionnaires qui essaient de faire mieux (plus rapide) que la recherche aléatoire ci-dessus, tout en en préservant la robustesse.
Pour aller plus loin
La partie [ananume] contient quelques développements, dont l’indispensable méthode de Newton.
La notion de quasi-convexité, plus générale que la convexité, est parfois utile en recherche d’extrema; une fonction \(f\) est quasi-convexe si \(\{x;f(x)<t\}\) est convexe quel que soit \(t\). En particulier, certaines méthodes d’optimisation, dites méthodes de recherche directe (on trouvera plus facilement "direct search methods" sur internet), parviennent à trouver les minima de fonctions quasi-convexes sous des hypothèses très générales.
On peut aussi s’intéresser aux extrêmas d’une fonction, sous contraintes. On pourra pour cela consulter [CIA]. On n’a pas ici formulé les caractérisations par calcul différentiel de l’optimalité locale d’un point en termes de conditions sur le jacobien ou la hessienne. Le lecteur est encouragé à se reférer à la section [blon3] pour y découvrir la hessienne, à la section [jacobienne] pour y découvrir jacobienne et jacobien, et à [CIA] pour en apprendre plus sur le sujet de l’énorme lien entre algèbre linéaire (et en particulier matricielle) et optimisation. En résumé:
Bibliographie
- [POM] A. Pommellet, Cours d’analyse, Ellipses 1994.[CIA] P.G. Ciarlet, Introduction à l’analyse numérique matricielle et à l’optimisation, Dunod, 1998.
Barre utilisateur
[ID: 22] [Date de publication: 12 mars 2021 17:55] [Catégorie(s): Le cours d'agrégation ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 5 ] [Auteur(s): Christophe Antonini Olivier Teytaud Pierre Borgnat Annie Chateau Edouard Lebeau ]
Commentaires sur le cours
Documents à télécharger
L'article complet