Open Collections

Incomplete factorization preconditioners for least squares and linear and quadratic programming

University of British Columbia

Many algorithms for optimization are based on solving a sequence of symmetric indefinite linear systems. These systems are often large and sparse, and the main approaches to solving them are based on direct factorization or iterative Krylovbased methods. In this thesis, we explore how incomplete sparse factorizations can be used as preconditioners for the special case of quasi-definite linear systems that arise in regularized linear and quadratic programming, and the case of least-squares reformulations of these systems. We describe two types of incomplete factorizations for use as preconditioners. The first is based on an incomplete Cholesky-like factorization. The second is based on an incomplete Householder QR factorization. Our approximate factorizations allow the user to prescribe the amount of fill-in, and therefore have predictable storage requirements. We use these incomplete factorizations as preconditioners for SYMMLQ and LSQR, respectively, and present numerical results for matrices that arise within an interior-point context.

Text

2011-03-04

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

http://hdl.handle.net/2429/32071

Computer Science

University of British Columbia

Graduate