Resultat d’implementation :
1. Cas α = 0.001 : Convergence Optimale
Résultat : La méthode a atteint le critère d'arrêt (||∇ f(xk) || <10-6) en seulement 38 itérations.
Explication:
Ce petit taux d'apprentissage est suffisamment faible pour garantir que chaque pas est une véritable
descente vers le minimum local. Il évite de "sauter" au-dessus du minimum. Pour cette fonction et ce
point initial x_0 = [1.0,0. 0,0.0, 1.0] ^ T c'est un pas efficace qui mène rapidement à la solution
optimale x* trouvée (avec f(x*) ≈ 5.8985).
2. Cas α = 0.010 : Divergence ou Oscillation Lente
Résultat : La méthode a atteint le nombre maximal d'itérations (5000) sans satisfaire
le critère d'arrêt. La valeur de la fonction objectif finale f(x) ≈ 52.76 est beaucoup plus
élevée, et surtout, la norme du gradient est très grande.
Explication : Un taux de α =0.01 est trop grand pour garantir une convergence
stable. À chaque pas, l'algorithme :
o Soit il oscille (rebondit) autour du minimum sans jamais s'en rapprocher.
o Soit il est en train de diverger lentement vers une zone où les pertes sont
beaucoup plus élevées.
o Le fait que ∇ F soit grand indique qu'il n'est pas du tout près d'un minimum (où
le gradient devrait être proche de zéro).
[Link] α= 0.100 : Divergence Explosive
Résultat : La méthode a atteint le maximum d'itérations avec des résultats NaN (Not a
Number)
Explication :
Un taux de alpha=0.1 est nettement trop grand. L'algorithme effectue des pas si importants
dans l'espace des variables que :
Il se retrouve très rapidement dans une zone où la fonction f(x) croît très rapidement.
Les valeurs de xk deviennent extrêmes.
Cela peut provoquer un débordement numérique (Overflow) lors du calcul des
exponentielles ou des puissances élevées, conduisant à des résultats Inf ou NaN. La
méthode diverge de manière "explosive".
Conclusion :
Cette analyse souligne la sensibilité de la descente de gradient à pas constant au choix de
alpha.
Pour ce problème, alpha=0.001est un taux de travail efficace. Les taux plus élevés entraînent
une instabilité ou une divergence. C'est pourquoi la recherche linéaire (Backtracking) de la
Question 2.2 est nécessaire, car elle adapte à chaque itération pour garantir la convergence et
éviter la divergenc6
Conclusion Numérique :
La Descente de Gradient avec Backtracking est une méthode robuste et plus efficace (moins
d'itérations) que la méthode à taux constant pour ce problème.
j
la Partie 4 :
(Q4.1) :
Q4.2 :
PARTIE 5
Question 5.3
Rédiger une analyse critique : Quelle méthode est la plus rapide pour ce problème ? Quelle méthode
est la plus robuste aux diérents points initiaux ? Quelles sont les limitations de chaque méthode ?
Recommandations pour un ingénieur devant résoudre ce type de problème
Critère de Vitesse Méthode Vainqueur Résultat Clé
Nombre Converge en itérations
Méthode de Newton
d'Itérations (k) (convergence quadratique)
Temps de Calcul Gradient Conjugué (PR
Converge 0.0005 secondes
(T) + Restart)
La rapidité d'une méthode est évaluée selon deux critères : le nombre d'itérations et le temps de
calcul CPU.
En itérations : La méthode de Newton est la plus rapide. Grâce à sa convergence
quadratique.
En temps CPU : Le Gradient Conjugué est le plus rapide. Bien qu'il nécessite plus
d'itérations (k=30 vs k=8), le coût de chaque itération est extrêmement faible (quelques
produits matrice-vecteur et la recherche linéaire) par rapport à Newton (calcul et factorisation
de la Hessienne à chaque étape)
2. Quelle méthode est la plus robuste aux différents points initiaux ?
La robustesse est la capacité à converger vers une solution acceptable même avec des
paramètres ou des points initiaux mal choisis .
Vainqueur : Gradient Conjugué (PR + Restart)
Justification :
Le Backtracking Armijo utilisé dans le GC garantit que la fonction objectif diminue
à chaque étape (Direction de descente garantie).
L'utilisation de la formule de Polak-Ribière (PR) et du Restart périodique (toutes les
5 itérations) empêche l'accumulation d'erreurs et de mauvaises directions, permettant
à l'algorithme de retrouver l'optimum même lorsque la DG à taux constant .
Cas Limite
La Descente de Gradient à Taux Constant a montré la plus faible robustesse, échouant
complètement pour des valeurs de alpha trop grandes (alpha=0.01, 0.1) ou pour le point initial
non standard .
Méthode Limitations Principales
Vitesse de convergence linéaire. Elle devient très lente (en itérations)
Descente de
à proximité de l'optimum, nécessitant de nombreuses étapes pour
Gradient (DG)
atteindre une haute précision (phénomène d'escalier).
Gradient Sensibilité aux non-linéarités. La propriété de conjugaison est perdue
Conjugué dans les problèmes non-quadratiques, ce qui peut ralentir la
(GC) convergence (limitation atténuée par le Restart).
Coût par itération prohibitif9. Nécessite le calcul de la Hessienne
Méthode de exacte et la résolution d'un système linéaire impliquant cette matrice à
Newton chaque itération. Cette méthode est inutilisable pour des problèmes
avec des millions de variables.
4-) Recommandations pour un ingénieur devant résoudre ce type de problème
La recommandation est faite en considérant le problème d'optimisation électrique triphasé
dans un contexte industriel réel, où la taille du problème (nombre de variables) pourrait être
beaucoup plus grande que N=4
pour un ingénieur travaillant sur des problèmes d'optimisation non-linéaire sans contraintes :
Méthode Recommandée : Gradient Conjugué (Polak-Ribière avec Restart).
o Justification : Cette méthode offre le meilleur compromis. Elle est
extrêmement rapide en temps CPU (battant même Newton sur ce petit
problème) et elle est très robuste grâce à la recherche linéaire de Armijo et au
Restart. De plus, son coût de mémoire et de calcul par itération (ne nécessitant
pas la Hessienne) la rend scalable à des problèmes de très grande taille.
Utilisation de Newton : La méthode de Newton (L-M) ne devrait être utilisée que pour des
problèmes de très petite taille où une très haute précision est requise, car son coût de calcul la rend
inutilisable pour la majorité des problèmes industriels.