# Systems Optimization Laboratory

## LNLQ: Sparse Equations and Least Squares

• AUTHORS: Ron Estrin, Dominique Orban. Michael Saunders.
• CONTRIBUTORS:
• 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.

• REFERENCES:
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).
• RELEASE:
2019: Matlab version.