| Hosted by CoCalc | Download
%auto
typeset_mode(True, display=False)

Descente de gradient

Dans les pages 215 à 217 du livre de Stewart on présente une méthode d minimisation, connue sous le nom de "descente de gradient". En gros, on part d'un point puis on fait des pas dans la direction oposée au gradient. La longueur du pas est celle qui permet de minimiser la valeur de la fonction objectif. Ci après, une implémentation très naïve de la chose, en SAGEMath.

L'exemple utilisé est celui de la page217 - 218.

var('x,y')
f(x,y) = x^4+y^2 -2*x^2 *y+2*y+x
(xx, yy)
Df = f.gradient()
Df(x,y)
(4 x3−4 xy+1, −2 x2+2 y+2)\left(4 \, x^{3} - 4 \, x y + 1,\,-2 \, x^{2} + 2 \, y + 2\right)



var('t')
def myDescente(f, prec, x0,y0):# prec = précision, x0, y0 sont les coordonnées du point de départ.
    Df = f.gradient()
    print "Point d'évalution :", (x0,y0)
    print "Valeur de la fonction objectif:", f(x0,y0).n(digits=6)
    if norm(Df(x0,y0)) < prec :
        print "Norme du gradient = ", norm(Df(x0,y0)), ". Valeur minimale trouvée :", f(x0,y0).n(digits=6)
    else:
        F(t) = f(x0-t*Df(x0,y0)[0],y0-t*Df(x0,y0)[1])
        t0 = F.find_local_minimum(0,1)[1]
        print "Norme du gradient = ", norm(Df(x0,y0)).n(digits=6), ". On va ailleurs. Longueur du pas (en fraction du gradient) : ", t0
        myDescente(f,prec,x0-t0*Df(x0,y0)[0], y0-t0*Df(x0,y0)[1])
tt
myDescente(f,0.01, 0,0)
Point d'évalution : (0, 0) Valeur de la fonction objectif: 0.000000 Norme du gradient = 2.23607 . On va ailleurs. Longueur du pas (en fraction du gradient) : 0.380408916489 Point d'évalution : (-0.3804089164888948, -0.7608178329777896) Valeur de la fonction objectif: -1.08206 Norme du gradient = 0.422488 . On va ailleurs. Longueur du pas (en fraction du gradient) : 0.345102236507 Point d'évalution : (-0.24999999815128793, -0.8260222938552688) Valeur de la fonction objectif: -1.11257 Norme du gradient = 0.249272 . On va ailleurs. Longueur du pas (en fraction du gradient) : 0.301870449467 Point d'évalution : (-0.28365182567320124, -0.8933259449322235) Valeur de la fonction objectif: -1.12205 Norme du gradient = 0.117240 . On va ailleurs. Longueur du pas (en fraction du gradient) : 0.320912992693 Point d'évalution : (-0.24999999661095967, -0.9101518604020017) Valeur de la fonction objectif: -1.12425 Norme du gradient = 0.0611523 . On va ailleurs. Longueur du pas (en fraction du gradient) : 0.302753672583 Point d'évalution : (-0.25827975081753274, -0.9267113608312758) Valeur de la fonction objectif: -1.12482 Norme du gradient = 0.0294276 . On va ailleurs. Longueur du pas (en fraction du gradient) : 0.314569676889 Point d'évalution : (-0.2500000051951869, -0.9308512295752441) Valeur de la fonction objectif: -1.12496 Norme du gradient = 0.0148671 . On va ailleurs. Longueur du pas (en fraction du gradient) : 0.302964223216 Point d'évalution : (-0.25201433772132315, -0.9348799071354438) Valeur de la fonction objectif: -1.12499 Norme du gradient = 0.007195119079376397 . Valeur minimale trouvée : -1.12499

Défi :

Ce serait bien de faire un graphique dans lequel on montre les courbes de niveau de la fonction objectif, puis des segments de droite rerpésentant les pas.