Documentation

Filter Content By
Version
Text Search
${sidebar_list_label} - Back
Languages
${item.name}
next up previous
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 <span>$</span>A x = b<span>$</span> with an unique solution (i.e. <span>$</span>A<span>$</span> 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 <span>$</span>b<span>$</span>. Since the system has a unique solution, we know that given <span>$</span>b<span>$</span>, the solution will be <span>$</span>A^{-1}b<span>$</span>, and if we perturb <span>$</span>b<span>$</span> with <span>$</span>\varepsilon<span>$</span>, the solution will be <span>$</span>A^{-1}(b+\varepsilon)<span>$</span>. A measure for the relative change in the solution with respect to the relative change in the input would be the ratio

<span>$</span>\eta(b,\varepsilon):=\frac{\Vert A^{-1}b\Vert}{\Vert A^{-1}(b+\varepsilon)\Vert}/\frac{\Vert b\Vert}{\Vert b+\varepsilon\Vert}.<span>$</span>
Note that the above definition is independent of the magnitudes of <span>$</span>b<span>$</span> and <span>$</span>\varepsilon<span>$</span>. From there, the worst possible ratio would be the result of
<span>$</span>\kappa(A):=\max_{b,\varepsilon}\eta(b,\varepsilon).<span>$</span>
This quantity is known as the condition number of the matrix <span>$</span>A<span>$</span>. It is not hard to prove that
<span>$</span>\kappa(A)=\frac{\lambda_{\max}}{\lambda_{\min}},<span>$</span>
where <span>$</span>\lambda_{\max}<span>$</span> and <span>$</span>\lambda_{\min}<span>$</span> are the maximum and minimum, respectively, eigenvalues of <span>$</span>A<span>$</span>. Equivalently
<span>$</span>\kappa(A)={\Vert A\Vert}{\Vert A^{-1}\Vert}.<span>$</span>
A common interpretation of <span>$</span>\kappa(A)=10^k<span>$</span> is that, when solving the system <span>$</span>A x = b<span>$</span>, you may lose up to <span>$</span>k<span>$</span> digits of accuracy in <span>$</span>x<span>$</span> from the accuracy you have in <span>$</span>b<span>$</span>.

The condition number for the optimal simplex basis in an LP is captured in the KappaExact attribute. A very large <span>$</span>\kappa<span>$</span> 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 <span>$</span>\kappa<span>$</span> 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 up previous
Next: The geometry of linear Up: Instability and the geometry Previous: Instability and the geometry