Méthodes de points intérieurs et fonctions noyaux pour l’optimisation quadratique semi-définie convexe
Loading...
Date
Journal Title
Journal ISSN
Volume Title
Publisher
Université Sétif 1 - Ferhat ABBAS , Faculté des Sciences
Abstract
In this thesis, we have proposed two primal-dual interior point algorithms for convex quadratic semidefinite programming (CQSDP). The first one is of the central path where we use at each iteration the full Newton step and a suitable proximity measure to obtain an approximate solution for (CQSDP). The second algorithm is based on a new kernel function such that this function is the parameterized version of the one introduced by M. W. Zhang in 2012. The study of this function leads us to a better complexity known until now of this type of large and small update algorithm. This study was followed by numerical results to show the efficiency of these two proposed algorithms. These proposals brought new contributions of algorithmic, theoretical and numerical order
Description
Dans cette thèse, on a proposé deux algorithmes primal-dual de points intérieurs pour la programmation quadratique convexe semi-définie (CQSDP). Le premier est de trajectoire centrale tel que à chaque itération on utilise le pas de Newton complet et une mesure de proximité pour obtenir une solution approximative du (CQSDP). Le deuxième algorithme est basé sur une nouvelle fonction noyau telle que cette fonction est la version paramétrée de celle qui est introduite par de M. W. Zhang en 2012. L’étude de cette fonction nous conduit à une meilleure complexité connue jusqu’à maintenant pour ce type d’algorithme à grand et petit pas.
On suit cette étude par des résultats numériques pour montrer l’efficacité de ces deux algorithmes proposés. Ces propositions ont apporté de nouvelles contributions d’ordre algorithmique, théorique et numérique.