Numerical stability of methods for solving augmented systems.(English)Zbl 0868.65025

Censor, Yair (ed.) et al., Recent developments in optimization theory and nonlinear analysis. AMS/IMU special session on optimization and nonlinear analysis, May 24–26, 1995, Jerusalem, Israel. Providence, RI: American Mathematical Society. Contemp. Math. 204, 51-60 (1997).
Summary: We consider questions of scaling and accuracy of methods for solving the two coupled symmetric linear systems $$Hy+Ax=b$$, $$A^Ty=c$$, where $$A\in\mathbb{R}^{m\times n}$$, $$m\geq n$$, and $$H\in \mathbb{R}^{m\times m}$$ is symmetric positive definite. Such systems, known in optimization as Karush-Kuhn-Tucker (KKT) systems, are symmetric indefinite and form the kernel in many optimization algorithms. An often used method for solving KKT systems is to compute an $$LDL^T$$ factorization of the system matrix, where $$L$$ is lower triangular and $$D$$ is block-diagonal with $$1\times 1$$ and symmetric $$2\times 2$$ pivots. The pivots are chosen according to a scheme by J. R. Bunch and L. Kaufman [Math. Comput. 31, 163-179 (1977; Zbl 0355.65023)].
For the standard case, when $$H=I$$, we review results from Å. Björck [Pitman Res. Notes Math. Ser. 260, 1-16 (1992; Zbl 0796.65056)] which show that for the above method to be numerically stable a scaling of the (1,1) block is needed. We give a closed expression for the optimal scaling factor, and show that for this scaling the errors in $$x$$ and $$y$$ are of the same size as from a norm-wise backward stable method. For the case when $$H=D^{-2}$$ is diagonal we recommend a diagonal scaling such that rows of $$A$$ are equilibrated before a block scaling is performed as in the standard case.
For sparse problems the scaling has to be a compromise between stability and sparsity, since the optimal scaling usually leads to unacceptable fill-in in the factorization. Accuracy of the computed solution can then usually be restored by fixed precision iterative refinement. A different scheme, due to C. C. Paige and M. A. Saunders [SIAM J. Numer. Anal. 12, 617-629 (1975; Zbl 0319.65025)], which uses SYMMLQ with a preconditioner derived from the $$LDL^T$$ factorization is also described.
For the entire collection see [Zbl 0861.00014].

MSC:

 65F35 Numerical computation of matrix norms, conditioning, scaling 65F50 Computational methods for sparse matrices 65F05 Direct numerical methods for linear systems and matrix inversion 65K05 Numerical mathematical programming methods 90C20 Quadratic programming