Etude des M-matrices et leurs applications en optimisation.

Abstract

Dans cette thèse, nous proposons une nouvelle approche pour résoudre un problème de programmation quadratique avec une M-matrice et des contraintes simples. Cette approche est basée sur les algorithmes de Luk et Pagano. Ces méthodes utilisent le fait qu'une M-matrice possède une inverse non négative qui permet d'obtenir une suite de points réalisables croissante et monotone. En introduisant le concept de support d'une fonction objective, notre approche conduit à une condition plus générale permettant d'obtenir une solution initiale réalisable, proche de la solution optimale. L'implémentation de notre méthode et de celle de Luk et Pagano a permis une analyse numérique, révélant que notre approche est plus efficace que celle de Luk et Pagano. En outre, une autre méthode de résolution (Box-QP), a été proposée, où nous nous sommes intéressés à résoudre un problème de programmation quadratique avec une M-matrice à diagonale dominante et des contraintes de bornes. Cette nouvelle approche inclut une procédure de prétraitement qui exploite la structure particulière de la M-matrice, permettant de simplifier le problème initial en réduisant la taille de la M-matrice. L'algorithme d'optimisation pour le problème réduit s'inspire de la méthode des points extérieurs et intègre le concept de support pour la fonction objectif. Cette intégration permet d'optimiser efficacement le problème.