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.