___________________________________________________________________________ Uni

___________________________________________________________________________ Université du Havre Ecole doctorale SPMII ___________________________________________________________________________ Laboratoire de mathématiques Appliquées du Havre – EA 3821 Etude et extensions d’algorithmes de points intérieurs pour la programmation non linéaire THESE Présentée et soutenue publiquement le / /2007 Pour l’obtention du Doctorat de l’université du Havre (spécialité optimisation) Par KEBBICHE Zakia Composition du jury Naceureddinne Bensalem Professeur à l’UFA-Sétif Président et rapporteur Jean-Rodolphe Roche Professeur à l’Université de Nancy I Rapporteur Sérigne Gueye M.C. à l’Université du Havre Examinateur Djamel Benterki M.C. à l’UFA-Sétif Examinateur Abdelkrim Keraghel M.C. à l’UFA-Sétif Directeur de Thèse en Algérie Adnan Yassine Professeur à l’Université du Havre Directeur de Thèse en France REMERCIEMENTS Je remercie Monsieur le professeur Abdelkrim Keraghel directeur du laboratoire de mathématiques fondamentales et numériques (LMFN), université Ferhat Abbas, Sétif et le professeur Adnan Yassine directeur du laboratoire de mathématiques appliquées (LMAH), université du Havre, d’avoir accepter de diriger cette thèse, qui par leurs conseils pertinents, leurs remarques et leurs encouragements m’ont permis de la réaliser. J'exprime mon respect à Monsieur le professeur Naceuredinne Bensalem qui m’a fait l'honneur de présider le jury de cette thèse, je le remercie respectueusement. Je tiens aussi à exprimer mes vifs remerciements et respects à Messieurs : Jean -Rodolphe Roche Professeur à l’université de Nancy I (France), Sérigne Gueye Maître de conférences à l’université du Havre( France) et Djamel Benterki Maître de conférences à l’université Ferhat Abbas-Sétif, qui ont bien accepter de juger ce travail et d’en être les examinateurs. Je remercie spécialement Monsieur : Mohammed Achache, Maître de conférences à l’université Ferhat Abbas-Sétif, pour son aide , ses conseils et ses encouragements. Je remercie toute l’équipe d’optimisation du laboratoire de mathématiques fondamentales et numériques de département de mathématiques de Sétif et l’équipe d’optimisation du laboratoire de mathématiques appliquées du Havre pour leurs aides continues et leurs encouragements. Mes remerciements s’adressent également à toute l’équipe administrative des départements de mathématiques de Sétif et du Havre d’avoir mis à notre service tous les moyens disponibles, en particulier le comité et le conseil scientifique d’avoir entrepris avec une grande souplesse les démarches nécessaires pour la soutenance. Enfin, je remercie tous ceux qui m’ont aidé de près ou de loin quelqu’ils soient et d’où qu’ils soient. TABLE DES MATIÈRES INTRODUCTION GÉNÉRALE….…………...……………………….1 CHAPITRE I MÉTHODES DE TRAJECTOIRE CENTRALE POUR LE PROBLÈME DE COMPLÉMENTARITÉ LINÉAIRE I.1. Préliminaires…………………………………………………….………..…4 I.2. Programmation mathématique………………………… ...……….…...…...5 I.2.1. Classification d’un programme mathématique…………………….…6 I.2.2. Qualification des contraintes…………………………………………6 I.2.3. Principaux résultats d’existence…………………………………..….7 I.2.4. Conditions d’optimalité…………………………………….…….…..7 I.3. Programmation linéaire (PL)…………………………………………….….8 Méthodes de résolution d’un programme linéaire………………..…………9 1- Méthode du simplexe…………………………………...………………..9 2- Méthodes de points intérieurs….……………….………………………..9 I.4. Programmation quadratique (PQ)…………………………………...……..11 Méthode de résolution d’un (PQ)………………………………………..…12 I.5. Complémentarité linéaire……………………………………. ……………12 Transformation d’un programme quadratique convexe en un programme de complémentarité linéaire………………………………………………....…….12 Transformation d’un programme complémentaire linéaire en un programme quadratique convexe………………………………………….….......................14 Méthodes de résolution d’un programme complémentaire linéaire………..15 a- Méthode de Lemke……………………………………………………...15 b- Méthode de points intérieurs………………………………………...…15 Méthodes de trajectoire centrale………………………………….………...16 Problème d’initialisation…………………………………………………...22 Méthode de trajectoire centrale avec poids………………………..……….22 Aspects numériques…………………….………………………. …………27 Méthode de trajectoire centrale non réalisable..………….………..............36 Aspects numériques…………………………………………. …………….39 Commentaire………………………………………………………………40 CHAPITRE II MINIMISATION D’UNE FONCTION CONVEXE SOUS CONTRAINTES LINÉAIRES PAR UNE MÉTHODE DE TRAJECTOIRE CENTRALE AVEC POIDS II.1. Description de la méthode classique………………………………...…….42 II.2. Méthode de trajectoire centrale avec poids…………………………..…....45 Description………………………….…………...…………………...…...45 Algorithme………………………………………………………………..47 Calcul de la direction de déplacement………………..…………………..48 Convergence…………………………………...………….……………...49 CHAPITRE III UNE VARIANTE DE TYPE PROJECTIF POUR LA MINIMISATION D’UNE FONCTION CONVEXE SOUS CONTRAINTES LINÉAIRES III.1. Méthode de Karmarkar……………… ………………….……………… 59 Description de l’algorithme de base……………………………………...59 Convergence de l’algorithme…………………………………………….62 III.2. Généralisation de l’algorithme de base………………………….….……63 III.3. Extension de la méthode de Karmarkar ……………………………….…65 Formulation du problème……….………………….……..….……….…66 Linéarisation……………………………………….……………………..68 Description de l’algorithme………………………………………………69 Etude de la convergence……………………………….……..……….….70 CONCLUSION………………………………..…………………..………..74 BIBLIOGRAPHIE ……………………….…………….……..…….. 76 Résumé Dans cette thèse, nous présentons une étude algorithmique et numérique concernant la méthode de trajectoire centrale appliquée au problème de complémentarité linéaire considéré comme une formulation unificatrice de la programmation linéaire et la programmation quadratique convexe. Puis, nous proposons deux variantes intéressantes, l’une de trajectoire centrale et l’autre de type projectif avec linéarisation, pour minimiser une fonction convexe différentiable sur un polyèdre. Les algorithmes sont bien définis et les résultats théoriques correspondants sont établis. Mots clés : Programmation linéaire, programmation quadratique convexe, complémentarité linéaire, programmation non linéaire, méthodes de points intérieurs, méthode de trajectoire centrale, méthode projective avec linéarisation. Abstract In this thesis, we present an algorithmically and numerical study concerning the central path method for linear complementarity problem which is considered as an unifying framework of linear and quadratic programming. Then, we propose two interesting variants namely the central path and the projective with linearization methods for minimizing a convex differentiable function on a polyhedral set. The algorithms are well defined and the corresponding theoretical results are established. Key words: Linear programming, convex quadratic programming, linear complementarity problem, nonlinear programming, central path interior point methods, projective with linearization methods. INTRODUCTION GÉNÉRALE La résolution d’un problème d’optimisation non linéaire de taille importante reste toujours un challenge malgré tout le succès observé dans ce domaine. Le relancement des méthodes de points intérieurs depuis 1984 [9] a donné espoir aux spécialistes du domaine pour réaliser des progrès considérables dans ce sens. Ces méthodes ont fait leurs preuves dans le domaine de la programmation linéaire (PL) no- tamment par leur bonnes propriétés théoriques (complexité polynômiale et convergence superlinéaire) et leur bon comportement numérique. Aussitôt, des variantes sont intro- duites pour la programmation quadratique et la complémentarité linéaire. Ceci étant, il faut signaler tout de même que ( sur le plan technique ), ces méthodes présentent des inconvénients d’ordre algorithmique et numérique entre autre : le problème d’initialisation et le coût excessif de l’itération lié aux choix de la direction et du pas de déplacement. Notre étude est répartie en deux volets : Le premier est une étude qualitative d’une classe privilégiée de méthodes de points in- térieurs, celle de trajectoire centrale. L’e¤ort est concentré sur le problème d’initialisation pour lequel nous proposons deux alternatives : trajectoire centrale avec poids et trajec- toire centrale non réalisable. Le modèle d’application étant celui de la complémentarité linéaire monotone qui couvre la programmation linéaire et la programmation quadra- tique convexe. Nous avons ainsi amélioré nettement le comportement numérique des algorithmes correspondants. Le deuxième volet concerne l’extension des méthodes de trajectoire centrale et les méthodes projectives pour des problèmes non linéaires en commençant par minimiser une fonction non linéaire convexe di¤érentiable sur un polyèdre. A ce propos, le mélange des techniques de linéarisation et les ingrédients de l’approche projective ont donné lieu à un algorithme simple et prometteur. Une variante de la méth- ode de trajectoire centrale avec poids est également à l’ordre du jour, dans les deux cas, les résultats théoriques sont établis. La thèse est présentée en trois chapitres : 1 Dans le premier chapitre, nous présentons quelques notions de base sur la programmation mathématique, puis une étude théorique et numérique des méthodes de trajectoire cen- trale appliquées à un programme complémentaire linéaire comme formulation uni…catrice de la programmation linéaire et la programmation quadratique convexe. Une extension de la méthode de trajectoire centrale avec poids pour la minimisation d’une fonction convexe sous contraintes linéaires est décrite dans le deuxième chapitre. Dans le dernier chapitre, les techniques de linéarisation sont combinées avec les ingré- dients de l’approche projective pour élaborer une méthode simple possédant des atouts d’un comportement numérique. 2 Chapter 1 Méthodes de trajectoire centrale pour le problème de complémentarité linéaire 3 1.1 Préliminaires - Un ensemble D  Rn est dit convexe si : 8x; y 2 D : (1 )x + y 2 D; 8 2 [0; 1]: - D est dit a¢ne si : 8x; y 2 D : (1 )x + y 2 D; 8 2 R: - D est un polyèdre s’il s’écrit comme suit : D = fx 2 Rn : pt ix  i; i = 1; :::; mg où pi est un vecteur non nul de Rn et i est un scalaire pour i = 1; :::; m: - Une fonction f : Rn ! R est dite convexe sur D si : f[(1 )x + y]  (1 )f(x) + f(y); 8 2 [0; 1]: - f est dite strictement convexe si l’inégalité ci-dessus est toujours stricte 8x 6= y; 8 2 ]0; 1[: - f est dite a¢ne si : f[(1 )x + y] = (1 )f(x) + f(y); 8 2 R: 4 1.2 Programmation mathématique En général, un programme mathématique est dé…ni comme suit : (PM) 8 < : min f(x) x 2 D  Rn où : f : Rn ! R est une fonction continûment di¤érentiable appelée fonction objectif et D est appelé ensemble des solutions réalisables présenté souvent comme : D = U \ V , avec: U = fx 2 Rn : fi(x)  0; i = 1; :::; mg et V = fx 2 Rn : gi(x) = 0; i = 1; :::; pg: Dé…nitions - On appelle solution réalisable de (PM) tout point véri…ant les contraintes ( i.e. : appartenant à D ). - Une solution réalisable qui minimise l’objectif sur D est dite solution uploads/Litterature/ 4 1 .pdf

Documents similaires

1 Exercice n° : 1 1) Une solution (0,1 mol. L-1) d’acide méthanoïque a un pH de 0 0

1 Le Cid Pierre Corneille Oeuvre du domaine public. En lecture libre sur Atrame 0 0

Essai de corrigé du devoir d’Analyse Numérique Exercice I : 1. Une bonne raison 0 0

Toutes les méthodes ne se valent pas Mixte Syllabique Il était une fois un homm 0 0

Bac pro Travaux publics S7.1 IMPLANTATIONS ET RELEVES S7.1.1.5 Le carnet de niv 0 0

Ecole normale supérieure- Ouargla. Département des langues étrangères- Français 0 0

UNIVERSITE Psychologie Lausanne, le 27 février 2012 Marine Lacroix Histoire de 0 0

Carnet de lecture 1 : la littérature d’idées du XVIème au XVIIIème siècle I- Le 0 0

Règles de typographie française Règles de typographie française applicables à l 0 0

BLAISE PASCAL PT 2019-2020 Chapitre 10 – Électronique ALI et rétroaction Au pro 0 0

• Détails
• Publié le Jui 21, 2022
• Catégorie Literature / Litté...
• Langue French
• Taille du fichier 0.3474MB