SOL Logo

Systems Optimization Laboratory

Stanford University
Dept of Management Science and Engineering (MS&E)

Huang Engineering Center

Stanford, CA 94305-4121  USA

LNLQ: Sparse Equations and Least Squares

  • AUTHORS: Ron Estrin, Dominique Orban. Michael Saunders.
  • CONTENTS: Implementation of a conjugate-gradient type method for solving the least-norm problem \begin{align*} \text{minimize } & \|x\|^2 \text{ subject to } Ax = b, \end{align*} where the matrix \(A\) may be square or rectangular with any rank, and the constraints are assumed to be consistent. \(A\) is represented by a routine for computing \(Av\) and \(A^T u\) for given vectors \(v\) and \(u\).

    The method is based on the Golub-Kahan bidiagonalization process. It is algebraically equivalent to applying SYMMLQ to the normal equation of the second kind, \( AA^T y = b, \ x = A^T y, \) but has better numerical properties, especially if \(A\) is ill-conditioned.

    LNLQ reduces the error \(\|x - x_k\|\) monotonically.

    If \(A\) is symmetric, use SYMMLQ, MINRES, or MINRES-QLP.

    R. Estrin, D. Orban, and M. A. Saunders, LNLQ: An iterative method for linear least squares with an error minimization property, submitted to SIMAX (2019).
    2019: Matlab version.