Sur l'exactitude de la relaxation SDP pour le problème d'affectation quadratique

Le problème d'affectation quadratique (QAP) est un problème fondamental en optimisation combinatoire et trouve de nombreuses applications en recherche opérationnelle, vision par ordinateur et reconnaissance de motifs. Cependant, il est bien connu que trouver le minimiseur global du QAP est un problème NP-difficile. Dans ce travail, nous étudions la relaxation semi-définie (SDR) du QAP et examinons quand la SDR retrouve le minimiseur global. En particulier, nous considérons que les deux matrices d'entrée satisfont un modèle simple de signal plus bruit et montrons que lorsque le bruit est suffisamment inférieur au signal, la SDR est exacte, c'est-à-dire qu'elle retrouve le minimiseur global du QAP. Il convient de noter que cette condition suffisante est purement algébrique et ne dépend d'aucune hypothèse statistique sur les données d'entrée. Nous appliquons notre borne à plusieurs modèles statistiques tels que le modèle de Wigner gaussien corrélé. Malgré la sous-optimalité en théorie sous ces modèles, des études empiriques montrent la performance remarquable de la SDR. Notre travail pourrait être le premier pas vers une compréhension plus approfondie de l'exactitude de la SDR pour le QAP.