From Glossary

Jump to: navigation, search

Small positive values to control elements of a computer implementation of an algorithm. When determining whether a value, LaTeX: v, is non-negative, the actual test is LaTeX: v > -t, where LaTeX: t is an absolute tolerance. When comparing two values to determine if LaTeX: u \le v, the actual test is

u - v \le t_a + t_r \left |v \right |,

where LaTeX: t_a is the absolute tolerance (as above), and LaTeX: t_r is the relative tolerance (some make the relative deviation depend on LaTeX: u as well as on LaTeX: v, such as the sum of magnitudes, LaTeX: \textstyle \left |u \right | + \left |v \right | ). Most MPSs have a tolerance for every action it takes during its progression; in particular, one zero tolerance is not enough - one to test feasibility is usually less than one that is used to determine an acceptable pivot element. In fact, the use of tolerances is a crucial part of an MPS, including any presolve that would fix a variable when its upper and lower bounds are "sufficiently close" (i.e., within some tolerance). A tolerance is dynamic if it can change during the algorithm. An example is that a high tolerance might be used for line search early in an algorithm, reducing it as the sequence gets close to an optimal solution. The Nelder-Mead simplex method illustrates how tolerances might change up and down during the algorithm.

Another typical tolerance test applies to residuals to determine if LaTeX: x is a solution to LaTeX: Ax=b. In this case, the residal is LaTeX: r=Ax-b, and the test has the form:

\left ||r \right || \le t_a + t_r \left ||b \right ||,

where LaTeX: \left ||* \right || is some norm. Further details are in the note on Tolerances.

Personal tools