We discussed the various types of relaxations of the original IP for MAP estimation, where the two non-convex constraints are the integer constraint {1, -1} on the variables, and the constraint that

However, this paper showed that, using only certain SOC constraints associated with edges of the MRF, that the SOCP was equivalent to the QP, and both were dominated by the LP. We discussed the notion of dominance, and why it makes sense that, for the minimization problem, a relaxation dominates a second relaxation if the first has a **greater** minimum value than the second. One key to understanding this is to see that every relaxation uses a feasible set that is a super set of the original problem, thus the original problem has a greater minimum value than every relaxation (why?) and hence dominates every relaxation, as would be expected.

It took me a little while to prove the facts stated in the paper regarding

The final section of the paper deals with ways of moving forward, given the theoretical results of the paper. One thing to do is to simply add the linear marginalization constraints to the SOCP, rather than using the SOC constraints on edges. Cycle inequality SOC constraints can be added to the SOCP (to get SOCP-C), but linear cycle inequalities can also be added to the LP. The paper ends by giving additional SOC constraints on cliques (SOCP-Q), results in a feasible region that is not a super set of the corresponding LP feasible region.

The takeaway message is that, only using the straightforward SOC constraints on edges is actually dominated by the LP. In general, SOCP is seen as a balance between LP and SDP, but in order to do better than LP, additional SOC constraints must be used.

The Ravikumar Lafferty QP paper is a good related paper on this general topic. One thing that is not immediately clear is why, in the QP paper, the LP performs substantially worse, despite the results in the paper we read. It could be that the LP or QP used in the Ravikumar paper do not match those in the paper we read.