Mémoires de Fin d’Etudes
Etablissement
Université de Béjaia - Abderrahmane Mira
Affiliation
Département de Recherche Opérationnelle
Auteur
BELKACEM, Brahmi
Directeur de thèse
Mohand Ouamer, Bibi (Professeur)
Filière
Mathématiques Appliquées
Diplôme
Doctorat
Titre
Méthodes primales et duales pour la programmation quadratique: extension et applications
Mots clés
Programmation quadratique: Méthodes d’activation des contraintes: Méthodes de points
Résumé
Cette thèse traite de la programmation quadratique convexe et son application à la classification binaire par les machines à vecteurs supports. Nous avons d’abord rappelé les concepts fondamentaux sur les formes quadratiques et les conditions d’optimalité de KKT pour les problèmes non linéaires avec contraintes. Ensuite, les résultats classiques de l’optimisation convexe, ainsi que la dualité lagrangienne ont été abordés, notamment ceux de la programmation quadratique convexe. Dans ce travail, on a élaboré une nouvelle méthode duale, basée sur le support coordinateur, pour la résolution d’un problème général de programmation quadratique convexe. Cette approche présente deux phases : la première consiste à construire un support coordinateur initial et la seconde permet le passage d’une itération à l’autre. Les expérimentations numériques ont montré son efficacité par rapport à la méthode d’activation des contraintes pour la résolution de ces problèmes. On a par la suite appliqué notre approche pour la résolution des problèmes de classification binaire par les SVM sur des problèmes tests de la base UCI. Mots Clés: Programmation quadratique, méthodes d’activation des contraintes, méthodes de points intérieurs, support coordinateur, critère de suboptimalité, méthode duale de support, machines à vecteurs supports (SVM). Abstract This thesis is devoted to convex quadratic programming and its application to the binary classification by support vector machines (SVM). First, we have recalled some fundamental concepts of quadratic forms and KKT optimality conditions for nonlinear problems with constraints. Classic results of the convex optimization and the lagrangian duality have been handled, especially those for the convex quadratic programming. In this work, we have elaborated a new dual method, based on the support coordinator, for the resolution of a general convex quadratic programming. This approach presents two phases: the first consists in constructing an initial coordinator support, and the second allowing us the passage from iteration to another. Numerical experimentations showed its efficiency in comparison with the active-set method for the solution of these problems. Finally, we have applied our approach for the resolution of binary classification problems by the SVM on problems tests of the datasets UCI. Key words: Quadratic programming, active-set methods, interior-points methods, coordinator support, suboptimality criterion, dual support method, machines vector support (SVM
Date de soutenance
23/05/2012
Cote
003D/11
Pagination
122 f.
Illusatration
Graph.
Format
30 cm
Notes
bibliogr.f.122 annexes
Statut
Soutenue