fixed point of max-marginal averaging. However, the maxmarginal agreement condition by itself does not uniquely determine λ
∗and, in fact, is not sufficient to insure that g(λ) is minimized (this is related to the existence of nonminimal fixed-points observed by Kolmogorov). Hence, our approach to minimize g(λ;τ) while gradually reducing the temperature has the advantage that it cannot get stuck in such spurious fixed-points. It also helps to accelerate convergence, because the initial optimization at higher temperatures serves to smooth over irregularities of the dual function.

Computational Examples. In this section we provide some preliminary results using our approach to solve binary MRFs.

These examples are for a binary model xv **∈ {−**1,+1}
defined on a 10×10 grid similar to the one seen in Fig. 2(a).

For each node, we include a node potential fv(xv) = θvxv with θv ∼ N(0,σ 2). For each edge, we include an edge potential fu,v(xu,xv) = θuvxuxv with θuv = 1 in the "attractive" model and random θuv = ±1 in the "frustrated" model. Hence, σ controls the strength of node potentials relative to edge potentials. As seen in Fig. 5, we obtain strong duality g
∗ = f
∗
and recover the correct MAP estimates in attractive models. This is consistent with a result on optimality of TRMP in attractive models [10]. In the frustrated model, the same holds with strong node potentials, but as σ is decreased the frustration of the edge potentials cause a duality gap. However, even in these cases, we have observed that some nodes have a unique maximum in their re-summed maxmarginals, and these nodes provide a partial MAP estimate that agrees with the correct global MAP estimate. This is apparently related to the *weak tree agreement* condition for partial optimality in TRMP [10].

IV. GAUSSIAN LAGRANGIAN RELAXATION
In this section we apply the LR approach to the problem of MAP estimation in Gaussian graphical models, which is equivalent to maximizing a quadratic objective function

$$f(x;h,J)=-\frac{1}{2}x^{T}Jx+h^{T}x,\tag{26}$$

where J ≻ 0 is sparse with respect to G . Again, we construct an augmented model, which is now specified by an information form (h
′,J
′), defined by a larger graph G
′. For consistency, we also require f
′(ζ(x);h
′,J
′) = f(x;h,J) for all x. Denoting variable replication by ζ(x) = Ax, this is equivalent to A
TJ
′A = J and A
T h
′ = h. In order for the dual function to be well-defined, we also require that J
′ ≻ 0. For general J ≻ 0, it is possible that, for a given augmented graph G

′, there do not exist any J
′ ≻ 0 defined on G
′such that A
TJ
′A = J. To avoid this issue, we will focus on models that are of the form:

$$f(x)=\sum_{E\in{\mathcal{F}}}f_{E}(x_{E})$$
read $\text{\hspace{0.17em}}x\text{\hspace{0.17em}}$ of $\text{\hspace{0.17em}}$ alias
where F is a hyper-graph, composed of cliques of G ,
and each term fE(xE ) is itself a quadratic form fE (xE) =
−
1 2 x TE
JExE +h TE
xE based on JE ≻ 0. Then, J = ∑E[JE]V is the sum of these (zero-padded) submatrices. Then, it is simple to obtain a valid augmented model. We split each JE between its replicas as JE′ = r
−1 E
JE to obtain J
′ = ∑E′∈F′[JE′]V′ ≻ 0.

If there exists a representation of J in terms of 2 × 2 pairwise interactions JE ≻ 0, it is said to be *pairwise normalizable*. This condition is equivalent to the walk-summability condition considered in [17], which is related to the convergence (and correctness) of a variety of approximate inference methods [17], [18]. Here, we show that for the more general class of models of the form (27), we obtain a convergent iterative method for solving the dual problem that is tractable provided the cliques are not too large. Moreover, for this class of Gaussian models, we show that there is *no duality* gap and we always converge to the unique MAP estimate of the model. As an additional bonus, we also find that, by solving marginal agreement conditions in the augmented Gaussian model, we obtain a set of upper-bounds on the variances of each variable, although these bounds are often rather loose.

A. Gaussian LR with Linear Constraints We begin by considering the Lagrangian dual of the following linearly-constrained quadratic program:

$$\begin{array}{r l}{{\mathrm{maximize}}}&{{}-{\frac{1}{2}}x^{\prime T}J^{\prime}x^{\prime}+h^{\prime T}x^{\prime}}\\ {{\mathrm{subject~to}}}&{{}x_{a}^{\prime}=x_{b}^{\prime}{\mathrm{~for~all~}}a\equiv b.}\end{array}$$
$$(28)$$

We may express the linear constraints on x
′as Hx′ = 0. Relaxing these constraints leads to the following dual function:

$$g(\lambda)$$
g(λ) = max
$$\begin{array}{r l}{={}}&{{}\operatorname*{max}_{x^{\prime}}\{-{\frac{1}{2}}x^{\prime T}J^{\prime}x^{\prime}+(h^{\prime}+H^{T}\lambda)x^{\prime}\}}\\ {={}}&{{}{\frac{1}{2}}(h^{\prime}+H^{T}\lambda)^{T}J^{\prime-1}(h^{\prime}+H^{T}\lambda)}\end{array}$$
$$(29)$$
T λ) (29)
Moreover, by strong duality of quadratic programming [7],
it holds that g
∗ = f
∗. We also note the following equivalent representation of the dual problem:

$$g^{*}=\left\{\begin{array}{l l}{{\mathrm{minimize}}}&{{\frac{1}{2}h^{T}J^{\prime-1}h^{\prime}}}\\ {{\mathrm{subject~to}}}&{{A^{T}h^{\prime}=h}}\end{array}\right.$$
$$(30)$$
′ = h(30)
Here, h
′is the problem variable, and we consider all possible choices of h
′that are consistent with h under the constraint x
′ = Ax. The optimal choice of h
′in this problem is the one which leads to consistency in the estimate ˆx
′ = J
′−1h
′.

B. Quadratic Constraints and Log-Det Regularization Although, in Gaussian models, it is sufficient to include only linear constraints (there is no duality gap), our method can also accommodate quadratic constraints, and this results in faster convergence and tighter bounds on variances. Consider the constrained optimization problem:

sured the constrained optimization problem.  $$\begin{array}{ll}\mbox{maximize}&-\frac{1}{2}x^{T}J^{\prime}x^{\prime}+h^{T}x^{\prime}\\ \mbox{subject to}&x_{a}=x_{b},x_{a}^{2}=x_{b}^{2}\;\;\mbox{for all}\;\;a\equiv b,\\ &x_{a_{1}}x_{a_{2}}=x_{b_{1}}x_{b_{2}}\;\;\mbox{for all}\;\;(a_{1},a_{2})\equiv(b_{1},b_{2}).\end{array}\tag{31}$$  This leads to the following equivalent version of the dual 
$$(27)$$
problem with problem variables (h
′,J
′):
minimize $\frac{1}{2}h^{T}J^{\prime-1}h^{\prime}$ subject to $A^{T}h^{\prime}=h$, $A^{T}J^{\prime}A=J$, $J^{\prime}\succ0$. (32)