#### Lagrangian Relaxation for Intractable Graphical Models

*Jason K. Johnson, Dmitry M. Malioutov*

*Lagrangian relaxation* (LR) is an approximate method to
estimate the most probable configuration of an intractable MRF. LR is
formulated with respect to an augmented graphical model, which
includes replicas of the nodes and edges of the original graph. By
dualizing the constraint that replicated variables (and, more
generally, replicated features) must be equal in any valid assignment,
we obtain a relaxed, convex "dual" problem, which is tractable to
solve provided the augmented graph has a low tree width. In
particular, if the augmented graph is chosen to correspond to a set of
spanning trees of the original graph, then we recover essentially the
same formalism as in the tree-reweighted max-product approach
developed by Martin Wainwright. More generally, we allow relaxations
based on small sub-graphs, narrow sub-graphs, "unwound" computation
trees and multiscale representations. These extensions can lead to
reduced duality gaps and faster convergence in the iterative methods
used to solve the dual problem.