Posterior Agreement for Large Parameter-Rich Optimization ProblemsPosterior Agreement for Large Parameter-Rich Optimization Problems • June 7th, 2018
Most real world combinatorial optimization problems are affected by noise in the input data, thus behaving in the high noise limit like large disordered par- ticle systems, e.g. spin glasses or random networks. Due to uncertainty in the input, optimization of such disordered instances should infer stable pos- terior distributions of solutions conditioned on the noisy input instance. The maximum entropy principle states that the most stable distribution given the noise influence is defined by the Gibbs distribution and it is characterized by the free energy. In this paper, we first provide rigorous asymptotics of the dif- ficult problem to compute the free energy for two combinatorial optimization problems, namely the sparse Minimum Bisection Problem (sMBP) and Lawler’s Quadratic Assignment Problem (LQAP). We prove that both problems exhibit phase transitions equivalent to the discontinuous behavior of Derrida’s Random Energy Model (REM). Furthermore, the derived free energy asymptotics
