 # Tolerances

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 $LaTeX: 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: $LaTeX: \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.