  Dual decomposition approaches in nonconvex optimization may suffer from a
duality gap. This poses a challenge when applying them directly to nonconvex
problems such as MAP-inference in a Markov random field (MRF) with continuous
state spaces. To eliminate such gaps, this paper considers a reformulation of
the original nonconvex task in the space of measures. This infinite-dimensional
reformulation is then approximated by a semi-infinite one, which is obtained
via a piecewise polynomial discretization in the dual. We provide a geometric
intuition behind the primal problem induced by the dual discretization and draw
connections to optimization over moment spaces. In contrast to existing
discretizations which suffer from a grid bias, we show that a piecewise
polynomial discretization better preserves the continuous nature of our
problem. Invoking results from optimal transport theory and convex algebraic
geometry we reduce the semi-infinite program to a finite one and provide a
practical implementation based on semidefinite programming. We show,
experimentally and in theory, that the approach successfully reduces the
duality gap. To showcase the scalability of our approach, we apply it to the
stereo matching problem between two images.
