Cette thèse est principalement consacrée à l'association des méthodes de points intérieurs et des techniques de l'optimisation DC et DCA pour résoudre les problèmes d'optimisation non convexes de grande taille.<br />La thèse comporte trois parties : <br />la première partie est consacrée aux techniques d'optimisations locales et s'articule autour des méthodes de points intérieurs et de la programmation DC. Nous y développons deux algorithmes. Après une présentation non exhaustive de la programmation DC, des méthodes de points intérieurs et des propriétés essentielles de la classe des matrices quasi-définies au chapitre un, nous présentons au chapitre deux un nouvel algorithme basé sur une reformulation des conditions d'optimalité de Karush-Kuhn-Tucker. Le troisième chapitre est consacré à l'intégration des techniques d'optimisation DC dans un schéma de points intérieurs, c'est l'algorithme IPDCA.<br />La seconde partie de la thèse est consacrée aux solutions globales de problèmes de programmation quadratique. Dans le premier chapitre de cette partie nous explorons l'intégration d'IPDCA dans un schéma B&B. Le second chapitre de la partie est consacré à la résolution de problèmes quadratiques à variables 0-1 par un schéma B\&B dans lequel nous faisons intervenir IPDCA. Le troisième chapitre est quant à lui consacré à l'optimisation monotone due au Professeur Tuy. Nous examinons plus particulièrement son intégration dans un B&B dans lequelle DCA est appelé pour améliorer la borne supérieure.<br />Le quatrième et dernier chapitre de cette partie est consacré à une procédure de redémarrage de DCA. <br />La dernière partie de la thèse est consacrée aux applications industrielles. Nous y appliquons les deux algorithmes développés dans la première partie de la thèse à un problème de mécanique de structure de grande dimension et à un problème en Data Mining.

Notre objectif dans cette thèse est de résoudre un problème quadratique binaire sous contraintes mixtes par les techniques d'optimisation DC. Puisque l'optimisation DC a prouvé son efficacité pour résoudre des problèmes de grandes tailles dans différents domaines, nous avons décidé d'appliquer cette approche d'optimisation pour résoudre ce problème. La partie la plus importante de l'optimisation DC est le choix d'une décomposition adéquate qui facilite la détermination et accélère la convergence de deux suites construites. La première suite converge vers la solution optimale du problème primal et la seconde converge vers la solution optimale du problème dual. Dans cette thèse, nous proposons deux décompositions DC efficaces et simples à manipuler. L'application de l'algorithme DC (DCA) nous conduit à résoudre à chaque itération un problème quadratique convexe avec des contraintes mixtes, linéaires et quadratiques. Pour cela, il faut trouver une méthode efficace et rapide pour résoudre ce dernier problème à chaque itération. Pour cela, nous appliquons trois méthodes différentes: la méthode de Newton, la programmation semi-définie positive et la méthode de points intérieurs. Nous présentons les résultats numériques comparatifs sur les mêmes repères de ces trois approches pour justifier notre choix de la méthode la plus rapide pour résoudre efficacement ce problème. / Our objective in this work is to solve a binary quadratic problem under mixed constraints by the techniques of DC optimization. As DC optimization has proved its efficiency to solve large-scale problems in different domains, we decided to apply this optimization approach to solve this problem. The most important part of D.C. optimization is the choice of an adequate decomposition that facilitates determination and speeds convergence of two constructed suites where the first converges to the optimal solution of the primal problem and the second converges to the optimal solution of the dual problem. In this work, we propose two efficient decompositions and simple to manipulate. The application of the DC Algorithm (DCA) leads us to solve at each iteration a convex quadratic problem with mixed, linear and quadratic constraints. For it, we must find an efficient and fast method to solve this last problem at each iteration. To do this, we apply three different methods: the Newton method, the semidefinite programing and interior point method. We present the comparative numerical results on the same benchmarks of these three approaches to justify our choice of the fastest method to effectively solve this problem.

Cette thèse est particulièrement destinée à traiter deux types de problèmes : clustering et l'alignement multiple de séquence. Notre objectif est de résoudre de manière satisfaisante ces problèmes globaux et de tester l'approche de la Programmation DC et DCA sur des jeux de données réelles. La thèse comporte trois parties : la première partie est consacrée aux nouvelles approches de l'optimisation non convexe. Nous y présentons une étude en profondeur de l'algorithme qui est utilisé dans cette thèse, à savoir la programmation DC et l'algorithme DC (DCA). Dans la deuxième partie, nous allons modéliser le problème clustering en trois sous-problèmes non convexes. Les deux premiers sous-problèmes se distinguent par rapport au choix de la norme utilisée, (clustering via les normes 1 et 2). Le troisième sous-problème utilise la méthode du noyau, (clustering via la méthode du noyau). La troisième partie sera consacrée à la bio-informatique. On va se focaliser sur la modélisation et la résolution de deux sous-problèmes : l'alignement multiple de séquence et l'alignement de séquence d'ARN par structure. Tous les chapitres excepté le premier se terminent par des tests numériques. / This Ph.D. thesis is particularly intended to treat two types of problems : clustering and the multiple alignment of sequence. Our objective is to solve efficiently these global problems and to test DC Programming approach and DCA on real datasets. The thesis is divided into three parts : the first part is devoted to the new approaches of nonconvex optimization-global optimization. We present it a study in depth of the algorithm which is used in this thesis, namely the programming DC and the algorithm DC ( DCA). In the second part, we will model the problem clustering in three nonconvex subproblems. The first two subproblems are distinguished compared to the choice from the norm used, (clustering via norm 1 and 2). The third subproblem uses the method of the kernel, (clustering via the method of the kernel). The third part will be devoted to bioinformatics, one goes this focused on the modeling and the resolution of two subproblems : the multiple alignment of sequence and the alignment of sequence of RNA. All the chapters except the first end in numerical tests.