Partie 1.2 -- Étude numérique de deux méthodes de descente de gradient

$$\newcommand{\eps}{\varepsilon}$$ Dans la suite, on fixe une fois pour toute $a=(0,1)$, $b = (0,-1)$, $c = (0.1,0)$, $\eps = 10^{-3}$.

QN1. Écrire quatre fonctions n(x), gradn(x), f(x), gradf(x) calculant respectivement $n_\eps(x),\nabla n_\eps(x),f_\eps(x),\nabla f_\eps(x)$.

In [58]:
# on importe les modules numpy et pyplot
import numpy as np
import matplotlib.pyplot as plt
# les deux commandes suivante paramètrent l'affichage des figures
%matplotlib inline
plt.rcParams['figure.figsize'] = [9.,6.]

a = [0.,1.]
b = [0.,-1.]
c = [.1,0.]
eps = 1e-3

# ecrire les fonction n, gradn, f, gradf

QN2. Écrire une fonction gradient_fixe(f,gradf,x0,tau) implémentant l'algorithme de descente de gradient à pas fixe:

$$\begin{cases} x^{(0)} \in \mathbb{R}^2 \hbox{ donné }\\ x^{(k+1)} = x^{(k)} - \tau \nabla f(x^{(k)}) \end{cases}$$

  • on s'arrêtera quand $k=100$ ou dès que $\|{\nabla f(x^{(k)})}\| \leq 10^{-6}$
  • la fonction retournera un tableau $G = [\|\nabla f(x^{(0)})\|,\dots, \|\nabla f(x^{(k)})\|]$
In [59]:
def gradient_fixe(f, gradf, x0, tau):
    # compléter

QN3 Tester la fonction gradient_fixe en partant du point $x^{(0)} = (1,1)$ pour $\tau \in \{0.03, 0.1, 0.5\}$. Tracer l'évolution de la norme du gradient au cours des itérations dans chaque choix de tau.

QN4 Écrire une fonction gradient_backtracking(f,gradf,x0,tau) implémentant l'algorithme de descente de gradient avec backtracking d'Armijo:

$$\begin{cases} x^{(0)} \in \mathbb{R}^2 \hbox{ donné }\\ g^{(k)} = \nabla f(x^{(k)}) \\ d^{(k)} = - g^{(k)} \\ \tau^{(k)} = backtrack(f,x^{(k)},d^{(k)}, g^{(k)}) \\ x^{(k+1)} = x^{(k)} + \tau^{(k)} d^{(k)} \end{cases}$$

La fonction backtrack est donnée. La fonction gradient_backtracking aura le même comportement que gradient_fixe:

  • on fera au plus $100$ itérations, et on s'arrêtera dès que $\|{\nabla f(x^{(k)})}\| \leq 10^{-6}$
  • la fonction retournera un tableau $G = [\|\nabla f(x^{(0)})\|,\dots, \|\nabla f(x^{(k)})\|]$
In [3]:
def backtrack(f,x,d,g):
    t = 1
    m = np.dot(d,g)
    while f(x+t*d) > f(x) + 0.3*t*m:
        t = 0.5*t
    return t

def gradient_backtracking(f,gradf,x0,err=1e-6):
    # à compléter

QN5 Tester la fonction gradient_backtracking en partant des points $x^{(0)} \in \{ (0,0), (1,1), (10,10) \}$. Tracer l'évolution de la norme du gradient au cours des itérations dans ces trois cas. Commenter.