Abstract
We address the problem of finding the most likely assignment, or Maximum A Posteriori (MAP) estimation, in a Markov Random Field (MRF). We analyze the linear programming formulation of MAP through the lens of Difference of Convex (DC) programming. By introducing a parameterized "hybrid bound" that selectively applies non-convex mean-field constraints to a subset of edges while maintaining standard LP constraints elsewhere, we develop a globally convergent message-passing algorithm. Our approach achieves optimal or near-optimal solutions on notoriously hard benchmarks in a fraction of the time required by exact solvers.
Introduction
Finding the MAP estimation in an MRF is a fundamental task in computer vision and computational biology. Since exact MAP estimation is NP-hard for general graphs, researchers typically rely on approximations. A standard approach is Linear Programming (LP) relaxation, which optimizes over the "local polytope"—an outer bound of the true marginal probabilities. However, this outer bound can be loose. Conversely, using a mean-field assumption provides an exact "inner bound," but introduces severe non-convexity, leading to local optima. This paper proposes a mathematical "sweet spot" between these two extremes.
Methods: The Hybrid Bound and DC Programming
The core innovation is a hybrid bound that selectively applies non-convex constraints to a specific subset of graph edges, termed QP edges. This allows for fine-grained control over the degree of non-convexity introduced into the problem. As shown in the geometric interpretation below, the hybrid set $\mathcal{H}(G; Q)$ provides a tighter approximation than the standard local polytope $\mathcal{L}(G)$.
We frame the MAP problem as a Difference of Convex (DC) functions program and solve it using the Concave-Convex Procedure (CCCP). This translates into an efficient, double-loop message-passing algorithm:
- Outer Loop: Computes gradients.
- Inner Loop: Solves a convex optimization problem using block coordinate ascent on its dual, utilizing the Lambert W-function for closed-form updates.
A key insight is that adding QP edges actually decreases the number of parameters by $O(k^2)$, potentially simplifying the optimization despite the non-convexity. Furthermore, we prove that for the pure LP relaxation (zero QP edges), every stationary point is a global optimum, ensuring CCCP avoids the local optima issues common in other dual-based solvers.
Experimental Results
We evaluated the algorithm (CCQP) on Binary Integer Quadratic (Biq) problems and 2D grid graphs. On hard Biq benchmarks, CCQP found the exact optimal solution for 26 out of 30 instances, whereas standard LP relaxations like MPLP failed to find good integral solutions.
In terms of speed, CCQP solved 250-node instances in approximately 650 seconds, compared to 4,500–316,000 seconds for exact solvers. On $50 \times 50$ grid graphs, the approach achieved within 97-98.5% of the optimal solution, significantly outperforming standard Max-Product and MPLP algorithms.
Conclusion
The DC programming framework offers a flexible and powerful way to tighten MAP estimation bounds. Future work includes developing adaptive schemes to dynamically select QP edges during optimization and incorporating additional constraints from the cut polytope to further improve accuracy without sacrificing the message-passing architecture.
Summary updated