Descente de gradient à une variable

La descente de gradient cherche un minimum par itérations. Pour maximiser $f$, on minimise plutôt $-f$. Cette approche est fondamentale dans les problèmes d'optimisation où les solutions exactes sont difficiles à dériver analytiquement, en particulier en raison des complexités dans les dimensions supérieures.

Concept de la descente de gradient

• Démontrée d'abord dans un cadre à une seule variable pour faciliter la transition vers la descente de gradient multivariable plus complexe.
• Emploie un processus itératif pour approcher le minimum d'une fonction en mettant systématiquement à jour le point d'intérêt en fonction de la dérivée de la fonction.

Formulation mathématique

Étant donnée une fonction $f(x) = e^x - \log(x)$, la recherche de son minimum implique :

1. Calcul de la dérivée : la première étape consiste à calculer la dérivée $f'(x) = e^x - \frac{1}{x}$.
2. Mise à jour itérative : en partant d'un point initial $x_0$, le point suivant $x_{1}$ est déterminé par $x_{1} = x_{0} - \alpha \cdot f'(x_{0})$, où $\alpha$ est le taux d'apprentissage.

Cette méthode s'appuie sur la dérivée pour guider la direction des pas effectués vers le minimum. Le signe de la dérivée indique s'il faut se déplacer vers la gauche ou vers la droite (dans le cas d'une seule variable).

Défis et solutions

Difficulté analytique

• Résoudre directement $e^x = \frac{1}{x}$ pour $x$ est analytiquement difficile, ce qui illustre les situations où la descente de gradient offre une solution pratique.

Taux d'apprentissage ($\alpha$)

• Le taux d'apprentissage $\alpha$ est crucial pour garantir que les pas itératifs sont dimensionnés de manière appropriée afin d'éviter les dépassements ou une convergence excessivement lente.
• Taux d'apprentissage adaptatifs : les recherches sur les taux d'apprentissage adaptatifs visent à ajuster dynamiquement $\alpha$ en fonction de la progression de l'optimisation, bien qu'une stratégie universellement optimale reste à établir.

Minima locaux

• La descente de gradient peut converger vers des minima locaux, risquant ainsi de manquer le minimum global.
• Points initiaux multiples : employer plusieurs points de départ et exécuter des itérations de descente de gradient depuis chacun d'eux peut augmenter la probabilité d'approcher le minimum global.

Mise en œuvre pratique

1. Initialisation : choisir un point de départ et un taux d'apprentissage.
2. Règle de mise à jour : appliquer itérativement la mise à jour $x_{k} = x_{k-1} - \alpha \cdot f'(x_{k-1})$.
3. Critère de convergence : vérifier la norme de la dérivée, la diminution de l’objectif, le domaine et une limite d’itérations. Une faible variation de $x$ ne prouve pas l’optimalité.

Exemple

• Pour $f(x) = e^x - \log(x)$, en partant d'une estimation initiale, les itérations progressent en calculant la dérivée au point courant et en mettant à jour le point en fonction du taux d'apprentissage et du gradient calculé.
• Ce processus ne nécessite pas de déterminer quand la dérivée s'annule, mais s'ajuste plutôt de manière itérative selon la direction et l'amplitude du gradient.

Un calcul qui respecte le domaine

Ici $\log$ désigne le logarithme naturel et le domaine est $x>0$. La courbure $f''(x)=e^x+1/x^2>0$ rend $f$ strictement convexe. De plus, $f$ tend vers l’infini lorsque $x\to0^+$ ou $x\to\infty$ : elle possède donc un unique minimum global. Résoudre $xe^x=1$ donne $x_*\approx0.567143$, aussi noté $W(1)$. Le risque de minima locaux concurrents ne concerne pas cet exemple.

Depuis $x_0=1$, avec $\alpha=0.1$, on obtient $g_0=e-1$ puis $x_1\approx0.828172$ ; $f$ passe de $2.718282$ à $2.477665$. En revanche, depuis $x_0=2$ avec $\alpha=1$, le point suivant est négatif et son logarithme n’est pas défini. Il faut rejeter un pas inadmissible avant d’évaluer l’objectif. Cette recherche par rebroussement divise le pas par deux jusqu’à satisfaire la condition de diminution d’Armijo ; les limites d’itérations et d’essais signalent un échec plutôt qu’une convergence fictive.

from math import exp, log, isfinite

def f(x):
    return exp(x) - log(x)

x = 1.0
for iteration in range(10000):
    g = exp(x) - 1 / x
    if abs(g) <= 1e-7:
        break
    alpha = 1.0
    for trial in range(60):
        candidate = x - alpha * g
        if candidate > 0 and isfinite(candidate):
            try:
                value = f(candidate)
            except OverflowError:
                value = float("inf")
            if isfinite(value) and value <= f(x) - 1e-4 * alpha * g * g:
                break
        alpha *= 0.5
    else:
        raise RuntimeError("line search failed")
    x = candidate
else:
    raise RuntimeError("iteration limit reached")
print(round(x, 6), round(f(x), 6))

La sortie est 0.567143 2.330366. La tolérance sur la dérivée indique ici une stationnarité approchée ; la stricte convexité identifie l’unique point stationnaire au minimum global. Pour un objectif non convexe, une petite dérivée pourrait signaler un point-selle ou un maximum.

Comme repère pour le pas, $f(x)=x^2$ donne $x_{k+1}=(1-2\alpha)x_k$. Depuis un point initial non nul, la convergence exige $0<\alpha<1$ ; à $\alpha=1$, les itérés oscillent, et au-delà ils divergent. Inversement, un $\alpha$ infime peut rendre la variation des itérés minuscule alors que $|f'(x)|$ reste grand. Si $|f'(u)-f'(v)|\le L|u-v|$ sur un intervalle contenant le pas (gradient $L$-Lipschitz), $f(x-\alpha g)\le f(x)-\alpha(1-L\alpha/2)g^2$ ; ainsi $0<\alpha<2/L$ assure la descente pour $g\ne0$. L’exemple logarithmique n’a pas de constante globale $L$ finie sur $(0,\infty)$ ; la recherche par rebroussement évite cette hypothèse.

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