CME 338: Large-Scale Numerical Optimization

SOL Software

Some software for linear equations, least squares, and constrained optimization is described here: SOL software

MATLAB Overview

The main matrix factorization (LU, QR, SVD) and many other important features of MATLAB are summarized here: MATLAB Guide, Second Edition by Desmond J. Higham and Nicholas J. Higham, SIAM, 2005.

Texts on Sparse Matrices and Large-Scale Optimization

• T. F. Coleman and Y. Li, eds., Large-Scale Numerical Optimization, SIAM, Philadelphia, 1990.

• A. R. Conn, N. I. M. Gould and Ph. L. Toint, LANCELOT: a Fortran Package for Large-Scale Nonlinear Optimization (Release A), Springer Verlag, Heidelberg, Berlin and New York, 1992.

• W. W. Hager, D. W. Hearn and P. M. Pardalos, eds., Large-Scale Optimization: State of the Art, Kluwer, Dordrecht, 1994.

• G. H. Golub and C. F. Van Loan, Matrix Computations, Third edition, The Johns Hopkins University Press, Baltimore, 1996.

• L. N. Trefethen and D. Bau, III, Numerical Linear Algebra, SIAM, Philadelphia, 1997.

• S. J. Wright, Primal-Dual Interior-Point Methods, SIAM, Philadelphia, 1997.

• A. R. Conn, N. I. M. Gould and Ph. L. Toint, Trust-Region Methods, SIAM, Philadelphia, 2000.

• See extremely fine review of Trust-Region Methods: Natalia Alexandrov, SIAM Review 45(1), 128-131, 2003.

• R. J. Vanderbei, Linear Programming: Foundations and Extensions, Second edition, Kluwer, Dordrecht, 2001.

• Y. Saad, Iterative Methods for Sparse Linear Systems, Second edition, SIAM, Philadelphia, 2003.

• H. A. van der Vorst, Iterative Krylov Methods for Large Linear Systems, Cambridge University Press, 2003.

• Y. Nesterov, Introductory Lectures on Convex Optimization. Vol. 87. Springer Science & Business Media, 2004.

• T. A. Davis, Direct Methods for Sparse Linear Systems, SIAM, Philadelphia, 2006.

• J. Nocedal and S. J. Wright, Numerical Optimization, Second Edition, Springer Verlag, New York, 2006.

• F. Bach and R. Jenatton and J. Mairal and G. Obozinski, Optimization with Sparsity-Inducing Penalties, Foundations and Trends in Machine Learning 4(1), 1-106 (2011), DOI: 10.1561/2200000015.

• E. G. Birgin and J. M. Martinez, Practical Augmented Lagrangian Methods for Constrained Optimization, SIAM, Philadelphia, 2014.

• N. Parikh, S. P. Boyd, Proximal Algorithms, Foundations and Trends in Machine Learning (3):123-231, 2014.

• I. S. Duff, A. M. Erisman, and J. K. Reid. Direct Methods for Sparse Matrices, second edition, Oxford University Press, 2017.

Sparse Matrix Methods (Saunders et al.)

• C. C. Paige and M. A. Saunders, Solution of sparse indefinite systems of linear equations, SIAM J. Num. Anal. 12, 617-629 (1975).

• C. C. Paige and M. A. Saunders, LSQR: An algorithm for sparse linear equations and sparse least squares, ACM TOMS 8(1), 43-71 (1982).

• C. C. Paige and M. A. Saunders, Algorithm 583; LSQR: Sparse linear equations and least-squares problems, ACM TOMS 8(2), 195-209 (1982).

• P. E. Gill, W. Murray, M. A. Saunders and M. H. Wright, Sparse matrix methods in optimization, SISSC 5, 562-589 (1984).

• P. E. Gill, W. Murray, M. A. Saunders and M. H. Wright, Maintaining LU factors of a general sparse matrix, LAA 88/89, 239-270 (1987).

• S. K. Eldersveld and M. A. Saunders, A block-LU update for large-scale linear programming, SIMAX 13, 191-201 (1992).

• P. E. Gill, W. Murray, D. B. Ponceleón and M. A. Saunders, Preconditioners for indefinite systems arising in optimization, SIMAX 13, 292-311 (1992).

• M. A. Saunders, Solution of sparse rectangular systems using LSQR and CRAIG, BIT 35, 588-604 (1995).

• P. E. Gill, M. A. Saunders and J. R. Shinnerl, On the stability of Cholesky factorization for quasi-definite systems, SIMAX 17(1), 35-46 (1996).

• M. A. Saunders, Cholesky-based methods for sparse least squares: The benefits of regularization, In L. Adams and J. L. Nazareth (eds.), Linear and Nonlinear Conjugate Gradient-Related Methods, SIAM, Philadelphia, 92-100 (1996).

• A. George and M. A. Saunders, Solution of sparse linear equations using Cholesky factors of augmented systems, Report SOL 99-1, Dept of EESOR, Stanford University (1999), 9 pages. Revised Oct 26, 2000 (draft), 12 pages.

• M. Jacobsen, P. C. Hansen and M. A. Saunders, Subspace preconditioned LSQR for discrete ill-posed problems, BIT 43, 975-989 (2003).

• S.-C. Choi, C. C. Paige and M. A. Saunders, LSMR: An iterative algorithm for sparse least-squares problems, SIAM J. Sci. Comput. 33:5, 2950-2971, published electronically Aug 4, 2011.

• D. C.-L. Fong and M. A. Saunders, LSMR: An iterative algorithm for sparse least-squares problems, SIAM J. Sci. Comput. 33:5, 2950-2971, published electronically Oct 27, 2011.

• D. C.-L. Fong and M. A. Saunders, CG versus MINRES: An empirical comparison, SQU Journal for Science 17:1, 44-62 (2012).

• D. Ma, L. Yang, R. M. T. Fleming, I. Thiele, B. O. Palsson and M. A. Saunders, Reliable and efficient solution of genome-scale models of Metabolism and macromolecular Expression, Sci. Rep. 7, Article number: 40863 (2017); doi:10.1038/srep40863.

Sparse Matrix Methods (other authors)

• J. K. Reid, A sparsity-exploiting variant of the Bartels-Golub decomposition for linear programming bases, Math. Prog. 24, 55-69, 1982. (Original code LA05 revised as LA15 in HSL 2002.)

• I. S. Duff and J. K. Reid, The design of MA48: a code for the direct solution of sparse unsymmetric linear systems of equations, ACM TOMS 22(2), 187-226, 1996. (abstract)

• A. Gupta, Recent advances in direct methods for solving unsymmetric sparse systems of linear equations, ACM TOMS 28(3), 301-324, 2002. (abstract)

• L. Bergamaschi, J. Gondzio, and G. Zilli, Preconditioning indefinite systems in interior point methods for optimization, Report MS-02-002, Dept of Mathematics and Statistics, The University of Edinburgh, July 26, 2002, revised March 18, 2003. (PS file)

• I. S. Duff, MA57 - A new code for the solution of sparse symmetric definite and indefinite systems, ACM TOMS 30(2), 118-144, 2004. (Abstract, BibTex entry)

• T. Davis, UMFPACK.

• M. Benzi, G. H. Golub, and J. Liesen, Numerical solution of saddle-point problems, Acta Numerica 2005, Cambridge University Press, 1-137 (2005).

• G. H. Golub, C. Greif, and J. M. Varah, An algebraic analysis of a block diagonal preconditioner for saddle point systems, SIAM J. Matrix Analysis and Applics. 27(3), 779-792 (2006). (SIAM archive)

• S.-C. Choi, Iterative Methods for Singular Linear Equations and Least-Squares Problems, PhD thesis, ICME, Stanford University (2006).

• H. M. Huynh, A Large-scale Quadratic Programming Solver Based on Block-LU Updates of the KKT System, PhD thesis, ICME, Stanford University (2008).

• Ghussoun Al-Jeiroudi, Jacek Gondzio, and Julian Hall, Preconditioning indefinite systems in interior point methods for large scale linear optimisation, Optimization Methods and Software 23:3 (2008) 345-363.

• C. M. Maes, A Regularized Active-set Method for Sparse Convex Quadratic Programming, PhD thesis, Stanford University (2010).

• D. C.-L. Fong, Minimum-Residual Methods for Sparse Least-Squares Using Golub-Kahan Bidiagonalization, PhD thesis, Stanford University (2011).

Optimization Methods (Saunders et al.)

• B. A. Murtagh and M. A. Saunders, Large-scale linearly constrained optimization, Math. Prog. 14, 41-72 (1978).

• B. A. Murtagh and M. A. Saunders, A projected Lagrangian algorithm and its implementation for sparse nonlinear constraints, Math. Prog. Study 16 (Constrained Optimization), 84-117 (1982).

• P. E. Gill, W. Murray, M. A. Saunders, J. A. Tomlin and M. H. Wright, On projected Newton barrier methods for linear programming and an equivalence to Karmarkar's projective method, Math. Prog. 36, 183-209 (1986).

• M. A. Saunders, Major Cholesky would feel proud, ORSA J. on Computing 6, 23-27 (1994).

• M. A. Saunders and J. A. Tomlin, Solving regularized linear programs using barrier methods and KKT systems, Report SOL 96-4, Dept of EESOR, Stanford University (1996).

• S. S. Chen, D. L. Donoho and M. A. Saunders, Atomic decomposition by Basis Pursuit, SIAM Review 43(1), 129-159 (2001). (SIAM archive)

• P. E. Gill, W. Murray and M. A. Saunders, SNOPT: An SQP algorithm for large-scale constrained optimization, SIAM Review 47(1), 99-131, 2005. (SIAM archive) (SIGEST Introduction)

• M. P. Friedlander and M. A. Saunders, A globally convergent LCL method for nonlinear optimization, SIAM J. Optim. 15(3), 863-897 (2005).

• R. Tibshirani, M. A. Saunders, S. Rosset, J. Zhu, and K. Knight. Sparsity and smoothness via the fused lasso, J. Royal Statistical Society B 67(1), 91-108 (2005).

• M. W. Carter, H. H. Jin, M. A. Saunders, and Y. Ye. SpaseLoc: An adaptive subproblem algorithm for scalable wireless sensor network localization, SIAM J. on Optimization 17(4), 1102-1128 (2006).

• S.-C. T. Choi, C. C. Paige and M. A. Saunders. MINRES-QLP: A Krylov subspace method for indefinite or singular symmetric systems, SIAM J. Sci. Comput. 33:4, 1810-1836 (2011).

• D. C.-L. Fong and M. A. Saunders. LSMR: An iterative algorithm for sparse least-squares problems, SIAM J. Sci. Comput. 33:5, 2950-2971 (2011).

• D. C.-L. Fong and M. A. Saunders. CG versus MINRES: An empirical comparison, SQU Journal for Science 17:1, 44-62 (2012).

Optimization Methods (other authors)

• R. E. Bixby, Solving real-world linear programs: a decade and more of progress, Operations Research 50(1), 3-15, 2002.

• Jiming Peng, Cornelis Roos and Tamas Terlaky, Self-Regularity: A New Paradigm for Primal-Dual Interior Point Algorithms, Princeton University Press, Princeton, NJ, 2002.

• E. M. Gertz and S. J. Wright, Object-oriented software for quadratic programming, ACM TOMS 29(1), 58-81, 2003.

• N. I. M. Gould, D. Orban and Ph. L. Toint, GALAHAD, a library of thread-safe Fortran 90 packages for large-scale nonlinear optimization, ACM TOMS 29(4), 353-372, 2003. (current reports)

• SIAG/OPT View-and-News, 14(1), April 2003. Special issue on Large Scale Nonconvex Optimization. (View on-line)

• N. I. M. Gould, D. Orban and Ph. L. Toint, Numerical methods for large-scale nonlinear optimization, Acta Numerica 2005, Cambridge University Press, 299-361, 2005. (current reports)

• Michael Friedlander's homepage refers to some excellent papers and software.

• Dominique Orban's homepage refers to more excellent papers and software.

• Stephen Becker's software.