import numpy as np
import matplotlib.pyplot as plt
def log_1(t):
if t <= 0:
return -float("inf")
return np.log(t)
log = np.vectorize(log_1)
# comme en TP, on fournit des fonctions permettant de vérifier le gradient et/ou la hessienne
def verifier_gradient(f,gradf,x0):
N = len(x0)
gg = np.zeros(N)
for i in range(N):
eps = 1e-5
e = np.zeros(N)
e[i] = eps
gg[i] = (f(x0+e) - f(x0-e))/(2*eps)
print('erreur numérique dans le calcul du gradient: %g (doit être petit)' % np.linalg.norm(gradf(x0)-gg))
def verifier_hessienne(gradf,hessf,x0):
N = len(x0)
H = np.zeros((N,N))
for i in range(N):
eps = 1e-5
e = np.zeros(N)
e[i] = eps
H[i,:] = (gradf(x0+e) - gradf(x0-e))/(2*eps)
print('erreur numerique dans le calcul de la hessienne: %g (doit etre petit)' % np.sum((H-hessf(x0)))**2)
# on donne également la fonction pas_armijo/gradient_armijo
def pas_armijo(f,gradf,x,v):
t = 1
m = np.dot(v,gradf(x))
alpha=0.3
beta=0.5
while f(x+t*v) > f(x) + alpha*t*m:
t = beta*t
return t
def gradient_armijo(f,gradf,x0,err=1e-4):
x = x0
G = []
k = 0
maxiter = 200
while(True):
k = k+1
if k > maxiter:
print('erreur: nombre maximum d\'itérations atteint')
break
# calcul de d, t,
d = -gradf(x)
G.append(np.linalg.norm(d))
if np.linalg.norm(d) <= err:
break
t = pas_armijo(f,gradf,x,d)
x = x + t*d
return x,np.array(G)
QN1. Écrire deux fonctions f(x)
, gradf(x)
calculant respectivement $f(x),\nabla f(x)$. (On pourra utiliser la fonction verifier_gradient()
pour vérifier le calcul)
log
définie dans le préambule ci-dessus plutôt que np.log
help
pour obtenir de l'aide sur une fonction i.e. help(np.dot)
# paramètres
z = np.array([8., 1.])
eps = 1e-3
# compléter
# verifier_gradient(f,gradf,np.random.rand(2)/3)
QN2. La fonction x,G = gradient_armijo(f,gradf,x0)
donnée en préambule implémente la descente de gradient avec rebroussement d'Armijo. Elle retourne la solution calculée x
et un tableau G
contenant $(\|\nabla f (x^{(k)})\|)$. En utilisant cette fonction, tracer sur un même figure et en échelle logarithmique $k\mapsto \|\nabla f (x^{(k)})\|$ en partant de $x^{(0)} = (\frac{1}{4},\frac{1}{4})$, pour plusieurs choix du paramètre $\eps \in \{.1,.01,.001,.0001\}$.
QN3 Écrire une fonction hessf(x)
calculant $\mathrm{D}^2 f(x)$. (On pourra utiliser verifier_hessienne()
pour vérifier le calcul)
# compléter
# verifier_hessienne(gradf,hessf,np.random.rand(2)/3)
QN4. Implémenter la méthode de Newton avec rebroussement d'Armijo (appelée (Newton) dans le sujet). La fonction Python x,G = newton_armijo(f,gradf,x0)
retournera la solution calculée x
et un tableau G
contenant $(\|\nabla f (x^{(k)})\|)$. En utilisant cette fonction, tracer en échelle logarithmique $k\mapsto \|\nabla f (x^{(k)})\|$ en partant de $x^{(0)} = (\frac{1}{4},\frac{1}{4})$ et pour plusieurs choix du paramètre $\eps \in \{.1,.01,.001,.0001\}$.
(On pourra utiliser la fonction np.linalg.solve
pour résoudre un système linéaire ou np.linalg.inv
pour inverser une matrice)
Ce fichier doit être enregistré dans le répertoire reMise_copie
situé sur le bureau, et nommé M315-nom-prenom.ipynb