Why are shared variables copied?

Copies let the subproblems be optimized separately after agreement constraints are relaxed.

What does a zero primal - dual gap establish?

A valid labeling attaining a valid lower bound is globally optimal for the stated discrete objective.

Can a gap remain after dual convergence?

Yes. It can reflect a non-tight relaxation rather than incomplete dual optimization.

AI Glossary / Mathematics and optimization / Intermediate

MRF optimization via dual decomposition

Definition

MRF optimization via dual decomposition is a framework for minimizing a discrete Markov random field's energy by splitting it into easier subproblems and coordinating their overlapping variables through dual quantities. It produces lower bounds on the best possible energy while searching for a consistent labeling. Agreement between suitable subproblem solutions can provide an optimality certificate.

What it means

A Markov random field, or MRF, represents relationships among variables arranged on a graph. Unary costs express preferences for individual labels, while pairwise or higher-order costs express interactions. Finding a low-energy labeling can be difficult when the graph and costs create competing requirements.
Dual decomposition gives different subproblems their own copies of shared variables. It temporarily relaxes the requirement that those copies agree, then adjusts costs to encourage consistency. These cost adjustments redistribute the objective without changing the energy of a labeling on which all copies agree. The dual is a mathematical optimization problem, not a second independently trained AI model.

How it works

Choose tractable subgraphs or factors and allocate the original energy terms across them without double counting. Introduce agreement constraints between copies of shared variables. Relax those constraints using Lagrange multipliers, so each subproblem can be optimized separately for fixed multipliers.
The sum of the separate minimum values is a lower bound for the original minimization problem. Update the multipliers using disagreement information to improve that bound. Meanwhile, construct consistent candidate labelings and evaluate their original energy, providing upper bounds. A zero gap between a valid labeling's energy and the lower bound certifies optimality. A nonzero relaxation gap may remain even when the dual problem has been solved.

Three practical examples

An image-labeling model can divide a graph into tractable pieces while coordinating labels at shared pixels or regions.
A structured-prediction study can combine subproblems with different useful structures and track a bound on its MAP energy.
A numerical research team can compare inference methods using both the energy of returned labelings and the quality of their dual lower bounds.

Think of it this way

Think of several planning teams solving overlapping portions of a shared schedule. Temporary prices discourage incompatible choices, but the final schedule must agree on shared commitments. The analogy is limited: the multipliers are algebraic coordination variables, and a collection of independently good local plans is not automatically a valid global solution.

Worked example

Consider an original three-variable chain with binary labels a,b,c. Define its energy as E=2a+(1−c)+3|a−b|+3|b−c|. Split it into E_1(a,b)=2a+3|a−b| and E_2(b,c)=1−c+3|b−c|.
Give the two subproblems separate copies b_1 and b_2. Add λb_1 to the first energy and −λb_2 to the second. When the copies agree, the added terms cancel, leaving the original energy unchanged.
At λ=0, the first subproblem chooses (a,b_1)=(0,0) with value zero. The second chooses (b_2,c)=(1,1), also with value zero. Their summed minimum is zero, a valid lower bound, but their choices disagree on b and cannot be joined into one labeling.
For a fixed b_1=0, the first subproblem's minimum is zero; for b_1=1 it is 2+λ. For the second subproblem, b_2=0 gives minimum one, while b_2=1 gives minimum −λ. Therefore the dual bound is g(λ)=min{0,2+λ}+min{1,−λ}.
Choose λ=−1.5. The first subproblem compares zero with 0.5 and chooses b_1=0, a=0. The second compares one with 1.5 and chooses b_2=0, c=0. The copies now agree. Their minimum values sum to one, and the resulting original labeling (0,0,0) has energy one.
Every feasible labeling has energy at least the dual lower bound one, and this labeling attains it, so it is globally optimal. The all-one labeling has energy two and is worse. This small chain could be solved directly; its purpose is to make the lower-bound and agreement logic visible, not to demonstrate a computational speed advantage.

Illustrative case study

In a fictional vision-software project, a team evaluates an MRF solver on synthetic graphs with known answers. It reports the original energy of each consistent labeling together with the dual lower bound. If subproblem copies disagree, the team records that fact rather than displaying the incompatible collection as a completed image labeling. This is an illustrative validation process, not a reported benchmark or a claim that low energy guarantees correct interpretation of an image.

Common misconceptions and mistakes

The lower bound is not generally the energy of a valid global labeling. Relaxing agreement enlarges the set of combinations being considered, which explains why the bound can be lower than every feasible energy.
Solving the dual optimally also need not solve the original discrete problem exactly; the chosen relaxation can have a gap. Conversely, finding a consistent collection of exact subproblem minimizers at the same multipliers can certify a solution. Approximate subproblem solves require care because an arbitrary approximate minimum is not automatically a valid lower-bound contribution. Finally, naive multiplier steps can oscillate or worsen an iterate's bound even when a well-designed procedure converges.

Business use

For business applications using structured prediction, the framework offers useful diagnostics: a candidate solution, a lower bound, and an explicit gap. That helps distinguish an optimization limitation from an error in the underlying model. Review the graph, labels, and cost design alongside solver performance. A mathematically optimal labeling is optimal for the specified energy, which may still differ from the operational objective.

Check your understanding

Why is zero not an achieved feasible energy at λ=0 in the example?

Answer: The subproblem minima require b_1=0 and b_2=1. Those incompatible choices cannot represent one original variable b.

Related terms

Markov random field
Duality gap
Message passing
MAP inference
Energy minimization
Lagrangian relaxation
Linear-programming relaxation
Graphical model

Learn next

Evaluate g(λ) at λ=−3, −2, −1, and zero. Determine where the lower bound equals one and examine whether ties in subproblem solutions affect the ability to choose agreeing minimizers.

Sources

Primary source: Komodakis, Paragios, and Tziritas, Optimization of Discrete Markov Random Fields via Dual Decomposition, original research report: https://www.csd.uoc.gr/~komod/publications/docs/Dual_Decomposition_TR.pdf . The binary-chain calculation and certificate here are original.

Previous: Moving object detection Next: MS between groups (MS group )