︠c8e6f40f-4d53-478c-ba96-c59dc9ecf297as︠ %auto typeset_mode(True, display=False) ︡f6aacb4c-c21e-4887-8bad-55cf5344857f︡{"done":true}︡ ︠7298fef0-2a10-429b-880b-a3f73ddb5ffei︠ %md ## 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. ︡3e19b314-4bc2-4790-b654-a2c6384cdfeb︡{"done":true,"md":"## Descente de gradient\n\n### 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.\n\n#### L'exemple utilisé est celui de la page217 - 218."} ︠20f64c19-ff78-4a1c-a245-933b030e5907s︠ var('x,y') f(x,y) = x^4+y^2 -2*x^2 *y+2*y+x ︡a7382614-0d9b-4987-beee-dfa1dcd0a6a7︡{"html":"
($x$, $y$)
"}︡{"done":true}︡ ︠03542a0b-2ea0-4631-8cee-0313eae81aa9s︠ Df = f.gradient() Df(x,y) ︡4ceb8a72-6f70-49b2-a97d-1dcb1e607755︡{"html":"
$\\left(4 \\, x^{3} - 4 \\, x y + 1,\\,-2 \\, x^{2} + 2 \\, y + 2\\right)$
"}︡{"done":true}︡ ︠e1dc8cc5-6220-4200-8ad7-f70a201a05a0s︠ ︡e5345777-a3c9-4101-85b7-e5c8c134acd8︡{"done":true}︡ ︠7f2762ae-8012-484c-9eb7-f13334a2754c︠ 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]) ︡1aeea772-bd76-4625-a9fb-e458e142117f︡{"html":"
$t$
"}︡{"done":true}︡ ︠e9b7f446-6a3c-406a-adc2-c931590ec020s︠ myDescente(f,0.01, 0,0) ︡fb37b637-b445-496d-8ba3-a5155354593c︡{"stdout":"Point d'évalution : (0, 0)\nValeur de la fonction objectif: 0.000000\nNorme du gradient = "}︡{"stdout":" 2.23607 . On va ailleurs. Longueur du pas (en fraction du gradient) : 0.380408916489\nPoint d'évalution : (-0.3804089164888948, -0.7608178329777896)\nValeur de la fonction objectif: -1.08206\nNorme du gradient = 0.422488 . On va ailleurs. Longueur du pas (en fraction du gradient) : 0.345102236507\nPoint d'évalution : (-0.24999999815128793, -0.8260222938552688)\nValeur de la fonction objectif: -1.11257\nNorme du gradient = 0.249272 . On va ailleurs. Longueur du pas (en fraction du gradient) : 0.301870449467\nPoint d'évalution : (-0.28365182567320124, -0.8933259449322235)\nValeur de la fonction objectif: -1.12205\nNorme du gradient = 0.117240 . On va ailleurs. Longueur du pas (en fraction du gradient) : 0.320912992693\nPoint d'évalution : (-0.24999999661095967, -0.9101518604020017)\nValeur de la fonction objectif: -1.12425\nNorme du gradient = 0.0611523 . On va ailleurs. Longueur du pas (en fraction du gradient) : 0.302753672583\nPoint d'évalution : (-0.25827975081753274, -0.9267113608312758)\nValeur de la fonction objectif: -1.12482\nNorme du gradient = 0.0294276 . On va ailleurs. Longueur du pas (en fraction du gradient) : 0.314569676889\nPoint d'évalution : (-0.2500000051951869, -0.9308512295752441)\nValeur de la fonction objectif: -1.12496\nNorme du gradient = 0.0148671 . On va ailleurs. Longueur du pas (en fraction du gradient) : 0.302964223216\nPoint d'évalution : (-0.25201433772132315, -0.9348799071354438)\nValeur de la fonction objectif: -1.12499\nNorme du gradient = 0.007195119079376397 . Valeur minimale trouvée : -1.12499\n"}︡{"done":true}︡ ︠35e73b63-a4ad-42c1-ae3c-5ee1a2c8f597i︠ %md ### 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. ︡8fbd663f-06cc-491d-ad28-099546465940︡{"done":true,"md":"### Défi :\n#### 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."} ︠9d42bdf5-cf46-4020-b5c6-86eb54cfa06a︠