Multistart method with estimation scheme for global satisfycing problems

We present a multistart method for solving global satisfycing problems. The method uses data generated by linearly converging local algorithms to estimate the cost value at the local minimum to which the local search is converging. When the estimate indicates that the local search is converging to a value higher than the satisfycing value, the local search is interrupted and a new local search is initiated from a randomly generated point. When the satisfycing problem is difficult and the estimation scheme is fairly accurate, the new method is superior over a straightforward adaptation of classical multistart methods.