Extrema

Table des matières

19.1 INTRODUCTION
19.2 COURS
19.3 EXEMPLES
EXERCICES

19.1 INTRODUCTION

19.1.1 Explorer l'apprentissage comme un processus d'optimisation

L'apprentissage est un processus d'optimisation ayant pour but d'augmenter les connaissances, les compétences et la puissance créative. Cela s'applique aussi bien à l'éducation qu'à l'apprentissage automatique. Afin de suivre le processus d'apprentissage, nous avons besoin d'une fonction qui mesure les progrès. Une métrique ancienne est la moyenne générale (GPA) qui fait la moyenne de certaines notes dans un système éducatif, une autre est le score de QI mesuré par des tests. Un autre exemple de métrique dans un contexte de recherche est un score de réseau social comme le nombre de citations ou l'indice h. Pour une voiture conduisant de manière autonome, cela pourrait être $f (x) = 100 / (1 + N (x))$ où $N (x)$ est le nombre d'accidents produits en utilisant la configuration de paramètres $x$ sur une période fixe.

**Figure 1.** L'image du Klondike de David Perkins illustre la recherche de solutions dans un paysage de dimension supérieure défini par une fonction de hauteur $f$ . Le calcul suggère de suivre le gradient $\nabla f$ car cela mène à des **maxima locaux**. Pour trouver les maxima globaux (qui pourraient être des idées révolutionnaires), nous devons chercher plus intensément et dresser une liste de tous les maxima. Le processus tire son nom de la région du Klondike au Canada, devenue tristement célèbre pendant la ruée vers l'or.

19.1.2 L'IA conquerra-t-elle tous les domaines ?

Une fois le cadre et la fonction $f$ fixés, la question est de savoir comment augmenter $f$ le plus efficacement possible. Cette image simpliste est assez efficace tant pour l'intelligence humaine que pour l'intelligence artificielle. Pour de nombreuses fonctions qui ont été considérées (gagner aux échecs, puissance de calcul, rétention de données, détection de caractéristiques, conduite de voitures ou pilotage d'avions), les machines ont progressé rapidement. Il n'y a pratiquement personne qui doute sérieusement que les humains finiront par perdre la bataille pour toute fonction $f$ qui peut être considérée. Il existe encore des domaines où les machines n'ont pas pris le dessus. Des exemples sont l'art ou la rédaction d'articles scientifiques.¹

19.1.3 L'avantage de l'apprentissage automatique dans l'optimisation basée sur le gradient

Une fois qu'une machine connaît la fonction $f$ , elle peut déterminer confortablement à partir d'une position $x$ dans quelle direction changer pour augmenter $f$ le plus rapidement. La direction de l'augmentation la plus rapide est la direction du gradient $\nabla f$ de $f$ . En calcul, nous examinons des situations où la position ne comporte que quelques variables. Le calcul à une variable traite de la situation d'une variable. Nous examinons ici la situation avec $n$ variables mais nous travaillerons principalement avec $2$ variables car cela donne déjà l'idée principale. Le principe est que nous avons atteint un optimum où aucun changement ne peut plus augmenter la fonction $f$ . Cela signifie mathématiquement que la dérivée $d f$ de $f$ est nulle. Nous appelons ces points des "points critiques".

19.1.4 Utiliser les gradients pour trouver la direction d'amélioration

Examinons d'abord le taux de variation d'une fonction le long d'une direction $v$ . Prenons une courbe $r (t) = x + t v$ où $v$ est un vecteur unitaire. Par la règle de la chaîne, le taux de variation en $x$ est donné par f(r(t))=\nabla f(r(t)) \cdot r^{\prime}(0)=\nabla f(x) \cdot v. Nous savons pour le produit scalaire que cela est égal à $| \nabla f (x) | | v | \cos (α) = | \nabla f (x) | \cos (α) .$ Ceci est maximisé pour $\cos (α) = 1$ ce qui signifie que $v$ pointe dans la même direction que $\nabla f$ . Ainsi, le gradient pointe dans la direction de l'augmentation maximale. C'est important à retenir. Si vous êtes dans un paysage donné par la hauteur $f (x)$ , vous devez aller dans la direction de $\nabla f (x) / | \nabla f (x) |$ afin d'augmenter le plus. Bien sûr, cela n'a pas de sens si $\nabla f (x) = 0$ mais c'est la situation où vous êtes à un maximum, et où vous ne pouvez plus augmenter $f$ .

19.2 COURS

19.2.1 Trouver les optima avec les gradients

Toutes les fonctions sont supposées ici être de classe $C^{2}$ , c'est-à-dire deux fois continûment différentiables. Tout commence par une observation remontant à Pierre de Fermat :

Théorème 1. Si $x_{0}$ est un maximum de $f : ℝ^{m} \to ℝ$ , alors $\nabla f (x_{0}) = 0$ .

Preuve. Nous prouvons cela par contradiction. Supposons $\nabla f (x_{0}) \neq 0$ , définissons le vecteur $v =$ $\nabla f (x_{0})$ et considérons $g (t) = f (x_{0} + t v)$ , qui est une fonction d'une variable. Par la règle de la chaîne, elle satisfait g^{\prime}(0)=\nabla f(x_{0}+0 v) \cdot v=|\nabla f|^{2}>0. Cela signifie que $f (x_{0} + t v) > 0$ pour de petits $t > 0$ . Le point $x_{0}$ ne peut pas avoir été maximal. C'est une contradiction. ◻

19.2.2 Dévoiler les points critiques

Un point $x$ avec $\nabla f (x) = 0$ est appelé un point critique de $f$ . Par la formule de Taylor, nous avons en un point critique $x_{0}$ l'approximation quadratique $Q (x) = f (x_{0}) + (x - x_{0})^{T} H (x_{0}) (x - x_{0}) / 2,$ où $H (x_{0})$ est la matrice hessienne $H (x_{0}) = [\begin{array}{llll} f_{x_{1} x_{1}} & f_{x_{1} x_{2}} & \dots & f_{x_{1} x_{m}} \\ f_{x_{2} x_{1}} & f_{x_{2} x_{2}} & \dots & f_{x_{2} x_{m}} \\ \dots & \dots & \dots & \dots \\ f_{x_{m} x_{1}} & f_{x_{m} x_{2}} & \dots & f_{x_{m} x_{m}} \end{array}] .$

19.2.3 Le test de la dérivée seconde entre en jeu

Comme en une dimension, avoir un point critique ne garantit pas que ce point soit un maximum ou un minimum local. Le test de la dérivée seconde en calcul à une variable garantit que si f^{\prime}(x_{0})=0, f^{\prime \prime}(x_{0})>0, nous avons un minimum local et si f^{\prime}(x_{0})=0, f^{\prime \prime}(x_{0})<0, nous avons un maximum local. Si f^{\prime \prime}(x_{0})=0, nous ne pouvons rien dire sans examiner les dérivées d'ordre supérieur.

19.2.4 Matrices définies positives et négatives

Une matrice $A$ est dite définie positive si $v \cdot A v > 0$ pour tout vecteur $v \neq 0$ . Elle est dite définie négative si $v \cdot A v < 0$ pour tout vecteur $v \neq 0$ . Une matrice diagonale avec des entrées diagonales positives est définie positive. Dans les énoncés suivants, nous supposons que $x_{0}$ est un point critique.

19.2.5 Dévoiler le rôle des hessiennes définies positives

Nous disons que $x_{0}$ est un maximum local de $f$ s'il existe $r > 0$ tel que $f (x) \leq f (x_{0})$ pour tout $| x - x_{0} | < r$ . Nous disons que c'est un minimum local de $f$ si $f (x) \geq f (x_{0})$ pour tout $| x - x_{0} | < r$ . Comment pouvons-nous vérifier si un point est un maximum ou un minimum local ?

Théorème 2. Supposons $\nabla f (x_{0}) = 0$ . Si $H (x_{0})$ est définie positive, alors $x_{0}$ est un minimum local. Si $H (x_{0})$ est définie négative, alors $x_{0}$ est un maximum local.

Preuve. Comme $\nabla f (x_{0}) = 0$ , l'approximation quadratique en $x_{0}$ est $Q (x) = f (x_{0}) + H (x_{0}) v \cdot v / 2 > f (x_{0})$ pour de petits $v = x - x_{0}$ non nuls et la hessienne $H$ . L'énoncé analogue pour le minimum peut être déduit en remplaçant $f$ par $- f$ . ◻

19.2.6 Classification des extremums en deux dimensions

Examinons le cas où $f (x, y)$ est une fonction de deux variables telle que $f_{x} (x_{0}, y_{0}) = 0$ et $f_{y} (x_{0}, y_{0}) = 0$ . La matrice hessienne est

$H (x_{0}, y_{0}) = [\begin{array}{ll} f_{x x} & f_{x y} \\ f_{y x} & f_{y y} \end{array}]$

Dans ce cas bidimensionnel, nous pouvons classer les points critiques si le déterminant $D = \det (H) = f_{x x} f_{y y} - f_{x y}^{2}$ de $H$ est non nul. Le nombre $D$ est aussi appelé le discriminant en un point critique.

**Figure 2.** $f = x^{2} + y^{2}$ donne un minimum, $f = - x^{2} - y^{2}$ un maximum et $f = x^{2} - y^{2}$ un point-selle. Le cas $f = x^{2} y - y x^{2}$ n'est pas Morse.

19.2.7 Fonctions de Morse et le test de la dérivée seconde

Nous disons que $(x_{0}, y_{0})$ est un point de Morse si $(x_{0}, y_{0})$ est un point critique et que le déterminant est non nul. Une fonction de classe $C^{2}$ est une fonction de Morse si tout point critique est de Morse. Des exemples de fonctions de Morse sont $f (x, y) = x^{2} + y^{2}$ , $f (x, y) = - x^{2} - y^{2}$ et $f (x, y) = x^{2} - y^{2}$ . Ce dernier cas est appelé un point-selle hyperbolique. En général, un point critique est un point-selle hyperbolique si $D \neq 0$ et s'il n'est ni un maximum ni un minimum. Voici le test de la dérivée seconde en dimension $2$ :

Théorème 3. Supposons que $f \in C^{2}$ ait un point critique $(x_{0}, y_{0})$ avec $D \neq 0$ .

Si $D > 0$ et $f_{x x} > 0$ alors $(x_{0}, y_{0})$ est un minimum local.
Si $D > 0$ et $f_{x x} < 0$ alors $(x_{0}, y_{0})$ est un maximum local.
Si $D < 0$ alors $(x_{0}, y_{0})$ est un point-selle hyperbolique.

Preuve. Après translation $(x, y) \to (x - x_{0}, y - y_{0})$ et remplacement de $f$ par $f -$ $f (x_{0}, y_{0})$ , nous avons $(x_{0}, y_{0}) = (0, 0)$ et $f (0, 0) = 0$ . Au point critique, l'approximation quadratique est maintenant $Q (x, y) = a x^{2} + 2 b x y + c y^{2} .$ Cela peut être réécrit comme $a (x + \frac{b}{a} y)^{2} + (c - \frac{b^{2}}{a}) y^{2} = a (A^{2} + D B^{2})$ avec $A = (x + \frac{b}{a} y), B = b^{2} / a^{2}$ et le discriminant $D$ . Si $a = f_{x x} > 0$ et $D > 0$ alors $c - b^{2} / a > 0$ et la fonction a des valeurs positives pour tout $(x, y) \neq (0, 0)$ . Le point $(0, 0)$ est alors un minimum. Si $a = f_{x x} < 0$ et $D > 0$ , alors $c - b^{2} / a < 0$ et la fonction a des valeurs négatives pour tout $(x, y) \neq (0, 0)$ et le point $(x, y)$ est un maximum local. Si $D < 0$ , alors $f$ prend à la fois des valeurs négatives et positives près de $(0, 0)$ . ◻

19.2.8 De la hessienne à la courbure de Gauss

On peut se demander pourquoi $f_{x x}$ est choisi et non $f_{y y}$ . Cela n'a pas d'importance, car si $D > 0$ , alors $f_{x x}$ et $f_{y y}$ doivent être non nuls et avoir le même signe. Au lieu de $f_{x x}$ , on aurait aussi pu choisir la trace plus naturelle $tr (H)$ . Elle est invariante par changement de coordonnées, tout comme le déterminant $D$ . Le discriminant $D$ se trouve également être la courbure de Gauss de la surface en ce point.

19.2.9 Le lemme de Morse

En dimensions supérieures, la situation est décrite par le lemme de Morse. Il indique qu'à proximité d'un point critique, il existe un changement de coordonnées $ϕ$ tel que $g (x) = f (ϕ (x))$ est une fonction quadratique $f (x) = B (x - x_{0}) \cdot (x - x_{0})$ où $B$ est diagonale avec des entrées $+ 1$ ou $- 1$ . Le point critique peut alors se voir attribuer un indice de Morse, le nombre d'entrées $- 1$ dans $B$ . Le lemme de Morse est en réalité un théorème (les théorèmes sont plus importants que les lemmes=théorèmes auxiliaires).

Théorème 4. Près d'un point critique de Morse $x_{0}$ d'une fonction $C^{2}$ $f$ , il existe un changement de coordonnées $ϕ : ℝ^{m} \to ℝ^{m}$ tel que $g (x) = f (ϕ (x)) - f (x_{0})$ est $g (x) = - x_{1}^{2} - \dots - x_{k}^{2} + x_{k + 1}^{2} + \dots + x_{m}^{2} .$

Preuve. On utilise une récurrence par rapport à $m$ .

Base de récurrence : Pour $m = 1$ , le résultat indique que pour un point critique de Morse, la fonction ressemble à $y = x^{2}$ ou $y = - x^{2}$ . Montrons d'abord que si f(0)=f^{\prime}(0)=0, f^{\prime \prime}(0) \neq 0, alors $f (x) = x^{2} h (x)$ ou $f (x) = - x^{2} h (x)$ pour une fonction $C^{2}$ positive $h$ . Preuve. Par un changement linéaire de coordonnées, on suppose $x_{0} = 0$ et $f (0) = 0$ . Il existe alors $g (x)$ tel que $f (x) = x g (x)$ : c'est $g (x) = f (x) / x$ pour $x \neq 0$ et à la limite $x \to 0$ la valeur de $lim_{x \to 0} (f (x) -$ f(0)) / x=f^{\prime}(0). Par la règle du produit, f^{\prime}(x)=g(x)+x g^{\prime}(x) avec $g (0) = 0$ . Comme f^{\prime}(0)=g(0)=0, on peut définir $f (x) / x^{2}$ pour $x \neq 0$ et prendre la limite $x \to 0$ , car en appliquant deux fois la règle de l'Hôpital, la limite est f^{\prime \prime}(0). Le changement de coordonnées est maintenant donné par une fonction $y = ϕ (x)$ satisfaisant $g (x, y) = y \sqrt{h (y)} = x$ . La différentiation implicite donne $g_{y} (0, 0) = \sqrt{h (y)} \neq 0$ de sorte que, par le théorème des fonctions implicites, $y (x)$ existe.
Étape de récurrence $𝒎 \to 𝒎 + 1$ : on note d'abord que le développement de Taylor pour $C^{2}$ avec reste implique que $f (x_{1}, \dots, x_{n}) = \sum_{i, j} x_{i} x_{j} h_{i j} (x_{1}, \dots, x_{n})$ avec des fonctions continues $h_{i j}$ . De plus, la valeur $h_{i j} (0) = f_{x_{i} x_{j}} (0) = H_{i j} (0)$ sont les coordonnées de la hessienne. Appliquons d'abord une rotation pour que $h_{11} \neq 0$ . Considérons maintenant $x_{1}$ et gardons les autres coordonnées constantes. Comme en (i), trouvons un changement de coordonnées $ϕ$ tel que $f (ϕ (x)) = \pm x_{1}^{2} + g (x_{2}, \dots, x_{m})$ , où $g$ hérite des propriétés mais est d'une dimension de moins. Par hypothèse de récurrence, il existe un second changement de coordonnées tel que $g (ψ (x)) = x_{2}^{2} - \dots - x_{l}^{2} + x_{l + 1}^{2} + \dots + x_{m}^{2} .$ La combinaison de $ϕ$ et $ψ$ produit la forme normale de Morse.

◻

19.3 EXEMPLES

Exemple 1. Q : Classifier les points critiques de $f (x, y) = x^{3} - 3 x - y^{3} - 3 y$ .
R : Comme $\nabla f (x, y) = {[3 x^{2} - 3, - 3 y^{2} + 3]}^{T},$ les points critiques sont $(1, 1)$ , $(- 1, 1)$ , $(1, - 1)$ et $(- 1, - 1)$ . On calcule $H (x, y) = [\begin{array}{cc} 2 x & 0 \\ 0 & - 2 y \end{array}] .$ Pour $(1, 1)$ et $(- 1, - 1)$ on a $D = - 4$ donc des points-selles. Pour $(- 1, 1)$ , on a $D = 4$ , $f_{x x} = - 2$ , un maximum local. Pour $(1, - 1)$ où $D = 4$ , $f_{x x} = 2$ on a un minimum local.

EXERCICES

Exercice 1.

Classifiez les points critiques de la fonction $f (x, y) = x^{2} + y^{3} - x y .$ (Maxima, minima ou points-selles).
Faites maintenant de même pour $f (x, y, z) = x^{2} + y^{3} - x y + z^{2}$ et trouvez l'indice de Morse en chaque point critique.

Exercice 2. Trouvez tous les points critiques de la fonction $3$ D zone $51$ $f (x, y, z) = x^{51} - 51 x + y^{51} - 51 y + z^{51} - 51 z .$ Calculez la hessienne $H = d^{2} f$ en chaque point critique et déterminez les maxima (toutes les valeurs propres sont négatives) et les minima (toutes les valeurs propres sont positives).
P.S. La zone $51$ est un vieux chapeau. Mais la zone $51$ en $3$ D est encore hautement classifiée et il se murmure qu'elle se trouve près de la face cachée de la lune.

Exercice 3. Où sur la surface paramétrée $r (u, v) = [u^{2}, v^{3}, u v]$ la température $T (x, y, z) = 12 x + y - 12 z$ est-elle minimale ? Classifiez tous les points critiques de la fonction $f (u, v) = T (r (u, v))$ . [Si vous avez trouvé la fonction $f (u, v)$ , vous pouvez remplacer $u$ , $v$ par $x$ , $y$ si vous préférez travailler avec une fonction $f (x, y)$ .]

Exercice 4. Trouvez tous les points critiques de la fonction $f (x, y, z) = (x - 1)^{2} - y^{2} + x z^{2} .$ Dans chaque cas, trouvez la matrice hessienne. Calculez également ici les valeurs propres. Ce sont des nombres $λ$ tels que $H v = λ v$ pour un vecteur non nul. On peut les trouver en cherchant les racines du polynôme caractéristique $χ_{H} (λ) = \det (L - λ)$ . Vous pouvez les calculer sur un ordinateur. Trouvez dans chaque cas les valeurs propres.

Exercice 5.

Trouvez une fonction $f (x, y)$ avec $3$ maxima et $3$ points-selles et un minimum.
Vous voyez ci-dessous une carte de contours d'une fonction de deux variables. Combien y a-t-il de points critiques ? La fonction est-elle une fonction de Morse ?

Il pourrait y avoir de la résistance : les humains pourraient décider de ne pas citer les découvertes scientifiques faites par des machines. D'un autre côté, qui ne voudrait pas apprendre une « théorie du tout » même si elle est découverte par une machine ?↩︎