Partie 6 · Optimisation

Points critiques, Hessien et descente de gradient

Points critiques

Un point critique est un point où $\nabla f(x,y)=0$ . Ce sont les candidats à un minimum local, un maximum local ou un point-selle. Pour $f(x,y)=x^2+y^2$ : $\nabla f=(2x,2y)=0$ donne $(0,0)$ .

Dérivées secondes et Hessien

On définit $f_{xx}, f_{yy}, f_{xy}, f_{yx}$ et la matrice Hessienne :

H_f=\begin{pmatrix} f_{xx} & f_{xy} \\ f_{yx} & f_{yy} \end{pmatrix}.

Elle sert à analyser la convexité/concavité et la nature des points critiques. Elle est symétrique si les dérivées secondes sont continues ; une matrice symétrique a des valeurs propres réelles, une base de vecteurs propres et une diagonalisation orthogonale.

Vérifie que tu as compris

Quelle condition caractérise un point critique ?

Lire le Hessien avec ses valeurs propres

Soit $H$ le Hessien évalué en un point critique. Le signe de ses valeurs propres indique directement la courbure :

valeurs propres de $H$	conclusion
toutes $> 0$	Hessienne définie positive : strictement convexe, minimum local (unique)
toutes $< 0$	définie négative : strictement concave, maximum local (unique)
au moins une $>0$ et une $<0$	point-selle (ni minimum ni maximum)
une valeur propre $=0$	cas indécidable : le test ne conclut pas

Dans le cours, ces tests s'écrivent avec NumPy : np.all(eigvals > 0), np.all(eigvals < 0), np.any(eigvals < 0) and np.any(eigvals > 0), np.any(np.isclose(eigvals, 0)).

Exemple 1 : $f=x^2+y^2$ , $H=\begin{pmatrix}2&0\\0&2\end{pmatrix}$ , valeurs propres $2,2$ : minimum global. Exemple 2 : $f=x^2-y^2$ , $H=\begin{pmatrix}2&0\\0&-2\end{pmatrix}$ , valeurs propres $2$ et $-2$ : point-selle en $(0,0)$ .

Vérifie que tu as compris

Pour

f(x,y)=x^2+y^2-4x

, quel est le point critique ?

Cas indécidable et descente de gradient

Si une valeur propre est nulle, le test du Hessien ne permet pas de conclure : le point peut être un minimum non strict, un maximum non strict ou un point-selle. Il faut alors étudier la fonction autrement.

Exemple du cours : $f(x,y)=x^2-y^4$ en $(0,0)$ . Le gradient $(2x,\,-4y^3)$ s'annule en $(0,0)$ , et le gradient est quasi nul tout près de $y=0$ puisque $y^3$ est minuscule. Pour la descente de gradient (on avance de $-\eta\,\nabla f$ à chaque étape, avec un pas $\eta$ ), c'est un problème : la pente disparaît, l'algorithme ralentit puis s'arrête sans avoir trouvé de minimum. (Ici le point est en réalité un selle : $f$ monte en $x$ et descend en $y$ , mais le Hessien $\mathrm{diag}(2,0)$ ne le voit pas. Précision hors cours.)

Autre exercice du cours : $f(x,y)=x^3-3xy^2$ (fonction « classique en optimisation ») a un gradient $(3x^2-3y^2,\,-6xy)$ qui s'annule en $(0,0)$ , avec un Hessien nul en ce point : cas indécidable.

En dimension supérieure, on raisonne de même sur les valeurs propres du Hessien : le cours donne une fonction analyse_hessienne(H) qui conclut convexe/min local, concave/max local, selle ou test inconcluant.

Vérifie que tu as compris

Pourquoi le gradient de

f(x,y)=x^2-y^4

« chute-t-il vers

0

» en

(0,0)

À toi de coder

Descente de gradient en 1D

On minimise $f(x)=(x-3)^2$ , de dérivée $f'(x)=2(x-3)$ . À chaque étape : $x \leftarrow x - \eta\, f'(x)$ . Écris descente_1d(df, x0, eta, n) qui applique cette mise à jour n fois et renvoie le $x$ final. Avec $x_0=0$ , $\eta=0{,}1$ , $n=100$ on doit approcher $3$ .

def descente_1d(df, x0, eta, n):
    x = x0
    for _ in range(n):
        x = x - ___ * df(x)
    return x

Ctrl/⌘+Entrée

À toi de coder

Descente de gradient en 2D

On minimise $f(x,y)=x^2+3y^2$ , de gradient $(2x,;6y)$ . Écris descente_2d(x, y, eta, n) : à chaque étape, $x \leftarrow x-\eta\, 2x$ et $y \leftarrow y-\eta\, 6y$ (mets à jour les deux avec les anciennes valeurs). Renvoie la liste [x, y]. De $(4, 2)$ avec $\eta=0{,}1$ et $n=200$ , on tend vers $(0,0)$ .

def descente_2d(x, y, eta, n):
    for _ in range(n):
        gx = 2 * x
        gy = ___ * y
        x = x - eta * gx
        y = y - eta * ___
    return [x, y]

Ctrl/⌘+Entrée

À toi de coder

Classer un point critique (Hessien 2x2)

Pour un Hessien symétrique $\begin{pmatrix}a&b\\b&c\end{pmatrix}$ , les valeurs propres valent $\lambda=\frac{a+c}{2}\pm\sqrt{\left(\frac{a-c}{2}\right)^2+b^2}$ (formule hors cours). Écris classer(a, b, c) qui renvoie "minimum" (deux valeurs propres $>0$ ), "maximum" (deux $<0$ ), "selle" (signes mélangés) ou "indecidable" (une valeur propre nulle, tolérance $10^{-9}$ ).

import math

def classer(a, b, c):
    r = math.sqrt(((a - c) / 2) ** 2 + b ** 2)
    l1 = (a + c) / 2 + r
    l2 = (a + c) / 2 - r
    if abs(l1) < 1e-9 or abs(l2) < 1e-9:
        return "indecidable"
    if l1 > 0 and l2 > 0:
        return "___"
    if l1 < 0 and l2 < 0:
        return "maximum"
    return "___"

Ctrl/⌘+Entrée