Abstract FR:

Cette these a pour centre d'interet les problemes de programmation convexe. Dans un premier temps, on etudie la sensibilite par l'analyse du conditionnement, de sa distance aux problemes mal poses, de sa distribution et l'erreur retrograde des problemes de programmation lineaire. Dans un second temps, on analyse la complexite de la methode barriere appliquee a la resolution de problemes de programmation convexe. Nous considerons le probleme de minimisation d'une fonction objectif supposee etre analytique convexe sur un convexe ferme d'un espace vectoriel reel de dimension finie ; nous avions auparavant etudie le cas ou les contraintes sont des inegalites lineaires. La methode barriere utilisee pour resoudre le probleme fait alors intervenir une fonction barriere auto-concordante. En supposant de plus cette barriere analytique et non degeneree (i. E de hessien inversible), nous proposons un algorithme dont le but est d'obtenir une solution approchee de ce probleme. Nous montrons que la complexite de l'algorithme depend du parametre de la fonction barriere, de la tolerance, d'un parametre apparaissant deja lors de l'etude des contraintes lineaires, et de deux autres invariants dependant de la fonction barriere. Comme cas particulier nous retrouvons les bornes de complexite usuelle pour le probleme de programmation lineaire et pour le cas ou la fonction objectif est quadratique convexe.