Soutenance mémoire
Les problèmes de minimisation sans contraintes et leurs algorithmes
Aspect général des algorithmes
Les algorithmes d’optimisation sont itératifs. Ils commencent avec un jeu (guess)initial des valeurs optimales des variables et puis ils génèrent une suite d’estimés améliorées jusqu’à l’obtention d’une solution. La stratégie employée afin de procéder d’une itérée à la suivante est ce qui distingue un algorithme d’un autre. La plupart des stratégies utilisent les valeurs de la fonction objectif f , les contraintes et possiblement les première et deuxième dérivées de ces fonctions. Certains algorithmes accumulent l’information obtenue aux itérations précédentes, tandis que d’autres utilisent que de l’information locale du point actuel. Tout algorithme de bonne qualité devrait posséder les propriétés suivantes :
• Robustesse : L’algorithme doit marcher bien sur une gamme de problèmes dans sa classe, pour tous les choix raisonnables de valeurs initiales.
• Eficacité : L’algorithme ne doit pas nécessiter du temps ou du stockage excessif sur l’ordinateur.
• Précision : L’algorithme doit être capable d’identifier une solution avec précision, sans être trop sensible aux erreurs dans les données ou erreurs d’arrondi pendant le calcul.
Ces exigences peuvent être en conflit. Par exemple, une méthode qui converge rapidement peut demander trop de place de stockage pour des grands problèmes. De l’autre coté, une méthode robuste peut être trop lente. Des compromis entre taux de convergence et besoins de stockage, entre robustesse et vitesse, et ainsi de suite, sont des problèmes au centre de l’optimisation numérique. Ils recevront de la considération soigneuse dans ce cours. La théorie mathématique d’optimisation est utilisée aussi bien pour caractériser des points optimaux, que pour fournir une base pour les algorithmes. Il est impossible d’avoir une bonne compréhension d’optimisation numérique sans une prise ferme sur la théorie sous-jacente. Ainsi, ce cours va donner un traitement solide des conditions d’optimalité, aussi bien que l’analyse de convergence qui révèle les forces et les faiblesses des algorithmes les plus importants.
Algorithme à directions de descente
Definition 16 Un algorithme à directions de descente est un algorithme d’optimisation différentiable (l’optimisation dont il est question ici est une branche des mathématiques), destiné à minimiser une fonction réelle différentiable définie sur un espace euclidien (par exemple, Rn , l’espace des n-uplets de nombres réels, muni d’un produit scalaire) ou, plus généralement, sur un espace hilbertien. L’algorithme est itératif et procède donc par améliorations successives. Au point courant, un déplacement est effectué le long d’une direction de descente, de manière à faire décroître la fonction. Le déplacement le long de cette direction est déterminé par la technique numérique connue sous le nom de recherche linéaire.
Cette approche algorithmique peut être vue comme une technique de globalisation, c’est-à-dire une méthode permettant d’obtenir la convergence des itérés (sous certaines conditions) quel que soit l’itéré initial choisi. Elle s’apparente ainsi aux algorithmes à régions de confiance ; ces dernières améliorent légèrement (mais parfois de manière décisive) leurs résultats de convergence mais sont plus compliquées à mettre en œuvre, ce qui limite parfois leur application. Les algorithmes à directions de descente s’étendent aux problèmes avec contraintes simples (pourvu que la projection sur l’ensemble admissible soit aisée, peu coûteuse en temps de calcul) ou pour des problèmes avec contraintes fonctionnelles non linéaires, par l’intermédiaire de fonctions de mérite. Elles sont aussi utilisées en optimisation non lisse.
Principes de l’algorithme
Cadre Le cadre est le suivant. On cherche un point x∗ qui minimise une fonction différentiable
x ∈ E 7→ f(x) ∈ R
définie sur un espace hilbertien E, dont on note h·,·i le produit scalaire et k · k la norme associée. On note f’ (x) et ∇f(x) la dérivée et le gradient de f en x, si bien que
∀ d ∈ E : f'(x) · d = ∇f(x), d.
Énoncé Les algorithmes à directions de descente cherchent un minimum de f en générant une suite de points (xk)k>1, appelés itérés, qui approchent de mieux en mieux un minimiseur x∗ du critère f, si tout va bien. Cette suite est construite en se fondant sur deux constructions : calcul d’une direction de descente dk ∈ E, détermination d’un pas αk, qui est un nombre réel strictement positif, le long de la direction de descente de telle sorte que le nouvel itéré donne au critère une valeur inférieure à celle qu’il a en l’itéré courant ; le nouvel itéré est de la forme suivante :
xk+1 := xk + αkdk;
cette opération de détermination du pas s’appelle la recherche linéaire. Ces deux opérations seront décrites ci-dessous, mais on peut dès à présent résumer l’algorithme. Il s’agit d’un schéma algorithmique, car beaucoup d’aspects de celui-ci ne sont pas spécifiés avec précision.
Schéma On se donne un point/itéré initial x1 ∈ E et un seuil de tolérance ε > 0. Un algorithme à directions de descente définit une suite d’itérés x1, x2, . . . ∈ E, jusqu’à ce qu’un test d’arrêt soit satisfait. Il passe de xk à xk+1(voir figure 2.1) par les étapes suivantes.
1) Simulation : calcul de ∇f(xk) au moins.
2) Test d’arrêt : si ∇f(xk) 6 ε, arrêt.
3) Direction : calcul d’une direction de descente dk ∈ E.
4) Recherche linéaire : déterminer un pas αk > 0 le long de dk. Nouvel itéré :
xk+1 = xk + αkdk.
À propos du test d’arrêt En pratique, il faudra prendre ε > 0 dans le test d’arrêt de l’étape 2 ; la valeur nulle de cette tolérance a été admise uniquement pour simplifier l’expression des résultats de convergence ci-dessous. Dans les problèmes sans contrainte, il est normal que le test d’arrêt porte sur la petitesse du gradient (ε est généralement pris petit). C’est en effet ce que suggère la condition nécessaire d’optimalité du premier ordre ∇f(x∗) = 0. Comme xk n’est jamais exactement égal à x∗, ce test ne pourra fonctionner que si ∇f(x) est faible en norme pour x voisin de x∗, ce qui revient pratiquement à supposer que f est de classe C1 . Par ailleurs, un tel test d’arrêt suggère qu’un algorithme à directions de descente ne peut pas trouver mieux qu’un point stationnaire de f. C’est en effet souvent le cas, mais ce point faible est rarement rédhibitoire en pratique. On peut noter qu’il existe une version élaborée des méthodes à régions de confiance qui permet de trouver un minimum local, évitant ainsi les points stationnaires qui n’ont pas cette propriété de minimalité locale. On est parfois tenté d’arrêter l’algorithme si le critère f ne décroît presque plus. Ceci n’est pas sans risque et il vaut mieux ne pas utiliser un tel test d’arrêt, car une faible variation du critère peut se produire loin d’une solution. En effet, au premier ordre, f(xk+1) ‘ f(xk) revient à αkh∇f(xk), dki ‘ 0, ce qui peut arriver si le pas αk est petit (c’est en général très suspect) ou si la direction de descente fait avec l’opposé du gradient un angle proche de 90 degrés, une situation qui se rencontre fréquemment (si l’algorithme est bien conçu, cela traduit un mauvais conditionnement du problème).
Choix d’une direction de descente
En optimisation différentiable, qui est une discipline d’analyse numérique en mathématiques étudiant en particulier les algorithmes minimisant des fonctions différentiables sur des ensembles, une direction de descente est une direction le long de laquelle la fonction à minimiser a une dérivée directionnelle strictement négative. Ces directions sont utilisées par les méthodes à directions de descente.
C’est le long de ces directions qu’un déplacement est effectué afin de trouver l’itéré suivant, en lequel la fonction à minimiser prend une valeur inférieure à celle qu’elle a en l’itéré courant.
|
Table des matières
Introduction
1 Optimisation sans contraintes
1.1 Rappels de pré-requis Mathématiques
1.1.1 Espace normé
1.1.2 Valeurs propres et vecteurs propres
1.1.3 Matrices symétriques
1.1.4 Différentiabilité
1.1.5 Convergence des Suites
1.1.6 Extrema d’une fonction
1.2 Définition d’un problème d’optimisation
1.2.1 Classification des problèmes d’optimisation
1.2.2 Terminologie
2 Les problèmes de minimisation sans contraintes et leurs algorithmes
2.1 Aspect général des algorithmes
2.1.1 Algorithme à directions de descente
2.1.2 Choix d’une direction de descente
2.1.3 Règles de recherche linéaire
2.2 Convergence et vitesse de convergence d’un algorithme à directions de descente
2.2.1 Convergence
2.2.2 Vitesse de convergence
2.3 Contribution de la recherche linéaire inexacte à la convergence des algorithmes à directions de descente
3 La méthode du gradient conjugué
3.1 La méthode du gradient conjugué linéaire
3.1.1 La méthode du gradient conjugué linéaire vue comme une méthode directe
3.1.2 La méthode du gradient conjugué linéaire vue comme une méthode itérative
3.1.3 Algorithme de La méthode du gradient conjugué linéaire
3.1.4 Convergence de la méthode de gradient conjugué linéaire
3.1.5 Le gradient conjugué linéaire pré conditionné
3.1.6 Les avantages de la méthode du gradient conjugué linéaire
3.2 La méthode du gradient conjugué non linéaire
3.2.1 La méthode de Fletcher-Reeves
3.2.2 La méthode de Polak-Ribière Polyak
3.2.3 Convergence de la méthode de gradient conjugué non linéaire
3.2.4 Condition de conjugaison
4 APPLICATION DE LA TECHNIQUE DE SYMETRIE DE POWELL AUX METHODES DU GRADIENT CONJUGUE AVEC LA GENERALISATION DE CONDITION DE CONJUGAISON
4.1 Introduction
4.2 Application de la technique de symétrie de Powell au méthode du gradient conjugué
4.3 La propriété de descente suffisante et algorithme de descente
4.4 La convergence de l’algorithme GDSHS
4.5 Expérience numérique
4.6 Remarques finales
Conclusion
Bibliographie
