Stopping Conditions and Solvability

In any computer algorithm there must be some stopping condition, which after some finite number of computing steps stops the computation. The condition should of course relate to the quality of the solution achieved.

This is a very crucial point in global optimization. Without some additional information or assumptions about the problem there is no way to decide on the quality of the solution after a given number of steps (eg. number of function evaluations made).

A necessary condition for solving the problem is that at least one of the points x₁,...,x_N is in the region of attraction of the global minimum S(x). If no information about the size of S(x) (eg. lower bound) is known then of course there is no hope to formulate a proper stopping condition. It is of course not possible for the algorithm to decide on the proper stopping condition based on the function values f(x₁),...,f(x_N).

This means that either additional information or assumptions must be utilized for establishing a proper stopping condition or else the stopping condition is more or less heuristic.

From this we may conclude that the global optimization problem in general is unsolvable and that we must be prepared to accept non-global minima as solutions.