Complexité et implémentation numérique d’une méthode de points intérieurs pour la programmation convexe
Loading...
Date
Journal Title
Journal ISSN
Volume Title
Publisher
Université Sétif 1 - Ferhat ABBAS , Faculté des Sciences
Abstract
In this thesis, we are interested in the theoretical study (in particular the polynomial complexity) and in the numerical implementation of a primal-dual path-following method to
solve the linearly constrained convex optimization. In our study, we propose new parameters which describe the barrier parameter and the threshold which measures the
neighborhood of the central path. Through this latter, a well-defined short-step with a full- Newton primal-dual algorithm is presented and its complexity is computed. The numerical
efficiency of this algorithm is confirmed by some numerical tests, and they are very encouraging.
Description
Dans cette thèse, on s'intéresse à l'étude théorique (notamment la complexité polynomiale) et à l'implémentation numérique d'une méthode de points intérieurs de trajectoire centrale
de type primal-dual pour résoudre les problèmes de la programmation non linéaire convexe à contraintes linéaires. Dans notre étude, nous proposons de nouveaux paramètres qui
décrivent le paramètre barrière et le seuil qui mesure le voisinage de la trajectoire centrale. A travers ces derniers, un algorithme primal-dual à pas court et d’itération de Newton
complet bien défini est présenté et de plus sa complexité est calculée. L'efficacité numérique de cet algorithme est confirmée par des tests numériques qui sont encouragée