Soutenance mémoire
Dans la vie courante, nous sommes fréquemment confrontés à des problèmes « d’optimisation » plus ou moins complexes. Cela peut commencer au moment où l’on tente de ranger son bureau, de placer son mobilier, et aller jusqu’à un processus industriel, par exemple pour la planification des différentes tâches. Ces problèmes peuvent être exprimés sous la forme générale d’un « problème d’optimisation ». L’optimisation peut être définie comme la science qui détermine la meilleure solution à certains problèmes mathématiquement définis, qui sont souvent des modèles de physique réel. C’est une technique qui permet de « quantifier » les compromis entre des critères parfois non commensurables ([03]).
L’optimisation recouvre l’étude des critères d’optimalité pour les différents problèmes, la détermination des méthodes algorithmiques de solution, l’étude de la structure de telles méthodes et l’expérimentation de l’ordinateur avec ces méthodes avec vrais problèmes de la vie ([34]). D’un point de vue mathématique, l‘optimisation consiste à rechercher le minimum ou le maximum d’une fonction avec ou sans contraintes. L’optimisation possède ses racines au 18ième siècle dans les travaux de :
– Taylor, Newton , Lagrange, qui ont élaboré les bases des développements limités.
– Cauchy ([14]) fut le premier à mettre en œuvre une méthode d’optimisation, méthode du pas de descente, pour la résolution de problèmes sans contraintes. Il faut attendre le milieu du vingtième siècle, avec l’émergence des calculateurs et surtout la fin de la seconde guerre mondiale pour voir apparaître des avancées spectaculaires en termes de techniques d’optimisation. A noter, ces avancées ont été essentiellement obtenues en Grande Bretagne.
De nombreuses contributions apparaissent ensuite dans les années soixante. G. Zoutendijk ([81]), C. W. Carroll ([11]), P. Wolfe ([73]), R. Fletcher et M. J. D. Powell ([36]), C. Reeves ([35]), A. A. Goldstein ([44]) et A. V. Fiacco et G. P. McCormick ([37]) pour la programmation non linéaire ainsi que E. Polak et G. Ribière([56]), B.T. Polyak ([57]) et J.F. Price ([43]). Soit f : Rn → R. On cherche à résoudre le problème de minimisation sans contraintes suivant :
(P) : min {f (x) : x ∈ Rn} (0.1)
Parmi les plus anciennes méthodes utilisées pour résoudre les problèmes du type (P), on peut citer la méthode du Gradient conjugué. Cette méthode est surtout utilisée pour les problèmes de grande taille. Cette méthode a été découverte en 1952 par Hestenes et Steifel ([48]), pour la minimisation de fonctions quadratiques strictement convexes. Plusieurs mathématiciens ont étendu cette méthode pour le cas non linéaire. Ceci a été réalisé pour la première fois, en 1964 par Fletcher et Reeves ([35]) (méthode de Fletcher-Reeves) puis en 1969 par Polak, Ribière ([56]) et Polyak ([57]) (méthode de Polak-Ribière-Polyak). Une autre variante a été étudiée en 1987 par Fletcher ([34]) (Méthode de la descente conjuguée). Toutes ces méthodes génèrent une suite {xk}k∈N de la façon suivante :
xk+1 = xk + αkdk (0.2)
Les problèmes de minimisation sans contraintes et leurs algorithmes
Soit f : Rn → R. On appelle problème de minimisation sans contraintes le problème suivant :
Minimiser { f(x) : x ∈ Rn} .
L’étude de ces problèmes est importante pour des raisons diverses. Beaucoup de problèmes d’optimisation avec contraintes sont transformés en des suites de problèmes d’optimisation sans contraintes (multiplicateur de Lagrange, méthodes des penalités, …). L’étude des problèmes d’optimisation sans contraintes trouve aussi des applications dans la résoulution des systèmes non linéaires. Les méthodes numériques de résolution de divers problèmes de minimisation sans contraintes ont pris ces dernières années un bel essor si bien que la bibliographie correspondante contient des centaines d’ouvrages et d’articles. Cet intérêt n’est nullement fortuit, il reflète le rôle de premier plan que les problèmes d’optimisation jouent dans les applications. La construction d’algorithmes consacrés à la recherche efficace de minimum d’une fonction sans contraintes est un problème complexe, car il ne suffit pas d’élaborer un algorithme il faut montrer de plus qu’il emporte sur ceux connus. On compare des algorithmes en se basant sur des plusieurs critères, par exemple, la précision du résultat, le nombre d’évalutions fonctionnelles et celui d’évaluations du gradient, la vitesse de la convergence, le temps de calcul, l’occupation de la mémoire nécessaire, ….
Même en se fixant des critères de comparaison, on ne peut pas classer les algorithmes ni en indiquant lequel est le meilleur ou le pire. Le fait est qu’on obtient les estimations de l’un des critères précédents pour des classes des problèmes, et un algorithme mauvais pour une vaste classe peut s’averer efficace pour une autre, plus restreinte. L’utilisateur doit posseder tout un arsenal d’algorithmes pour être en mesure de faire face à chaque problème posé.
Aspect général des algorithmes
Pour construire des algorithmes de minimisation sans contraintes on fait appel à des procesuss itératifs du type
xk+1 = xk + αkdk
où dk détermine la direction de déplacement à partir du point xk et αk est un facteur numérique dont le grandeur donne la longueur du pas dans la direction dk. Le type d’algorithme permettant de résoudre le problème (P) sera déterminé dés qu’on définit les procédes de construction du vecteur dk et de calcul de αk à chaque itération. La façon avec laquelle on construit les vecteurs dk et les scalaires αk détermine directement les propriètés du procesuss et spécialement en ce qui concerne la convergence de la suite {xk} , la vitesse de la convergence,…. Pour s’approcher de la solution optimale du problème (P) (dans le cas général, c’est un point en lequel ont lieu peut être avec une certaine précision les conditions nécessaires d’optimalité de f), on se déplace naturellement à partir du point xk dans la direction de la décroissance de la fonction f.
Fonctions multivoques et algorithmes
Une application multivoque est une application A qui à x ∈ Rn fait correspondre un sous ensemble A(x) de Rn . Etant donné un point xk. En appliquant les instructions d’un certain algorithme, on obtient un nouveau point xk+1. Cette procédure peut être décrite par une application multivoque A applée application algorithmique. Donc étant donné un point x1 ∈ Rn , l’application algorithmique génère une suite x1, x2, ….., où xk+1 ∈ R n pour tout k. La notion d’application algorithmique fermé est directement liée à la convergence des algorithmes .
|
Table des matières
Introduction générale
I Notions de base et résultats préliminaires
1 Calcul matriciel
1.1 Indépendance linéaire
1.2 Produit scalaire et normes vectorielles
1.3 Normes matricielles
1.4 Orthogonalité dans Rn
2 Analyse convexe
2.1 Ensembles et fonctions convexes
3 Optimisation sans contraintes
3.1 Différentiabilité
3.1.1 Gradient, Hessien
3.1.2 Dérivée directionnelle
3.2 Conditions d’optimalité des problèmes d’optimisation sans contraintes
3.2.1 Conditions nécessaires d’optimalité
3.2.2 Conditions suffisantes d’optimalité
3.3 Les problèmes de minimisation sans contraintes et leurs algorithmes
3.3.1 Aspect général des algorithmes
3.3.2 Fonctions multivoques et algorithmes
3.4 Convergence globale des algorithmes
3.5 Modes et vitesse de convergence
II Optimisation unidimensionnelle ou recherche linéaire
1 Objectifs à atteindre
1.1 Le premier objectif
1.2 Le second objectif
2 Recherches linéaires exactes et inexactes
2.1 Recherches linéaires exactes
2.1.1 Les inconvénients des recherches linéaires exactes
2.1.2 Intervalle de sécurité
2.1.3 Algorithme de base
2.2 Recherches linéaires inexactes
2.2.1 Schéma des recherches linéaires inexactes
2.3 La règle d’Armijo
2.3.1 Test d’Armijo
2.4 La règle de Goldstein&Price
2.4.1 Test de Goldstein&Price
2.5 La règle de Wolfe
2.5.1 Test de Wolfe
2.5.2 Conditions de Wolfe fortes
2.5.3 La règle de Wolfe relaxée
III Méthodes a directions de descentes et méthodes à directions conjuguées
1 Principe général des Méthodes à directions de descentes
1.1 Direction de descente
1.2 Description des méthodes à directions de descentes
2 Exemples de méthodes à directions de descente
2.1 Exemples de choix de directions de descente
2.2 Exemples de choix de pas αk
3 Convergence des méthodes à directions de descente
3.1 Condition de Zoutendijk
4 Méthodes du gradient conjugué
5 Le principe général d’une méthode à directions conjuguées
5.1 Description de la méthode
6 Méthode de gradient conjugué dans le cas quadratique
6.1 Algorithme de La méthode du gradient conjugué pour les fonctions quadratiques
6.2 La validité de l’algorithme du gradient conjugué linéaire
6.2.1 Les avantages de la méthode du gradient conjugué quadratique
6.3 Différentes formules de βk+1 dans le cas quadratique
7 Méthode du gradient conjugué dans le cas non quadratique
7.1 Algorithme de La méthode du gradient conjugué pour les fonctions quelconques
IV Synthèse des résultats de convergence des méthodes du gradient conjugué
1 Hypothèses C1 et C2 et théorème de Zoutendijk
1.1 Hypothèses C1 et C2 (de Lipschitz et de bornetude)
1.2 Théorème de Zoutendijk
1.3 Utilisation du théorème de Zoutendijk pour démontrer la convergence globale
2 Role joué par la direction de recherche initiale
3 Les méthodes dans lesquelles le terme kgk+1k 2 figure dans le numérateur de βk
3.1 Méthode de Fletcher-Reeves
3.1.1 Synthèse des principaux résultats de convergence pour la méthode de Fletcher-Reeves
3.1.2 Résultats d’El Baali
3.2 Méthode de descente conjuguée
3.3 Méthode de Dai-Yuan
3.3.1 Introduction
3.3.2 Théorèmes de convergence de Dai et Yuan exigeant seulement la condition de Wolfe et la condition de Lipschitz C1
3.3.3 Résultat de Dai et Yuan sur la descente suffisante
3.4 Méthode de Dai-Yuan généralisée
3.4.1 Applications du théorème à la méthode de Dai Yuan
3.4.2 Applications du théorème à la méthode de Fletcher Reeves
4 Les méthodes où gT k+1yk figure dans le numérateur de βk
4.1 Méthode de Polak-Ribière-Polyak
4.1.1 Introduction
4.1.2 Modification de la méthode PRP en agissant sur le coéfficient βk
4.1.3 Modification de la méthode PRP en agissant sur le pas de la recherche linéaire αk
4.2 Méthode de Hestenes et Stiefel HS
4.2.1 Introduction
4.2.2 Convergence de la méthode HS
4.3 Méthode de Liu et Storey LS
5 Méthodes hybrides et familles paramétriques du gradient conjugué
5.1 Les méthodes hybrides
5.1.1 Méthodes hybrides utilisant FR et PRP
5.1.2 Méthodes hybrides utilisant DY et HS
5.2 Les méthodes unifiées
V Modification de la recherche linéaire d’Armijo pour satisfaire les propriétés de convergence globale de la méthode du gradient conjugué de HestenesStiefel
1 Nouvelle recherche linéaire inéxacte d’Armijo modifiée .
2 Le nouveau Algorithme. Définition et propriétés générales
3 Convergence globale du nouveau Algorithme
4 Etude de la vitesse de convergence
5 Tests numériques
5.1 les profils de performance numérique
Annexe
1 Programme en fortran 77 d’ Armijo
2 Programme en fortran 77 de Goldschtien
3 Programme en fortran 77 de Wolfe
4 Programme en fortran 90 de la méthode du gradient conjugé
Bibliographie
Conclusion générale
