  We consider the linear programming relaxation of an energy minimization
problem for Markov Random Fields. The dual objective of this problem can be
treated as a concave and unconstrained, but non-smooth function. The idea of
smoothing the objective prior to optimization was recently proposed in a series
of papers. Some of them suggested the idea to decrease the amount of smoothing
(so called temperature) while getting closer to the optimum. However, no
theoretical substantiation was provided. We propose an adaptive smoothing
diminishing algorithm based on the duality gap between relaxed primal and dual
objectives and demonstrate the efficiency of our approach with a smoothed
version of Sequential Tree-Reweighted Message Passing (TRW-S) algorithm. The
strategy is applicable to other algorithms as well, avoids adhoc tuning of the
smoothing during iterations, and provably guarantees convergence to the
optimum.
