# Systems Optimization Laboratory

## Freely Available Optimization Software

The following software packages are provided by SOL under the terms of The MIT License (MIT). The software may alternatively be used under the terms of a BSD License (BSDlicense.txt).

• SYMMLQ: Fortran, MATLAB, and Python software for sparse symmetric linear equations $$Ax = b$$, where $$A$$ is definite or indefinite. (Iterative method. Allows a positive-definite preconditioner.)

• MINRES: Fortran, MATLAB, and Python software for sparse symmetric linear equations $$Ax = b$$, where $$A$$ is definite or indefinite, possibly singular. (Iterative method. Allows a positive-definite preconditioner.)

• MINRES-QLP: MATLAB software for sparse symmetric linear equations $$Ax = b$$ or least-squares problems $$\min \|Ax - b\|$$, where $$A$$ is definite or indefinite, possibly singular. (Iterative method. Allows a positive-definite preconditioner. For singular systems, computes the minimum-norm solution.)

• cgLanczos: MATLAB software for sparse symmetric positive-definite linear equations $$Ax = b$$. (Iterative method; Lanczos-based implementation of CG, the conjugate-gradient method.) Special feature: Returns an estimate of the diagonals of $$A^{-1}$$.

• LSQR: MATLAB, Fortran, C, C++, .NET, and Python software for sparse linear equations and sparse least squares. (Iterative method; more stable than symmetric conjugate-gradient method on normal equations. Allows positive "damping".) Special feature: Returns an estimate of the diagonals of $$(A^T A)^{-1}$$.

• LSMR: MATLAB, Python, and Fortran 90 software for sparse linear equations and sparse least squares. (Iterative method; more stable than MINRES on normal equations. Allows positive "damping".) Special feature: Both $$\|r\|$$ and $$\|A^T r\|$$ decrease monotonically. For LSQR, only $$\|r\|$$ is monotonic.

• CGLS: MATLAB software for sparse linear equations and sparse least squares. (Iterative method; more stable than symmetric conjugate-gradient method on normal equations.) Special feature: Allows positive or negative "damping" (although negative is potentially unstable).

• CRAIG: MATLAB software for under-determined sparse linear equations $$Ax=b$$. Returns the minimum-length solution.

• covLSQR: MATLAB software for sparse linear equations and sparse least squares, derived from LSQR. Special feature: Can estimate any principal submatrix of the covariance matrix $$(A^T A)^{-1}$$.

• LSRN: Python and C++ (with MATLAB interface) software for strongly over-determined or under-determined, possibly rank-deficient, linear least squares.

• LUSOL: Fortran and MATLAB software for maintaining a sparse square or rectangular factorization $$A = LU$$. (Suitable as a basis factorization package for sparse simplex method.)

• lusolZ: MATLAB software for computing a nullspace operator $$Z$$ of the transpose of a sparse matrix $$S$$ (so that $$S^T Z = 0$$) using sparse QR factors of either $$S$$ or $$S^T$$ computed by SuiteSparseQR, or sparse LU factors of either $$S$$ or $$S^T$$ computed by LUSOL. MATLAB routines {spqrZ, spqrZv, spqrZt} and {lusolZ, lusolZv, lusolZt} are provided to factorize $$S$$ or $$S^T$$ and to compute products of the form $$w = Zv$$ and $$s = Z^T t$$ for given vectors $$v$$ and $$t$$.

• LUMOD: Fortran software for updating a dense square factorization $$LC = U$$ when rows and columns of $$C$$ are added, deleted or replaced. (Suitable as basis factorization package for dense simplex method, or for updating sparse factorizations via the Schur-complement (Block-LU) method.)

• ASP: MATLAB software implementing an active-set method for sparse optimization: minimize $$\lambda \|x\|_1 + \frac12 \|Ax-b\|_2^2$$. This includes basis pursuit (BP), basis pursuit denoising (BPDN), and NNLS (non-negative least squares). For certain matching values of $$\lambda$$ and $$\tau$$, BPDN is equivalent to the Lasso problem: minimize $$\frac12 \|Ax-b\|_2^2$$ subject to $$\|x\|_1 \le \tau$$. Special feature: $$A$$ may be a dense or sparse matrix or a function for computing $$Ax$$ and $$A^Ty$$.

• PDCO: MATLAB software implementing a primal-dual interior method for sparse linear programming, least squares, or convex optimization subject to linear constraints $$Ax=b$$, $$l \le x \le u$$. This includes NNLS (non-negative least squares). Special feature: $$A$$ may be a dense or sparse matrix or a function for computing $$Ax$$ and $$A^Ty$$.

• PDSCO: Superseded by PDCO.

• PNOPT: MATLAB solver that uses proximal Newton-type methods to minimize composite functions (the sum of a smooth and a nonsmooth function).

• qdotdd: Fortran 90 quad-precision dotproduct of double-precision vectors.