On the asymptotic convergence of the simulated annealing algorithm in the presence of a parameter dependent penalization

We establish asymptotic convergence of the standard simulated annealing algorithm - when used with a parameter dependent penalization - to the set of globally optimal solutions of the original combinatorial optimization problem. Precise and explicit asymptotic estimates are given. Moreover, we present an explicit description of the asymptotic behaviour of the expected cost, the variance of the cost and the entropy. We show that familiar properties like monotonicity of the expected cost and the entropy are no longer guaranteed in the penalized case and discuss the practical consequences of our results.