Contributions à la résolution de problèmes de programmation fractionnaire généralisée

Abstract

Un problème de programmation fractionnaire généralisée est un problème de programmation non-linéaire dans lequel la fonction objective à minimiser est définie comme le maximum d’un nombre fini de quotients de fonctions. De tels problèmes peuvent provenir de plusieurs domaines tels que l’économie et l’analyse numérique. On s’intéresse dans ce travail à la résolution de problèmes fractionnaires généralisés dans différentes situations, utilisant différents moyens et techniques. En particulier, on utilisera les algorithmes de type Dinkelbach, l’algorithme proximal et les méthodes proximales basées sur les fonctions de Bregman, ainsi que des techniques d’optimisation sans contraintes et des techniques de linéarisation. Dans le chapitre 1, on développe la méthode des centres de Huard pour la résolution de problèmes d’optimisation convexe avec contraintes. Une extension de cette méthode à la programmation fractionnaire généralisée est donnée dans chapitre suivant. Dans le chapitre 2, on propose un algorithme basé sur l’approche paramétrique et la méthode des centres de Huard. Cette méthode est une généralisation de cette dernière et génère une suite de problèmes sans contraintes. Le chapitre 3 se base sur la méthode décrite au chapitre 2 et sur l’algorithme proximal. On introduit alors dans ce chapitre une méthode dans laquelle des problèmes intermédiaires sans contraintes, ayant un minimum unique, sont résolus à une tolérance donnée. Dans le chapitre 4 on étudie la convergence et la vitesse de convergence de deux algorithmes basés sur la régularisation proximale de deux algorithmes de type Dinkelbach. Le chapitre 5 est consacré à un autre type de régularisation basée sur les fonctions de Bregman ou les B-fonctions. On propose dans ce chapitre dans ce chapitre un algorithme conceptuel générique qui nous permettra par la suite l’analyse de différentes méthodes. Des applications de ce schéma sont données pour la programmation fractionnaire généralisée, et en particulier pour la programmation convexe. On consacre le chapitre 6 à l’implémentation de la méthode donnée au chapitre 2. On traite dans ce chapitre le cas différentiable. A l’aide d’approximations par des fonctions quadratiques, on développe un algorithme qui ramène la résolution du problème initial à celle d’une suite de programmes quadratiques suivie d’une recherche linéaire.