Simulated annealing

Simulated annealing is a probabilistic optimization algorithm which is used for approximating the global extremes of a function at a large state space. We construct a homogeneous Markov chain, whose stationary distribution is depen- dent on the temperature parameter (this distribution is called the Boltzmann distribution), on this space. With declining the parameter this distribution fo- cuses on the states minimizing the function. The algorithm, on which it can be viewed as a non-homogeneous Markov chain, we use to solve the hard-core model and the graph bisection. We will also deal with the convergence of the algorithm, too rapidly decreasing sequence of the parameters can result in stucking in a lo- cal extreme of the function, therefore some requirements on this sequence will be determined.