Généralisation à la programmation semi-définie de la méthode de suivi de chemin établie en programmation linéaire.

  • Catherine Charles

Thèse de l'étudiant: Master typesMaster en sciences mathématiques

Résumé

La programmation semi-définie consiste à minimiser une fonction linéaire en tenant compte d'inégalités matricielles. Elle recouvre de nombreux problèmes standards, dont la programmation linéaire. De plus, la plupart des résultats ainsi qu'un grand nombre de procédés de résolution utilisés en programmation linéaire s'y étendent. Plus particulièrement, ce mémoire étudie la généralisation à la programmation semi-définie de la méthode primale-duale de points intérieurs et de suivi de chemin établie en programmation linéaire. Celle-ci engendre des points suivant de manière approximative une trajectoire spécifique. Ce chemin, situé à l'intérieur du domaine admissible, mène à une solution optimale du problème primal-dual initial. L'extension à la programmation semi-définie de différents algorithmes basés sur cette méthode et de leurs propriétés de convergence s'effectue grâce à un artifice de calcul se basant sur une transformation du problème primal-dual initial. La généralisation de la dualité et de procédés déterminant l'admissibilité du problème (avec obtention d'un itéré de départ) se ré&alise par l'intermédiaire de la théorie de la dualité en programmation conique convexe fermée. Similairement à la programmation linéaire, cette méthode possède une complexité polynomiale et s'avère performante d'après les utilisateurs.
Date de réussitejuin 1998
langueFrançais
SuperviseurJean-Jacques STRODIOT (Promoteur)

Contient cette citation

Généralisation à la programmation semi-définie de la méthode de suivi de chemin établie en programmation linéaire.
Charles, C. (Auteur). juin 1998

Thèse de l'étudiant: Master typesMaster en sciences mathématiques