Note that the Lagrange multipliers may be interpreted as parameterizing all consistent splittings, θ
′(λ) spans the subspace of all consistent θ
′ parameters.2 It is tractable to maximize the Lagrangian, as it is defined over the thin graph G
′. The value of this maximization defines the *dual function*:

$$g(\lambda)=\operatorname*{max}_{\lambda}L(x^{\prime},\lambda)$$
x
′,λ) (11)
Note that this is an *unconstrained* optimization over X
′, and its solution need not lead to a consistent x
′ ∈ ζ(X). However, if this x
′is consistent then it is an optimal solution of the constrained optimization problem (7), and hence x = ζ
−1(x
′)
(which is well-defined for consistent x
′) is also an optimal solution of the original problem. This is the goal of our approach, to find tractable relaxations of the MAP estimation problem which lead to the correct MAP estimate. This motivates solution of the *dual problem*:

$$\operatorname*{min}_{\lambda}g(\lambda)\triangleq g^{*}$$
λ

∗(12)
Appealing to well-known results [7], [8], we conclude:
Proposition 1 (Lagrangian duality): We have g(λ) ≥ f
∗
for all λ. Hence g
∗ ≥ f
∗. If g(λ
∗) = g
∗, then one of the following holds:
(i) There exists a consistent solution:

$$x^{\prime}\in\arg\operatorname*{max}_{x^{\prime}\in\mathbb{X}^{\prime}}L(x^{\prime};\lambda^{*})\cap\zeta(\mathbb{X}).$$

Then, we have *strong duality g*∗ = f
∗and the set of all MAP estimates is obtained as:

$$\operatorname{arg}_{x^{\prime}\in\zeta(\mathbb{X})}f^{\prime}(x^{\prime})=\operatorname*{arg\operatorname*{max}_{x^{\prime}\in\mathbb{X}}}L(x^{\prime},\lambda^{*})\cap\zeta(\mathbb{X}).$$

(ii) There are no consistent solutions:

$$\arg\operatorname*{max}_{x^{\prime}\in\mathbb{T}^{\prime}}L(x^{\prime};\lambda^{*})\cap\zeta(\mathbb{X})=\emptyset.$$
x
′∈X′
Then, there is a *duality gap g*∗ > f
∗and no choice of λ will provide a consistent solution.

Also, condition (i) holds only if g(λ
∗) = g
∗.

This result generalizes the analogous *strong treeagreement* optimality condition for TRMP, and clarifies its connection to standard Lagrangian duality results for integer programs. To provide some intuition, we present the following geometric interpretation illustrated in Fig. 3. The dual function is the maximum over a finite set of linear functions in λ indexed by x
′. For each x
′ ∈ X
′,
there is a linear function g(λ;x
′) = ha(x
′),λi + b(x
′), with a(x
′) = (φA(x
′) − φB(x
′))A≡B, which is the gradient, and b(x
′) = f
′(x
′). The graph of each of these functions defines a hyperplane in R
d+1, where d is the number of constraints.

The flat hyperplanes, with a = 0, correspond to consistent assignments x
′ ∈ ζ(X). The remaining sloped hyperplanes represent inconsistent assignments. Hence, the highest flat hyperplane corresponds to the optimal MAP estimate, with height equal to f
∗. The dual function g(λ) is defined by the 2We obtain a minimal λ parameterization by only using a subset of constraints in (9), such that {(φA(x
′)−φB(x
′))} are linearly independent.

![0_image_0.png](0_image_0.png)

$$(11)$$
$$(12)$$

maximum height over this set of hyperplanes for each λ, and is therefore convex, piece-wise linear and greater than or equal to f
∗for all λ. In the case of a duality gap, the inconsistent hyperplanes hide the consistent ones, as depicted in (a), so that the minimum of the dual function is defined by an intersection of slanted hyperplanes corresponding to inconsistent assignments of x
′. If there is no duality gap, as depicted in (b), then the minimum is defined by the flat hyperplane corresponding to a consistent assignment. Its intersection with slanted hyperplanes defines the polytope of optimal Lagrange multipliers over which the maximum flat hyperplane is exposed.

## D. Linear Programming Formulations

We briefly consider a connection between this LR picture and TRMP [9], [10] and related linear programming approaches [11], [12], [13]. This analysis also serves to understand when different relaxations of the MAP estimation problem will be equivalent.

The *epigraph* of the dual function is defined as the set of all points (λ,h) = R
d+1 where g(λ) ≤ h, that is, where a(x
′)λ +b(x
′) ≤ h for all x
′. Thus, the minimum of the dual function is equal to the lowest point of the epigraph, which defines a linear program (LP) over (λ,h) ∈ R
d+1:

$$\begin{array}{r l}{{\mathrm{minimize}}}&{{h}}\\ {{\mathrm{subject~to}}}&{{\langle a(x^{\prime}),\lambda\rangle+b(x^{\prime})\leq h{\mathrm{~for~all~}}x^{\prime}.}}\end{array}$$
$$(13)$$

′.(13)
Note that there are exponentially many constraints in this formulation, so it is intractable. However, recalling that it is tractable to compute the dual function for a given λ, using the max-product algorithm applied to the thin graph G
′, we seek a more tractable representation of this LP. To achieve this, we consider the LP dual problem obtained by dualizing