Méthodes de Points Intérieurs et de quasi-Newton

Introduction

   Les méthodes de points intérieurs sont apparues dans les années cinquante. Ces méthodes reposent sur la fonction barrière logarithmique définie, en 1955, par Frisch ([23]). Cette fonction barrière logarithmique sera largement étudiée dans les années soixante, notamment dans le livre de Fiacco et McCormick ([19]). C’est dans ce livre que le terme de points intérieurs sera introduit. Les itérés générés par les méthodes basées sur cette fonction sont strictement réalisables : ils restent à l’intérieur du domaine réalisable, d’où la terminologie de ces méthodes. L’engouement pour ces méthodes dans les années soixante est dû au développement de méthodes performantes en optimisation sans contrainte, citons notamment le code SUMT développé par Fiacco et McCormick ([19]). Le problème du mauvais conditionnement des matrices hessiennes des fonctions barrières d’abord étudié par Murray ([46, 45]) puis par Lootsma ([39, 40, 41]) ralentit le développement de ces méthodes au début des années soixantedix. On redécouvrira ces méthodes plus tard grâce à l’optimisation linéaire. Avant 1984, tout problème d’optimisation linéaire se résolvait par la méthode du simplexe développé par Dantzig ([17]) ou par une variante de celleci. Des recherches ont été menées pour mettre au point une autre méthode mais aucune de celles proposées n’améliorait celle du simplexe. Aussi, pendant une quarantaine d’années, cette méthode domina l’optimisation linéaire. Puis, dans les années 70, la théorie de la complexité devint une part intégrante de l’optimisation linéaire, si bien qu’on demanda aux méthodes développées de converger en un temps polynômial, c’est à dire de résoudre le problème en un nombre d’opérations qui doit être borné par un polynôme en la taille du problème. Mais la méthode du simplexe n’a pas cette propriété, comme l’ont montré Klee et Minty ([36]). On se demanda alors si un algorithme d’optimisation linéaire avait cette propriété. En 1979, Khachian proposa un algorithme de programmation linéaire appelé méthode des ellipses de Khachian ([35]). Bien que convergeant polynômialement en théorie, cet algorithme convergeait en pratique moins vite que le simplexe. Toutefois, Khachian montra théoriquement l’existence d’algorithmes à convergence polynômiale. Il restait maintenant à en trouver qui soient efficaces en pratique. Ce que fit Karmarkar en 1984 ([34]). Il proposa en effet un algorithme de points intérieurs à convergence polynômiale pour résoudre des problèmes d’optimisation linéaire. Cela provoqua un regain d’intérêt pour les méthodes de points intérieurs, aussi bien en optimisation linéaire qu’en optimisation non linéaire.

Algorithme A

   Une fois le problème (Pµ) résolu, on fait décroître le paramètre µ vers 0 et on résout ensuite un nouveau problème barrière. L’algorithme A contrôle ces itérations et diminue le paramètre de perturbation. établissons maintenant une itération de cet algorithme résolvant le problème (P). Au début de la jème itération externe, une approximation zj1:= (xj1, λj1) ∈ Z de la solution z^ := (^x, ^λ) de (1.1) et une matrice définie positive Mj 1 approchant le hessien du lagrangien en x j 1 sont supposées disponibles. On suppose connues les valeurs du paramètre de perturbation µ j > 0 et celles des seuils de précision e^j:=(e^j`, e^jc) > 0.

Données initiales

   Considérons à nouveau le problème (P). L’utilisateur doit fournir un itéré x 0 strictement réalisable au début de l’algorithme, ce qui signifie que pour tout i ∈ {1, · · · , m}, on a ci(x 0 ) < 0. Les valeurs initiales du multiplicateur noté λ 0 et du paramètre de perturbation noté µ 0 ne sont par contre pas fournies. NOPTIQ doit donc les déterminer. Une idée consiste à les choisir de façon à l’itéré (x 0 , λ0 ) soit proche de la solution des conditions d’optimalité du premier problème barrière à résoudre avec un paramètre de perturbation égal à µ 0.

Interpolation polynômiale

  Dans le cas où les constantes k1 et k2 sont négatives ou nulles, on fait une interpolation polynômiale. A partir des données connues, on calcule les coefficients du polynôme P où P(x) = ax2 + bx + c ou P(x) = ax3 + bx2 + cx + d suivant le nombre de données calculées. On cherche ensuite en quel point le minimum de ce polynôme est atteint. On détermine ce point comme celui où le gradient de la fonction s’annule. Cela nous donne alors une estimation du prochain pas. Pour plus de détails sur ces méthodes, voir [7]. Des essais numériques ont été réalisés pour tester les différentes formules d’interpolation. Dans la majorité des cas, le meilleur pas (c’est à dire celui qui donnait la plus grande décroissance de la fonction de mérite) était celui donné par l’interpolation logarithmique. Aussi, NOPTIQ emploie cette méthode d’interpolation par défaut. Si elle n’est pas possible, l’interpolation polynômiale est alors utilisée

Correction de Powell

   On compare maintenant la prise en compte de la convexité ou du manque de convexité du problème en utilisant la correction de Powell ou pas. Ne pas l’utiliser revient à faire du skipping : on ne met pas à jour la matrice M si le produit y >s n’est pas positif. Les résultats sont donnés dans les tableaux 1.6 et 1.7 et une précision de 10−8 sur les conditions d’optimalité est demandée. On remarque que la correction de Powell améliore les résultats sur de nombreux problèmes. Elle est plus performante sur 54 problèmes, équivalente sur 22 problèmes et moins bonne sur 24 problèmes. Cela peut se justifier par le fait que faire du skipping revient à ne pas modifier la matrice approchant le hessien du lagrangien pendant une ou plusieurs itérations. L’information du second ordre conservée en mémoire peut alors provenir d’itérés distants de l’itéré courant. Tandis qu’avec la méthode la de Powell, cette information est modifiée à chaque correction

Comparaison des formules de BFGS et formules de BFGS à mémoire limitée

   On a tout d’abord testé le code NOPTIQ utilisant les formules de BFGS à mémoire limitée sur des problèmes de petite et moyenne taille (voir les tableaux 1.1, 1.2 et 1.3). On a comparé les résultats obtenus avec ceux obtenus avec le code NOPTIQ utilisant les formules de BFGS à mémoire pleine. Une précision de 10−8 sur les conditions d’optimalité est demandée. Le graphique 2.3 représente le nombre d’appels au simulateur faits par NOPTIQ pour résoudre les problèmes considérés en utilisant soit les formules de BFGS à mémoire pleine (notées bfgs) soit celles à mémoire limitée (notées lbfgs). On a éliminé les problèmes non résolus par NOPTIQ et ceux dont les solutions calculées par les deux versions de NOPTIQ sont différentes. Ce graphique montre que les résultats obtenus en utilisant les formules à mémoire limitée sont comparables avec ceux obtenus en utilisant les formules à mémoire pleine. Sur certains problèmes, NOPTIQ fait beaucoup plus d’itérations en utilisant les formules de BFGS à mémoire limitée qu’en utilisant les formules à mémoire pleine. Cela s’explique par l’emploi de la correction de Powell dans les secondes formules et par le fait qu’on fasse du skipping quand on utilise les formules à mémoire limitée. On a testé l’emploi de la correction de Powell dans les formules de BFGS à mémoire limitée afin de conserver à chaque itération la paire de vecteurs calculée mais cela n’améliorait pas les résultats. On remarque aussi, sur ce graphique, que l’emploi des formules à mémoire limitée est parfois meilleur que l’emploi des formules à mémoire pleine sur certains problèmes. Cela s’explique par le fait qu’en utilisant ces formules, on conserve une information sur les données du second ordre qui est locale. Les méthodes de BFGS à mémoire pleine conservent, elles, toutes l’information du second ordre depuis le début de l’algorithme. Si cette information est initialement très éloignée de la véritable information du second ordre du problème, les formules de BFGS à mémoire pleine devront alors la corriger, ce qui peut nécessiter des itérations supplémentaires

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela rapport-gratuit.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

Remerciements
Introduction
1 Mise en œuvre d’une méthode de points intérieurs et de quasi-Newton
1.1 Introduction
1.2 Présentation de la méthode 
1.2.1 Algorithme Aµ
1.2.2 Algorithme A
1.2.3 Convergence des algorithmes
1.3 Mise en œuvre 
1.3.1 Données initiales
1.3.2 Tests d’arrêt
1.3.3 Calcul de la direction
1.3.4 Recherche linéaire
1.3.5 Formules de quasi-Newton
1.3.6 Décroissance de µ
1.4 Résultats numériques
1.4.1 Codes testés : LANCELOT et NOPTIQ
1.4.2 Résultats
1.5 Conclusion
2 Utilisation des formules de quasi-Newton à mémoire limitée
2.1 Introduction
2.2 Représentation compacte des formules de BFGS à mémoire limitée
2.2.1 Formule récursive
2.2.2 Représentation compacte
2.3 Une méthode de points intérieurs à mémoire limitée 
2.3.1 Utilisation des formules de quasi-Newton à mémoire limitée
2.3.2 Problèmes avec des contraintes de bornes
2.3.3 Problèmes avec des contraintes générales
2.4 Algorithme et convergence 
2.4.1 Algorithme
2.4.2 Analyse de convergence
2.5 Résultats numériques
2.5.1 Le code l-BFGS-B
2.5.2 Comparaisons des différents codes
2.6 Conclusion
3 Analyse de convergence d’un algorithme non réalisable de points intérieurs
3.1 Introduction 
3.2 Rappels
3.3 Hypothèse
3.4 Le problème pénalisé 
3.5 Le problème barrière 
3.6 Le pas de Newton
3.7 Le problème barrière primal-dual
3.8 Algorithme Aσ,ω µ
3.9 Convergence r-linéaire de l’algorithme Aσ,ω µ
3.10 Convergence q-superlinéaire de l’algorithme Aσ,ω µ
3.11 Algorithme global A 
3.12 Convergence de l’algorithme A 
3.13 Convergence des itérés vers le centre analytique primal-dual 
3.14 Conclusion 
Conclusion
Annexes
Bibliographie

Rapport PFE, mémoire et thèse PDFTélécharger le rapport complet

Télécharger aussi :

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *