Caractérisez les minimums d'une fonction

Imaginez un randonneur perdu dans le brouillard, sur un plateau vallonné. Il ne voit rien au-delà de quelques mètres, mais il sent sous ses pieds dans quel sens le terrain descend, et si le sol est creusé en cuvette ou bombé. Comment saura-t-il qu’il est arrivé au fond d’une vallée ? Et comment être sûr que ce n’est pas simplement un replat, ou un col entre deux sommets ?

Ces deux sensations, la pente et la courbure, ont un nom mathématique : le gradient et la Hessienne. Dans ce chapitre, vous allez les utiliser pour reconnaître un minimum, avant d’apprendre à le calculer numériquement aux chapitres 6 et 7. Notre fil rouge sera l’altitude du plateau, décrite par la fonction $g(x, y) = x^3 - 3x + y^2$.

La pente et la courbure : gradient et Hessienne

Pour une fonction $f$ de $n$ variables, le gradient en un point $x$ est le vecteur de ses dérivées partielles :

$$\nabla f(x) = \left( \frac{\partial f}{\partial x_1}(x), \dots, \frac{\partial f}{\partial x_n}(x) \right)$$

Il indique la direction de plus forte montée, et sa norme dit à quel point ça monte. Il est toujours perpendiculaire aux lignes de niveau (les courbes d’altitude constante d’une carte de randonnée). Son opposé, $-\nabla f(x)$, est donc la direction de plus forte descente : retenez-la, c’est tout le chapitre suivant.

La Hessienne est la matrice des dérivées secondes :

$$\nabla^2 f(x) = \left( \frac{\partial^2 f}{\partial x_i \, \partial x_j}(x) \right)_{1 \leq i, j \leq n}$$

Elle décrit la courbure. Quand $f$ est deux fois continûment dérivable (on dit de classe $C^2$), elle est symétrique, car l’ordre des dérivations n’importe pas (théorème de Schwarz).

Exemple

Pour l’altitude du plateau $g(x, y) = x^3 - 3x + y^2$ :

$$\nabla g(x, y) = \begin{pmatrix} 3x^2 - 3 \\ 2y \end{pmatrix}, \qquad \nabla^2 g(x, y) = \begin{pmatrix} 6x & 0 \\ 0 & 2 \end{pmatrix}$$

Au point $(2, 1)$, le gradient vaut $(9, 2)$ : le terrain monte fort vers l’est. Pour descendre au plus vite, le randonneur partira vers $(-9, -2)$, c’est-à-dire plein ouest, un peu vers le sud.

Le gradient est partout perpendiculaire aux lignes de niveau et pointe vers la montée. Autour de (1, 0), les courbes se referment en cuvette ; en (−1, 0), elles se croisent en X : c'est un col.

Gradient et Hessienne se combinent dans le développement de Taylor à l’ordre 2, qui décrit $f$ près d’un point $x$ :

$$f(x + h) = f(x) + \nabla f(x)^T h + \tfrac12 \, h^T \nabla^2 f(x) \, h + o(\lVert h \rVert^2)$$

• $h$ est un petit déplacement ;
• $\nabla f(x)^T h$ est la variation due à la pente ;
• $\tfrac12 h^T \nabla^2 f(x) h$ est la correction due à la courbure ;
• $o(\lVert h \rVert^2)$ désigne un reste négligeable devant $\lVert h \rVert^2$ quand $h$ tend vers 0.

C’est ce développement qui justifie toutes les conditions de la section suivante, et c’est aussi lui que la méthode de Newton exploitera au chapitre 7.

Les conditions d’optimalité

Condition du premier ordre : le gradient s’annule

Si $x^*$ est un minimum local d’une fonction dérivable $f$ (sur tout $\mathbb{R}^n$, sans contrainte), alors

$$\nabla f(x^*) = 0$$

L’argument est simple : si le gradient n’était pas nul, un petit pas dans la direction $-\nabla f(x^*)$ ferait baisser $f$ (d’après Taylor à l’ordre 1), et $x^*$ ne serait pas un minimum. Un point où le gradient s’annule s’appelle un point critique (ou stationnaire).

Mais attention, c’est une condition nécessaire, pas suffisante. Un sommet ou un col ont aussi une pente nulle. Il faut regarder la courbure pour trancher.

Condition du second ordre : la courbure

Rappelons qu’une matrice symétrique $H$ est semi-définie positive si $h^T H h \geq 0$ pour tout $h$ (toutes ses valeurs propres sont positives ou nulles), et définie positive si $h^T H h \gt 0$ pour tout $h \neq 0$ (toutes ses valeurs propres sont strictement positives).

• Condition nécessaire : si $x^*$ est un minimum local et $f$ est $C^2$, alors $\nabla^2 f(x^*)$ est semi-définie positive.
• Condition suffisante : si $\nabla f(x^*) = 0$ et $\nabla^2 f(x^*)$ est définie positive, alors $x^*$ est un minimum local strict.

Au point critique, Taylor se réduit à $f(x^* + h) \approx f(x^*) + \tfrac12 h^T \nabla^2 f(x^*) h$ : si ce terme est strictement positif dans toutes les directions, on remonte de tous les côtés, c’est une cuvette.

Le signe des valeurs propres de la Hessienne dit comment le terrain se courbe autour du point critique : cuvette, sommet ou col.

À retenir

Pour trouver les minimums locaux d’une fonction sans contrainte : chercher les points critiques ($\nabla f = 0$), puis examiner la Hessienne en chacun. Définie positive : minimum local strict. Définie négative : maximum local strict. Valeurs propres de signes opposés : point selle (un col). Semi-définie avec une valeur propre nulle : on ne peut pas conclure avec la Hessienne seule.

En dimension 2 : les notations de Monge

En deux variables, on note traditionnellement $r = \partial^2 f / \partial x^2$, $s = \partial^2 f / \partial x \partial y$ et $t = \partial^2 f / \partial y^2$. Le signe du déterminant $rt - s^2$ de la Hessienne (produit des deux valeurs propres) et celui de $r$ suffisent :

$rt - s^2$	$r$	Nature du point critique
$\gt 0$	$\gt 0$	minimum local
$\gt 0$	$\lt 0$	maximum local
$\lt 0$		point selle (col)
$= 0$		on ne peut pas conclure

Exemple

Les points critiques de l’altitude $g$ vérifient $3x^2 - 3 = 0$ et $2y = 0$, soit $(1, 0)$ et $(-1, 0)$.

• En $(1, 0)$ : $r = 6$, $s = 0$, $t = 2$, donc $rt - s^2 = 12 \gt 0$ et $r \gt 0$. C’est un minimum local, d’altitude $g(1, 0) = -2$ : le fond d’une vallée.
• En $(-1, 0)$ : $r = -6$, $t = 2$, donc $rt - s^2 = -12 \lt 0$. C’est un col : en allant vers l’est ou l’ouest le terrain descend, vers le nord ou le sud il monte. Son altitude est $g(-1, 0) = 2$.

Numériquement, on calcule directement les valeurs propres de la Hessienne :

import numpy as np

def hessienne_g(x, y):
    return np.array([[6.0 * x, 0.0], [0.0, 2.0]])

for point in [(1, 0), (-1, 0)]:
    vp = np.linalg.eigvalsh(hessienne_g(*point))   # valeurs propres d'une matrice symétrique
    print(point, vp)   # (1, 0) : 2 et 6, toutes positives ; (-1, 0) : -6 et 2, signes opposés

Minimum local ou global ? L’existence

Le randonneur a trouvé le fond de la vallée $(1, 0)$, à l’altitude $-2$. Est-ce le point le plus bas du plateau ? Non ! Allez vers l’ouest : $g(-3, 0) = -27 + 9 = -18$. Et plus on s’éloigne, plus on descend, puisque $x^3$ tend vers $-\infty$. La fonction $g$ n’a aucun minimum global : son unique minimum local n’est qu’un creux sur une pente qui plonge.

Coupe du plateau le long de y = 0 : le creux en (1, 0) est un minimum local, mais le terrain descend sans fin vers l'ouest. Il n'y a pas de minimum global.

Les conditions d’optimalité ne regardent que le voisinage du point. Pour garantir qu’un minimum global existe, on dispose de deux résultats classiques :

• Théorème de Weierstrass : une fonction continue sur un ensemble compact (fermé et borné) y atteint son minimum et son maximum.
• Coercivité : si $f$ est continue sur $\mathbb{R}^n$ (ou sur un fermé) et coercive, c’est-à-dire $f(x) \to +\infty$ quand $\lVert x \rVert \to +\infty$, alors $f$ admet un minimum global. L’idée : loin de l’origine, $f$ est trop grande pour contenir le minimum, qui se trouve donc dans une boule, un compact.

Exemple

En TP, nous avons minimisé $f(x) = x^4 - 7x + 8$. Le terme $x^4$ l’emporte sur $-7x$ à l’infini, donc $f$ est coercive et admet un minimum global. Son unique point critique vérifie $f'(x) = 4x^3 - 7 = 0$, soit $x^* = (7/4)^{1/3} \approx 1{,}2051$, où $f(x^*) \approx 1{,}6734$. Comme le minimum global existe et qu’il doit être un point critique, c’est forcément lui.

Piège

Trouver un unique point critique qui est un minimum local ne prouve pas qu’il est global. L’altitude $g$ en est le contre-exemple parfait : un seul minimum local, aucun minimum global. Il faut un argument supplémentaire : existence (coercivité, compacité) ou convexité.

La convexité, ou comment se simplifier la vie

Une fonction $f$ est convexe si, pour tous points $x$, $y$ et tout $\theta \in [0, 1]$ :

$$f\big(\theta x + (1 - \theta) y\big) \leq \theta f(x) + (1 - \theta) f(y)$$

Géométriquement, la corde qui relie deux points du graphe reste au-dessus du graphe : la fonction est une cuvette sans bosse. Si l’inégalité est stricte pour $x \neq y$ et $\theta \in \, ]0, 1[$, $f$ est strictement convexe.

Pour une fonction $C^2$, il existe un critère pratique : $f$ est convexe si et seulement si sa Hessienne est semi-définie positive en tout point. Si la Hessienne est définie positive partout, $f$ est strictement convexe. Pour $f(x) = x^4 - 7x + 8$, $f''(x) = 12x^2 \geq 0$ : elle est convexe. Pour $g$, la Hessienne a une valeur propre $6x$, négative quand $x \lt 0$ : elle ne l’est pas, ce qui explique tous ses ennuis.

Convexe : toute corde reste au-dessus du graphe. Pour x³ − 3x, le graphe passe au-dessus de la corde là où la courbure est négative (x < 0) : la fonction n'est pas convexe.

La convexité change tout :

• tout minimum local est global ;
• tout point critique est un minimum global (plus besoin d’examiner la Hessienne en chaque point) ;
• si $f$ est strictement convexe, le minimum, s’il existe, est unique.

Le cas roi : les fonctions quadratiques

Une fonction quadratique s’écrit

$$f(x) = \tfrac12 \, x^T A x - b^T x + c$$

avec $A$ une matrice symétrique, $b$ un vecteur et $c$ une constante. Son gradient vaut $Ax - b$ et sa Hessienne vaut $A$, constante. Si $A$ est symétrique définie positive, $f$ est strictement convexe et coercive, et son unique minimum est la solution du système linéaire

$$A x^* = b$$

Minimiser une quadratique et résoudre un système linéaire, c’est donc le même problème. C’est pour cela que les méthodes de descente des chapitres suivants servent aussi à résoudre de grands systèmes linéaires.

Exemple

En TP, nous avons travaillé avec $f_1(x, y) = 2x^2 + 3x + y^2 - 2$. En l’écrivant sous la forme ci-dessus, $A = \begin{pmatrix} 4 & 0 \\ 0 & 2 \end{pmatrix}$, $b = (-3, 0)$ et $c = -2$. La matrice $A$ est définie positive (valeurs propres 4 et 2), donc le minimum est unique : $4x = -3$ et $2y = 0$, soit $(-\tfrac34, 0)$, où $f_1$ vaut $-\tfrac{25}{8} = -3{,}125$.

Les lignes de niveau d'une quadratique définie positive sont des ellipses centrées sur le minimum. Elles sont plus serrées selon x, où la courbure (valeur propre 4) est la plus forte.

En entretien

« Un minimum local sans contrainte annule le gradient et a une Hessienne semi-définie positive. La convexité est précieuse parce qu’elle garantit que tout minimum local est global : l’optimisation ne dépend plus du point de départ. »

En résumé

• Le gradient donne la direction de plus forte montée ; la Hessienne décrit la courbure. Taylor à l’ordre 2 les combine.
• Condition nécessaire : un minimum local annule le gradient (point critique) et a une Hessienne semi-définie positive.
• Condition suffisante : gradient nul et Hessienne définie positive donnent un minimum local strict ; en dimension 2, on regarde $rt - s^2$ et $r$.
• Un minimum global existe si $f$ est continue sur un compact (Weierstrass) ou continue et coercive.
• Une fonction convexe (Hessienne semi-définie positive partout) a tous ses minimums locaux globaux ; strictement convexe, elle a au plus un minimiseur.
• Une quadratique $\tfrac12 x^T A x - b^T x$ avec $A$ symétrique définie positive a un unique minimum, solution de $Ax = b$.

Exercices

Exercice · Trouver et classer un point critique

facile

Soit $f(x, y) = x^2 + xy + y^2 - 3x$. Trouvez ses points critiques et leur nature. Le minimum est-il global ?

Voir la solution

Le gradient vaut $(2x + y - 3, \; x + 2y)$. La seconde équation donne $x = -2y$ ; dans la première, $-4y + y = 3$, donc $y = -1$ et $x = 2$. Le seul point critique est $(2, -1)$.

Hessienne : $r = 2$, $s = 1$, $t = 2$, constante. $rt - s^2 = 3 \gt 0$ et $r \gt 0$ : c’est un minimum local, où $f(2, -1) = 4 - 2 + 1 - 6 = -3$.

La Hessienne est définie positive partout (valeurs propres 1 et 3), donc $f$ est strictement convexe : ce minimum est global et unique.

En code

Python

import numpy as np

# Gradient (2x + y - 3, x + 2y) = 0 : un système linéaire
H = np.array([[2, 1], [1, 2]])             # Hessienne, constante
point = np.linalg.solve(H, [3, 0])
x, y = point
print(point, x**2 + x*y + y**2 - 3*x)      # [ 2. -1.] -3.0
print(np.linalg.det(H), np.linalg.eigvalsh(H))   # 3.0 [1. 3.] : définie positive partout

R

# Gradient (2x + y - 3, x + 2y) = 0 : un système linéaire
H <- rbind(c(2, 1), c(1, 2))               # Hessienne, constante
p <- solve(H, c(3, 0))
p; p[1]^2 + p[1] * p[2] + p[2]^2 - 3 * p[1]    # 2 -1 ; -3
det(H); eigen(H)$values                    # 3 ; 3 1 : définie positive partout

Exercice · Quand la Hessienne ne suffit pas

moyen

Montrez que l’origine est un point critique de $f(x, y) = x^4 + y^4$ et de $k(x, y) = x^4 - y^4$, que le critère de Monge ne permet pas de conclure, puis concluez autrement.

Voir la solution

Les gradients $(4x^3, 4y^3)$ et $(4x^3, -4y^3)$ s’annulent à l’origine. Les Hessiennes y sont nulles ($r = 12x^2 = 0$, $t = \pm 12y^2 = 0$, $s = 0$) : $rt - s^2 = 0$, on ne peut pas conclure.

On revient à la définition. $f(x, y) = x^4 + y^4 \geq 0 = f(0, 0)$ pour tout point : l’origine est un minimum global (strict). Pour $k$, sur l’axe des $x$, $k(x, 0) = x^4 \gt 0$, et sur l’axe des $y$, $k(0, y) = -y^4 \lt 0$ : $k$ prend des valeurs plus grandes et plus petites que $k(0, 0) = 0$ arbitrairement près de l’origine, qui est donc un point selle. Deux fonctions à Hessienne nulle, deux natures différentes : la Hessienne seule ne pouvait pas trancher.

En code

Python

import numpy as np

f = lambda x, y: x**4 + y**4
k = lambda x, y: x**4 - y**4
# Hessiennes à l'origine : diag(12x², ±12y²) = matrice nulle, Monge ne conclut pas
# On regarde les valeurs sur un petit cercle de rayon 0,01 autour de l'origine
t = np.linspace(0, 2 * np.pi, 361)
x, y = 0.01 * np.cos(t), 0.01 * np.sin(t)
print(f(x, y).min(), f(x, y).max())    # 5e-09 1e-08 : toujours > 0 = f(0, 0), minimum
print(k(x, y).min(), k(x, y).max())    # -1e-08 1e-08 : des deux signes, point selle

R

f <- function(x, y) x^4 + y^4
k <- function(x, y) x^4 - y^4
# Hessiennes à l'origine : diag(12x², ±12y²) = matrice nulle, Monge ne conclut pas
# On regarde les valeurs sur un petit cercle de rayon 0,01 autour de l'origine
t <- seq(0, 2 * pi, length.out = 361)
x <- 0.01 * cos(t); y <- 0.01 * sin(t)
range(f(x, y))     # 5e-09 1e-08 : toujours > 0 = f(0, 0), minimum
range(k(x, y))     # -1e-08 1e-08 : des deux signes, point selle

Exercice · Un minimum local trompeur

difficile

Soit $f(x, y) = x^3 + y^3 - 3xy$. Trouvez ses points critiques, déterminez leur nature, et dites si $f$ admet un minimum global.

Voir la solution

Le gradient vaut $(3x^2 - 3y, \; 3y^2 - 3x)$. Il s’annule si $y = x^2$ et $x = y^2$, donc $x = x^4$, soit $x = 0$ ou $x = 1$. Les points critiques sont $(0, 0)$ et $(1, 1)$.

La Hessienne vaut $\begin{pmatrix} 6x & -3 \\ -3 & 6y \end{pmatrix}$.

• En $(0, 0)$ : $r = t = 0$, $s = -3$, donc $rt - s^2 = -9 \lt 0$ : point selle.
• En $(1, 1)$ : $r = t = 6$, $s = -3$, donc $rt - s^2 = 27 \gt 0$ et $r \gt 0$ : minimum local, de valeur $1 + 1 - 3 = -1$.

Il n’y a pas de minimum global : sur l’axe des $x$, $f(x, 0) = x^3$ tend vers $-\infty$ quand $x \to -\infty$. Par exemple, $f(-2, 0) = -8 \lt -1$. Comme pour l’altitude $g$ du cours, un unique minimum local n’est pas une garantie.

En code

Python

import numpy as np

f = lambda x, y: x**3 + y**3 - 3*x*y
hess = lambda x, y: np.array([[6*x, -3], [-3, 6*y]])

for p in [(0, 0), (1, 1)]:                 # points critiques : y = x², x = y²
    H = hess(*p)
    print(p, np.linalg.det(H), np.linalg.eigvalsh(H), f(*p))
# (0, 0) -9.0 [-3.  3.] 0   : valeurs propres de signes opposés, point selle
# (1, 1) 27.0 [3. 9.] -1    : définie positive, minimum local
print(f(-2, 0), f(-10, 0))                 # -8 -1000 : pas de minimum global

R

f <- function(x, y) x^3 + y^3 - 3 * x * y
hess <- function(x, y) rbind(c(6 * x, -3), c(-3, 6 * y))

for (p in list(c(0, 0), c(1, 1))) {        # points critiques : y = x², x = y²
  H <- hess(p[1], p[2])
  cat(p, ": det", det(H), ", valeurs propres", eigen(H)$values, ", f =", f(p[1], p[2]), "\n")
}
# 0 0 : det -9 , valeurs propres 3 -3 , f = 0   : point selle
# 1 1 : det 27 , valeurs propres 9 3 , f = -1   : minimum local
f(-2, 0); f(-10, 0)                        # -8 et -1000 : pas de minimum global