Exponential Family Relaxation in Combinatorial Optimization

We face the problem of the optimization of a pseudo-Boolean function by introducing a stochastic relaxation based on the exponential family. The original discrete optimization problem is replaced by the optimization of the expected value of the pseudo-Boolean function w.r.t. some distribution in a parametric statistical model. We study the relation among the two problems, by providing results about stationary conditions and critical points. We prove that the presence of local minima depends on the relationship between the function to be optimized and the statistical model employed in the relaxation, and we discuss the results obtained with simple examples. Finally we show how the marginal polytope can give useful insights about the relation between a stochastic relaxation and local search techniques used in integer programming.