Iterative Optimizers

1Some Definitions

An important point is that one is supposed to work with a digital computer and that, consequently, every manipulated entity is discrete finite. In particular, the difference between two values cannot be less than a given threshold ε, commonly known as computer machine epsilon, even if, in fact, it also depends on the operating system and the language being used.

Most theoretical analyses, especially for convergences, require continuity or even differentiability properties. As a result, they are not valid in our discrete context. A convergence theorem may very simply not hold therein.

1.1. Continuous case vs discrete case: when a theorem no longer holds

A classical theorem is when, with the set of non-negative real numbers, the sequence x_n+1 = αx_n converges to zero for every α positive smaller than 1, and this holds independently of the initial number x₁.

However, on a computer, this is different. For simplicity, suppose a machine epsilon ε equal to 1. Then, αx_n is rounded to the nearest integer. If, for example, x₁ = 10, then the sequence stabilizes at 1 and does not converge to zero. The theorem no longer holds. More specifically, it must be modified: the convergence still exists, but to ε.

Figure 1.1. On a digital computer a sequence that theoretically converges to zero may in fact converge to a positive value wrongly said to be zero

Naturally, this is ...