Projets d'Optimisation

Voici les détails de mes projets en optimisation.

Exercice : Conditions d’optimalité et descente de gradient

Énoncé

Soit l’espace euclidien \(E=\mathbb{R}^n\) muni du produit scalaire canonique. On fixe \(y \in E\), \(y \neq 0\), et on considère : \[ f(x) = \langle x, y \rangle e^{-\|x\|^2}. \] Question : Calculer le gradient de \(f\), puis mettre en place une méthode de descente de gradient.

1. Calcul du gradient

En posant \(\beta(x)=\langle x,y\rangle\), \(s(x)=e^{-\|x\|^2}\), on a : \[ \nabla f(x) = e^{-\|x\|^2}\big(y - 2\langle x,y\rangle x\big). \]

2. Méthode de descente de gradient

On construit la suite \((x_k)\) par : \[ x_{k+1} = x_k - \eta \nabla f(x_k), \] avec \(\eta>0\). Critères d’arrêt : norme du pas, norme du gradient ou nombre d’itérations.

3. Code général en Python


import numpy as np

def gradient_descent(grad, x0, lr=0.1, max_iter=1000, tol=1e-6):
    x = np.array(x0, dtype=float)
    history = [x.copy()]
    for k in range(max_iter):
        g = grad(x)
        x_new = x - lr * g
        history.append(x_new.copy())
        if np.linalg.norm(x_new - x) < tol:
            break
        x = x_new
    return np.array(history)

4. Application à \(f(x)=\langle x,y\rangle e^{-\|x\|^2}\)


import matplotlib.pyplot as plt

def f_xy(x, y):
    return np.dot(x, y) * np.exp(-np.linalg.norm(x)**2)

def grad_f_xy(x, y):
    return np.exp(-np.linalg.norm(x)**2) * (y - 2*np.dot(x,y)*x)

# paramètres
y = np.array([1.0, -2.0])
x0 = np.array([0.8, 0.8])
history = gradient_descent(lambda x: grad_f_xy(x,y), x0, lr=0.2)

# tracé
plt.plot(history[:,0], history[:,1], 'o-', color='red')
plt.title("Trajectoire de la descente de gradient")
plt.show()

CComparaison : Descente de Gradient

Optimisation en 1D : Descente de Gradient

Description

Nous analysons la fonction \( J(x) = \langle x, y \rangle \exp(-\|x\|^2) \) en 1D le long de la direction de \( y = (1, 2) \). La fonction en 1D est \( J_{1d}(t) = t \cdot \|y\| \cdot \exp(-t^2) \). Les minima locaux théoriques sont \( t_{\text{opt}} = \pm \frac{\|y\|}{\sqrt{2}} \).

Explications

- **Fonction en 1D** : La courbe montre \( J_{1d}(t) \) avec ses deux minima locaux. - **Descente de Gradient** : La trajectoire montre comment \( t \) converge vers un minimum local à partir d'un point initial perturbé. - **Points Optimaux** : Les points rouges et bleus indiquent les minima théoriques.

Code Python

Voici le code Python utilisé pour générer les résultats :


import numpy as np
import matplotlib.pyplot as plt

# Paramètres
y = np.array([1.0, 2.0])
norm_y = np.linalg.norm(y)

# Définition de la fonction J_1d(t) = t * ||y|| * exp(-t^2)
def J_1d(t):
    return t * norm_y * np.exp(-t**2)

# Dérivée analytique de J_1d(t)
def dJ_1d(t):
    return norm_y * np.exp(-t**2) * (1 - 2 * t**2)

# Descente de gradient en 1D
def gradient_descent(t0, learning_rate=0.01, epsilon=1e-6, max_iter=1000):
    t = t0
    trajectory = [t]
    for niter in range(max_iter):
        grad = dJ_1d(t)
        if abs(grad) < epsilon:
            print(f"Convergence atteinte après {niter} itérations.")
            break
        t -= learning_rate * grad
        trajectory.append(t)
    return np.array(trajectory)

# Solutions théoriques : t_opt = +/- ||y|| / sqrt(2)
topt1 = norm_y / np.sqrt(2)
topt2 = -norm_y / np.sqrt(2)

print("Solutions théoriques :")
print("topt1 =", topt1)
print("topt2 =", topt2)

# Descente de gradient à partir d'un point initial perturbé
perturbation = 0.5
tinit = topt1 + perturbation

trajectory = gradient_descent(tinit, learning_rate=0.01, epsilon=1e-6)

# Tracer la fonction J_1d(t)
t_vals = np.linspace(-3, 3, 400)
J_vals = J_1d(t_vals)

plt.figure(figsize=(12, 5))

plt.subplot(1, 2, 1)
plt.plot(t_vals, J_vals, label='J_1d(t)')
plt.scatter(topt1, J_1d(topt1), c='red', label='topt1')
plt.scatter(topt2, J_1d(topt2), c='blue', label='topt2')
plt.xlabel('t')
plt.ylabel('J_1d(t)')
plt.title('Fonction J_1d(t)')
plt.legend()
plt.grid(True)

plt.subplot(1, 2, 2)
plt.plot(t_vals, J_vals, label='J_1d(t)')
plt.plot(trajectory, J_1d(trajectory), 'ro-', label='Trajectoire')
plt.scatter(tinit, J_1d(tinit), c='green', label='Point initial')
plt.scatter(trajectory[-1], J_1d(trajectory[-1]), c='red', label='Minimum trouvé')
plt.scatter(topt1, J_1d(topt1), c='blue', label='topt1')
plt.scatter(topt2, J_1d(topt2), c='cyan', label='topt2')
plt.xlabel('t')
plt.ylabel('J_1d(t)')
plt.title('Trajectoire de la descente de gradient en 1D')
plt.legend()
plt.grid(True)

plt.tight_layout()
plt.show()