Abstract FR:

Les methodes de points interieurs jouent actuellement un role tres important dans la resolution des problemes de grande taille en programmation lineaire. Dans cette these, nous proposons deux algorithmes de points interieurs de type newton pour resoudre les problemes lineaires. Le premier, utilise la fonction barriere multiplicative primale qui est l'exponentielle d'une fonction du type fonction potentielle de karmarkar. Contrairement aux cas classiques, ici l'exposant de cette fonction varie d'une iteration a l'autre et prend des valeurs inferieures au nombre des contraintes d'inegalite du probleme. Nous montrons sous certaines hypotheses, que cet algorithme a une convergence quadratique. Les experiences numeriques faites montrent qu'il est moins sensible aux erreurs d'arrondi que les algorithmes de karmarkar et de gonzaga qui utilisent la fonction potentielle de type karmarkar. Le deuxieme algorithme que nous proposons utilise une nouvelle classe de fonctions potentielles basees sur les fonctions jauges concaves. Sous certaines hypotheses, nous montrons que la convergence de l'algorithme est quadratique ou superlineaire