Stopping Conditions and Solvability

One way to establish a stopping condition is to use the necessary condition, that at least one point in the region of attraction S(x^*) is obtained. Because the size of this is normally not known we could make an assumption about the minimum size of this (about our ambition in the solution effort), say that it is at least p, the size of A being 1.

Then if sampling a point at random (uniform sampling) in A, the probability that this point falls in S(x^*) is at least p. Sampling k points at random the probability that no point falls in S(x^*) is then at most

   (1-p)k

and the probability to obtain at least one point in S(x^*) is at least

   q = 1 - (1-p)k

Solving for k we obtain

  k = log(1-q)/(1-p)

For example, q= 0.95 and p= 0.001 means that we need to sample 2995 points at random in A.

However, not all methods use uniform sampling as global strategy, and for those which don't, using such kind of stopping condition is not normally possible.