In this paper, we study a nonconvex continuous relaxation of MAP inference in
discrete Markov random fields (MRFs). We show that for arbitrary MRFs, this
relaxation is tight, and a discrete stationary point of it can be easily
reached by a simple block coordinate descent algorithm. In addition, we study
the resolution of this relaxation using popular gradient methods, and further
propose a more effective solution using a multilinear decomposition framework
based on the alternating direction method of multipliers (ADMM). Experiments on
many real-world problems demonstrate that the proposed ADMM significantly
outperforms other nonconvex relaxation based methods, and compares favorably
with state of the art MRF optimization algorithms in different settings.

本研究探讨离散马尔可夫随机场的最大后验概率推断的非凸连续松弛，研究表明该松弛对于任意马尔可夫随机场都是紧密的，并且可以通过简单的块坐标下降算法轻松地达到其离散稳定点。我们进一步研究了使用基于交替方向乘子法 (ADMM) 的多线性分解框架的高效解决方案，该方案在许多现实世界的问题上的实验证明，ADMM 比其他非凸松弛方法表现更好，并且在不同设置中与最先进的 MRF 优化算法比较时表现优异。