On the convergence of ``threshold accepting'' (Q1179163): Difference between revisions

``Threshold accepting'' (TA) was introduced by \textit{G. Dueck} and \textit{T. Scheuer} [J. Comput. Phys. 90, No. 1, 161-175 (1990; Zbl 0707.65039)] as a (new) local search method. In the context of combinatorial optimization, assume a cost function \(C\) which assigns a real number to each configuration. Let \(i\) be the current configuration at time \(k\) and let \(j\) be the selected neighbour. Then \(j\) becomes the next configuration in the sequence with probability 1 if \(C(j)- C(i)\leq T_ k\), with probability 0 if \(C(j)- C(i)> T_ k\) (minimization problem). Therein, the threshold sequence \((T_ k)\) consists of nonnegative real numbers and has been chosen nonincreasing by Dueck and Scheuer. In this paper some convergence results for TA are presented. The proofs do not tell anything about how to construct optimal (or even good) threshold sequences.