Try our new documentation site (beta).
Next: The geometry of linear Up: Instability and the geometry Previous: Instability and the geometry
The case of linear systems:
Solving linear systems is a very common sub-routine in any MI(QC)P-solver, as we have to solve many linear systems during the full execution of the algorithm.
So, consider that we have a linear system 
with an
unique solution (i.e. 
is a square matrix with full rank), and you
want to evaluate how the solution to the system might change if we
perturb the right-hand side 
. Since the system has a unique
solution, we know that given , the solution will be 
, and
if we perturb with 
, the solution will be
. A measure for the relative change in
the solution with respect to the relative change in the input
would be the ratio
Note that the above definition is independent of the magnitudes of
and .
From there, the worst possible ratio would be the result of
This quantity is known as the condition number of the matrix
. It is not hard to prove that
where
and
are the maximum and
minimum, respectively, eigenvalues of . Equivalently
A common interpretation of
is that, when solving the
system , you may lose up to 
digits of accuracy in 
from
the accuracy you have in .
The condition number for the optimal simplex basis in
an LP is captured in the
KappaExact attribute.
A very large 
value might be an indication that
the result might be unstable.
When this is indeed the case, the best advice is to scale the
constraint matrix coefficients so that the resulting range of
coefficients is small.
This transformation will typically reduce the
value of the final basis; please refer to the
Scaling section for a discussion on how to
perform this rescaling, and also for caveats on scaling in general.
Next: The geometry of linear Up: Instability and the geometry Previous: Instability and the geometry
