Dans ce travail, nous étendons une méthode de type Burer-Monteiro pour calculer des minorants convexes (relaxation demi-définie positive) pour le problème de Maximum d'a Posteriori dans des modèles graphiques discrets où les variables ont un nombre d'états et des potentiels binaires arbitraires. Nous considérons une méthode incluant une contrainte pénalisée et une algorithme de type descente en coordonnées par bloc qui évite l’apparition de coefficient de magnitude importante dans la matrice de coûts. Nous montrons que l'algorithme est décroissant. Une évaluation empirique montre que l'approche BCD se compare favorablement à l'approche pénalisée et des minorants linéaires usuels, tels que ceux basés sur des approches de type "message passing" convergentes.

In this paper, we extend a Burer-Monteiro style method to compute low rank Semi-Definite Programming (SDP) bounds for the MAP problem on discrete graphical models with an arbitrary number of states and arbitrary pairwise potentials. We consider both a penalized constraint approach and a dedicated Block Coordinate Descent (BCD) approach which avoids large penalty coefficients in the cost matrix. We show our algorithm is decreasing. Experiments show that the BCD approach compares favorably to the penalized approach and to usual linear bounds relying on convergent message passing approaches.