ON A THE STABILITY OF NULL-SPACE METHODS FOR KKT SYSTEMS

This paper considers the numerical stability of null-space methods for Karush-Kuhn-Tucker (KKT) systems, particularly in the context of quad ratic programming. The methods we consider are based on the direct eli mination of variables, which is attractive for solving large sparse sy stems. Ill-conditioning in a certain submatrix A in the system is show n to adversely affect the method insofar as it is commonly implemented . In particular, it can cause growth in the residual error of the solu tion, which would not normally occur if Gaussian elimination or relate d methods were used. The mechanism of this error growth is studied and is not due to growth in the null-space basis matrix Z, as might have been expected, but to the indeterminacy of this matrix. When LU factor s of A are available it is shown that an alternative form of the metho d is available which avoids this residual error growth. These conclusi ons are supported by error analysis and Matlab experiments on same ext remely ill-conditioned test problems. These indicate that the alternat ive method is very robust in regard to residual error growth and is un likely to be significantly inferior to the methods based on an orthogo nal basis matrix. The paper concludes with some discussion of what nee ds to be done when LU factors are not available.