Return to search

Étude asymptotique des méthodes de points intérieurs pour la programmation linéaire / Asymptotic study of interior point methods for linear programming

Dans cette recherche, on s’intéresse à l’étude asymptotique des méthodes de points intérieurs pour la programmation linéaire. En se basant sur les travaux de Schrijver et Padberg, nous proposons deux nouveaux pas de déplacement pour accélérer la convergence de l'algorithme de Karmarkar et réduire sa complexité algorithmique. Le premier pas est une amélioration modérée du comportement de l'algorithme, le deuxième représente le meilleur pas de déplacement fixe obtenu jusqu'à présent. Ensuite nous proposons deux approches paramétrées de la l'algorithme de trajectoire centrale basé sur les fonctions noyau. La première fonction généralise la fonction noyau proposé par Y. Q. Bai et al., la deuxième est la première fonction noyau trigonométrique qui donne la meilleure complexité algorithmique, obtenue jusqu'à présent. Ces propositions ont apporté des nouvelles contributions d'ordre algorithmique, théorique et numérique. / In this research, we are interested by asymptotic study of interior point methods for linear programming. By basing itself on the works of Schrijver and Padberg, we propose two new displacement steps to accelerate the convergence of Karmarkar's algorithm and reduce its algorithmic complexity. The first step is a moderate improvement of the behaviour of this algorithm; the second represents the best fixed displacement step obtained actually. We propose two parameterized approaches of the central trajectory algorithm via a kernel function. The first function generalizes the kernel function given by Y. Q. Bai et al., the second is the first trigonometric kernel function that gives the best algorithmic complexity, obtained until now. These proposals have made new contributions of algorithmic, theoretical and numerical order.

Identiferoai:union.ndltd.org:theses.fr/2016LEHA0019
Date03 May 2016
CreatorsBouafia, Mousaab
ContributorsLe Havre, Université Ferhat Abbas (Sétif, Algérie), Yassine, Adnan, Benterki, Djamel
Source SetsDépôt national des thèses électroniques françaises
LanguageFrench
Detected LanguageFrench
TypeElectronic Thesis or Dissertation, Text

Page generated in 0.0028 seconds