TP Optimisation
Ce programme MATLAB implémente la méthode de la section dorée pour
minimiser la fonction f (x) = (x − 2)2 + 3 dans un intervalle donné.
1 % D f i n i t i o n de la fonction minimiser
2 f = @ ( x ) ( x - 2) ^2 + 3;
3
4 % Intervalle initial
5 a = 0;
6 b = 4;
7
8 % T o l r a n c e pour la p r c i s i o n de la recherche
9 tol = 1e -5;
10
11 % Rapport d ’ or
12 phi = (1 + sqrt (5) ) / 2;
13
14 % Initia lisation des points x1 et x2
15 x1 = b - ( b - a ) / phi ;
16 x2 = a + ( b - a ) / phi ;
17
18 % Boucle de recherche
19 while ( b - a ) > tol
20 % valuation de la fonction aux points x1 et x2
21 f1 = f ( x1 ) ;
22 f2 = f ( x2 ) ;
23
24 % Mise jour des limites de l ’ intervalle
25 if f1 < f2
26 b = x2 ;
27 x2 = x1 ;
28 x1 = b - ( b - a ) / phi ;
29 else
30 a = x1 ;
31 x1 = x2 ;
32 x2 = a + ( b - a ) / phi ;
33 end
34 end
35
36 % R s u l t a t final
37 xmin = ( a + b ) / 2;
38 fmin = f ( xmin ) ;
39
40 % Affichage des r s u l t a t s
41 fprintf ( ’ Le ␣ minimum ␣ de ␣ f ( x ) ␣ est ␣ a p p r o x i m a t i v e m e n t ␣ atteint ␣ en ␣ x ␣ = ␣
%.5 f \ n ’ , xmin ) ;
42 fprintf ( ’ La ␣ valeur ␣ de ␣ f ( x ) ␣ au ␣ minimum ␣ est ␣ f ( x ) ␣ = ␣ %.5 f \ n ’ , fmin ) ;
1
Listing 1: Programme MATLAB pour la recherche unidimensionnelle
Problème
Nous souhaitons minimiser la fonction suivante :
f (x) = x2 − 4x + 4
Objectif
Trouver la valeur de x qui minimise f (x) en utilisant la méthode de Newton.
Méthode de Newton
La méthode de Newton est une méthode itérative pour trouver les points où la
dérivée d’une fonction est nulle, en suivant ces étapes :
1. Dériver la fonction : Calculer la première dérivée f ′ (x) et la seconde
dérivée f ′′ (x).
2. Formule d’itération : La mise à jour de x à chaque itération est donnée
par :
f ′ (x)
xnew = x − ′′
f (x)
3. Initialisation et convergence : Choisir une valeur initiale x0 et itérer
jusqu’à ce que la différence entre xnew et x soit suffisamment petite.
Application
• Fonction et dérivées :
f (x) = x2 − 4x + 4, f ′ (x) = 2x − 4, f ′′ (x) = 2
• Itération : La formule d’itération devient
2x − 4
xnew = x − =2
2
En une seule itération, nous trouvons x = 2, le point minimum de f (x).
• Vérification :
f (2) = 22 − 4 · 2 + 4 = 0
2
Conclusion
Le minimum de la fonction f (x) = x2 −4x+4 est atteint en x = 2, avec f (2) = 0.
Code MATLAB
Voici un programme MATLAB qui applique la méthode de Newton pour min-
imiser la fonction f (x).
1 % D f i n i t i o n de la fonction et de ses d r i v e s
2 f = @ ( x ) x ^2 - 4* x + 4;
3 f_prime = @ ( x ) 2* x - 4;
4 f_dou ble_pri me = @ ( x ) 2;
5
6 % Initia lisation de x0
7 x = 0; % Point de d p a r t initial
8 tol = 1e -5; % T o l r a n c e pour la convergence
9
10 % M t h o d e de Newton
11 while abs ( f_prime ( x ) ) > tol
12 x = x - f_prime ( x ) / f_ double_ prime ( x ) ;
13 end
14
15 % Affichage des r s u l t a t s
16 fprintf ( ’ Le ␣ minimum ␣ de ␣ f ( x ) ␣ est ␣ atteint ␣ en ␣ x ␣ = ␣ %.5 f \ n ’ , x ) ;
17 fprintf ( ’ La ␣ valeur ␣ de ␣ f ( x ) ␣ au ␣ minimum ␣ est ␣ f ( x ) ␣ = ␣ %.5 f \ n ’ , f ( x ) ) ;
Listing 2: Programme MATLAB pour la méthode de Newton
Méthode de Quasi-Newton
Cette partie présente une implémentation de la méthode de quasi-Newton pour
une fonction d’une seule variable, en utilisant les différences finies pour estimer
la dérivée et la seconde dérivée.
Définition de la Fonction
Soit la fonction
f (x) = (x − 3)2 + 2
Paramètres d’Initialisation
• Point initial : x = 0
• Tolérance pour l’arrêt : tol = 1 × 10−5
• Petite variation pour les différences finies : ∆x = 10−6
• Approximation initiale de la seconde dérivée : B = 1
3
Algorithme de Quasi-Newton en Une Dimension
L’algorithme de quasi-Newton est exécuté avec une boucle d’itération jusqu’à
ce que la tolérance soit atteinte.
1. Calcul de la première dérivée :
f (x + ∆x) − f (x)
f ′ (x) ≈
∆x
2. Calcul de la seconde dérivée (approximation de la Hessienne
pour 1D) :
f (x + ∆x) − 2f (x) + f (x − ∆x)
f ′′ (x) ≈
(∆x)2
3. Vérification de la seconde dérivée : Si |f ′′ (x)| < tol, alors l’algorithme
s’arrête car la seconde dérivée est proche de zéro.
4. Calcul de la direction de descente :
f ′ (x)
p=−
f ′′ (x)
5. Mise à jour de la position :
xnew = x + p
6. Critère d’arrêt : Si |f ′ (x)| < tol, l’algorithme s’arrête.
7. Mettre à jour x pour la prochaine itération : x = xnew .
Code MATLAB
Voici le code MATLAB correspondant :
% Définition de la fonction
f = @(x) (x - 3)^2 + 2;
% Paramètres d’initialisation
x = 0; % Point initial
tol = 1e-5; % Tolérance pour l’arr^
et
delta_x = 1e-6; % Petite variation pour les différences finies
B = 1; % Approximation initiale de la seconde dérivée
% Méthode de quasi-Newton en une dimension
max_iter = 100;
for k = 1:max_iter
4
% Approximation de la première dérivée
f_prime = (f(x + delta_x) - f(x)) / delta_x;
% Approximation de la seconde dérivée (Hessienne pour 1D)
f_double_prime = (f(x + delta_x) - 2*f(x) + f(x - delta_x)) / (delta_x^2);
% Si la seconde dérivée est très proche de zéro, on arr^
ete
if abs(f_double_prime) < tol
disp(’La dérivée seconde est proche de zéro, arr^et des itérations’);
break;
end
% Calcul de la direction de descente
p = -f_prime / f_double_prime;
% Mise à jour de la position
x_new = x + p;
% Critère d’arr^
et : gradient proche de zéro
if abs(f_prime) < tol
break;
end
% Mettre à jour x pour la prochaine itération
x = x_new;
end
% Affichage des résultats
fprintf(’Le minimum de f(x) est atteint en x = %.5f\n’, x);
fprintf(’La valeur de f(x) au minimum est f(x) = %.5f\n’, f(x));
Conclusion
Cette approche permet de minimiser la fonction en utilisant des différences finies
pour calculer la dérivée et la seconde dérivée, ce qui est utile lorsque le calcul
analytique est difficile ou impossible.
