Gradient-based optimization methods guarantees only local solutions when the cost function is non-convex. RL algorithms are local minimizers by nature. Given an RL iteration scheme and the data, two factors affect the solution: the initial assignment of labels and the compatibility function [Rosenfeld et al. 1976]. However, it is shown that for certain choices of compatibility function, an RL algorithm can have a single convergence point regardless of the initial assignment [Bozma and Duncan 1988,O'Leary and Peleg1983].
In some earlier RL works [Rosenfeld et al. 1976,Peleg and Rosenfeld 1978], the dependence of solutions on initializations is regarded as a desirable property. There, compatibility functions are defined without referring to the observations and therefore they should be considered as containing a priori information only. Constraints due to the observation are encoded in the initial assignment. Therefore, traditional RL solutions rely much on the initialization; convergence to a solution regardless of the initialization is considered undesirable. However, the posterior MRF energy already contains both sources of information, i.e. on the prior and the observation. Therefore the global energy minimum is the desirable solution [Geman and Geman 1984]. An ``annealing labeling'' algorithm, a GNC-like algorithm for the MAP-MRF matching will be described in Section 9.3.1.