Gradient et optimisation multidimensionnelle

Définition du gradient

Pour une fonction différentiable $f(x, y)$ à deux variables, en coordonnées euclidiennes, le gradient, noté $\nabla f$, est défini comme le vecteur de ses dérivées partielles. Formellement,

$$\nabla f = \left( \frac{\partial f}{\partial x}, \frac{\partial f}{\partial y} \right)$$

Pour $f(x, y) = x^2 + y^2$, le gradient est $\nabla f = (2x, 2y)$. Ce vecteur pointe dans la direction de la plus forte augmentation locale, et sa norme donne ce taux de variation directionnel maximal. En un point régulier, le gradient est perpendiculaire — et non tangent — à la courbe de niveau passant par ce point.

Gradient en un point spécifique

Pour trouver le gradient de $f(x, y) = x^2 + y^2$ en un point particulier, par exemple $(2, 3)$, nous substituons $x = 2$ et $y = 3$ dans la formule du gradient :

$$\nabla f = (2 \cdot 2, 2 \cdot 3) = (4, 6)$$

Ce résultat correspond au gradient de $f$ au point $(2, 3)$ et représente le vecteur pointant dans la direction de la plus forte augmentation de $f$ à partir de ce point.

Pourquoi le gradient négatif donne une descente locale

Supposons $f$ différentiable en un point intérieur $q$. Pour un vecteur unitaire $u$ en norme euclidienne, la dérivée directionnelle est

$$D_u f(q)=\lim_{t\to0}\frac{f(q+tu)-f(q)}t=\nabla f(q)^Tu.$$

Cauchy–Schwarz donne $-\|\nabla f(q)\|_2\le D_u f(q)\le\|\nabla f(q)\|_2$. Si le gradient est non nul, la borne inférieure est atteinte pour $u=-\nabla f(q)/\|\nabla f(q)\|_2$. C’est la plus forte descente parmi les directions unitaires euclidiennes, sans garantie pour un grand pas ou des coordonnées redimensionnées. En particulier,

$$f(q-\alpha\nabla f(q))=f(q)-\alpha\|\nabla f(q)\|_2^2+o(\alpha),$$

donc des pas positifs suffisamment petits diminuent $f$. Pour le gradient $(4,6)$, la direction unitaire correspondante est $(-2,-3)/\sqrt{13}$ et son taux vaut $-2\sqrt{13}$. Un vecteur tangent $v$ à une courbe de niveau régulière vérifie $\nabla f(q)^Tv=0$, en dérivant la valeur constante le long de cette courbe.

Hessienne et courbure directionnelle

Pour une fonction deux fois continûment différentiable, la Hessienne rassemble les dérivées partielles secondes, $H_{ij}(q)=\partial^2 f(q)/\partial x_i\partial x_j$. L’égalité des dérivées mixtes la rend symétrique. Le développement au second ordre est

$$f(q+v)=f(q)+\nabla f(q)^Tv+\tfrac12v^TH(q)v+o(\|v\|_2^2).$$

La forme quadratique $v^THv$ décrit la courbure selon le déplacement. Une matrice réelle symétrique est définie positive si cette forme est positive pour tout $v$ non nul, et semi-définie positive si elle est toujours non négative. Cela équivaut à des valeurs propres toutes positives ou non négatives, respectivement. Une matrice indéfinie possède des directions de signes opposés. Voir Boyd et Vandenberghe, annexe A et §3.1.4 pour ces définitions et le critère de convexité du second ordre.

Pour $x^2-y^2$, $H=\operatorname{diag}(2,-2)$ : la courbure est positive sur l’axe x et négative sur l’axe y. Pour une matrice symétrique $2\times2$, la définition positive équivaut à $H_{11}>0$ et $\det H>0$, le test utilisé dans la régression ci-dessous. Une Hessienne nulle ne tranche pas : $x^4+y^4$, $-x^4-y^4$ et $x^4-y^4$ en ont une à l’origine, mais donnent un minimum, un maximum et un point-selle. La garantie globale de l’optimisation convexe exige une Hessienne semi-définie positive sur tout un domaine ouvert convexe, pas seulement en un point.

Un point stationnaire a un gradient nul ; un minimum local est optimal parmi les points admissibles voisins ; un minimum global l’est sur tout l’ensemble admissible. Ces notions diffèrent : $x^2-y^2$ possède un point-selle stationnaire à l’origine, tandis que minimiser $x$ sur $[0,1]$ donne la solution de bord $0$, de dérivée $1$. En un point stationnaire d’une fonction deux fois continûment différentiable, une Hessienne définie positive garantit un minimum local strict ; une Hessienne indéfinie donne un point-selle, et une Hessienne singulière semi-définie positive exige une analyse supplémentaire.

Application à l'optimisation

En un extremum local intérieur d’une fonction différentiable, la dérivée doit être nulle ; la réciproque n’est pas garantie. Pour $f(x)=x^2$, résoudre $f'(x)=2x=0$ donne le candidat $x=0$ ; l’inégalité distincte $x^2\ge0$ prouve qu’il s’agit du minimum global. Les points du bord et les points non dérivables nécessitent un examen séparé.

Pour les fonctions de deux variables ou plus, telles que $f(x, y) = x^2 + y^2$, le processus d'optimisation recherche les points où le gradient est nul, c'est-à-dire $\nabla f = \vec{0}$. Cette condition implique que les deux dérivées partielles, $\frac{\partial f}{\partial x}$ et $\frac{\partial f}{\partial y}$, sont nulles. La résolution du système d'équations

$$\begin{align*} \frac{\partial f}{\partial x} = 2x &= 0 \\ \frac{\partial f}{\partial y} = 2y &= 0 \end{align*}$$

donne le point $(0, 0)$ comme emplacement du minimum. Cette recherche se généralise aux fonctions d'un nombre quelconque de variables, mais un gradient nul n'identifie qu'un candidat stationnaire. Le point peut être un minimum, un maximum ou un point-selle, de sorte qu'un test du second ordre ou un autre argument reste nécessaire.

Optimisation dans un sauna bidimensionnel

Considérer un sauna comme un espace à deux dimensions permet de se déplacer dans n'importe quelle direction au sein d'une pièce de 5x5, avec pour objectif de trouver le point le plus froid en fonction de la distribution de température.

• Fonction de température : Pour une position donnée $(x, y)$, la température est une fonction $T(x, y)$ représentée par la hauteur dans un tracé en trois dimensions. Les zones chaudes sont indiquées en rouge (valeurs plus élevées) et les zones froides en bleu (valeurs plus basses).

• Objectif : Minimiser $T(x,y)$ sur le carré fermé $[0,5]^2$. Un minimiseur global n’est pas nécessairement intérieur et les valeurs aux autres points ne sont pas nécessairement strictement supérieures.

• Approche mathématique : Le processus consiste à calculer les dérivées partielles $\frac{\partial T}{\partial x}$ et $\frac{\partial T}{\partial y}$, à les égaler à zéro et à résoudre pour $x$ et $y$ afin de trouver les points minima potentiels.

• Exemple de fonction : $T(x, y) = 85 - \frac{1}{90}x^2(x - 6)y^2(y - 6)$.

• Dérivées partielles :

  $$\frac{\partial f}{\partial x} = -\frac{1}{90}x(3x - 12)y^2(y - 6)$$ $$\frac{\partial f}{\partial y} = -\frac{1}{90}x^2(x - 6)y(3y - 12)$$

• Recherche du minimum : Résoudre $\frac{\partial T}{\partial x}=0$ et $\frac{\partial T}{\partial y}=0$ donne uniquement les candidats intérieurs. Il faut aussi examiner les quatre côtés et les sommets ; le raisonnement complet ci-dessous inclut le bord.

Pour le sauna, prenons le domaine $[0,5]^2$. Posons $h(t)=t^2(6-t)$, d’où $T=85-h(x)h(y)/90$. Sur $[0,5]$, $h\ge0$ et $h'(t)=3t(4-t)$ : $h$ croît jusqu’à $h(4)=32$, puis décroît. L’unique minimum global est donc $(4,4)$, avec $T=3313/45\approx73.6222$. Les bords $x=0$ ou $y=0$ sont à $85$ ; ceux de coordonnée $5$ ont pour minimum $85-25\cdot32/90\approx76.1111$. Le bord est ainsi vérifié, pas seulement les points stationnaires.

Optimisation de la régression linéaire

La régression linéaire, un modèle fondamental d'apprentissage automatique, est optimisée par une approche de calcul multidimensionnel similaire, mais consiste à trouver la droite qui s'ajuste le mieux à un ensemble de points de données.

• Énoncé du problème : Étant donné les coordonnées de lignes électriques, la tâche consiste à minimiser le coût total de leur raccordement à une ligne principale de fibre optique. Dans ce modèle illustratif, le coût est proportionnel aux résidus verticaux au carré, pas aux distances les plus courtes à la droite.
• Formulation mathématique : L'équation de droite $y = mx + b$ représente la ligne de fibre, $m$ et $b$ étant respectivement la pente et l'ordonnée à l'origine. L'objectif d'optimisation est de minimiser la fonction de coût total $E(m, b)$, qui dépend de $m$ et $b$.
• Fonction de coût : Prenons les données illustratives $(1,2),(2,5),(3,3)$. Développer la somme des résidus verticaux au carré $E(m,b)=(m+b-2)^2+(2m+b-5)^2+(3m+b-3)^2$ donne $14m^2+3b^2+38+12mb-42m-20b$.
• Dérivées partielles et optimisation :
  • $\frac{\partial E}{\partial m} = 28m + 12b - 42$
  • $\frac{\partial E}{\partial b} = 6b + 12m - 20$
• Solution : Égaler $\frac{\partial E}{\partial m} = 0$ et $\frac{\partial E}{\partial b} = 0$ et résoudre pour $m$ et $b$ donne les paramètres de droite optimaux minimisant le coût.
• Résultat : Les valeurs optimales $m = \frac{1}{2}$ et $b = \frac{7}{3}$ sont trouvées, avec un coût minimal de 4.167.

Pour la quadratique de régression, la Hessienne est $\begin{pmatrix}28&12\\12&6\end{pmatrix}$, de premier mineur principal $28$ et de déterminant $24$. Elle est définie positive : $(1/2,7/3)$ est donc l’unique minimiseur global, avec $E_{\min}=25/6\approx4.1667$. La distance désigne ici un résidu vertical $y_i-(mx_i+b)$ ; le carré de la distance perpendiculaire serait divisé par $1+m^2$, ce qui changerait le problème. Pour le modèle statistique, voir Régression linéaire.

Descente de gradient : une méthode d'optimisation efficace

Lorsque résoudre directement les équations stationnaires est peu pratique, la descente de gradient fournit une alternative itérative. Elle n’est pas toujours plus rapide qu’un solveur direct, et la descente seule ne prouve ni convergence ni optimalité globale. La propriété locale découle de la différentiabilité, comme montré ci-dessous ; le guide à une variable fournit une implémentation respectant le domaine.

Mes lectures · Les notes ouvertes sont mémorisées dans ce navigateur.