MS&E  318  (CME 338)   Spring 2008

Large-Scale Numerical Optimization

Home

Contact

References

Notes

Homework

 


REFERENCES

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

  • I. S. Duff, A. M. Erisman, and J. K. Reid. Direct Methods for Sparse Matrices, Oxford University Press, New York and Oxford, 1986.
  • 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.
  • J. Nocedal and S. J. Wright, Numerical Optimization, Second Edition, Springer Verlag, New York, 2006.
  • 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. (pdf)
  • 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.
  • T. A. Davis, Direct Methods for Sparse Linear Systems, SIAM, Philadelphia, 2006.

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). (pdf)
  • 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. (pdf)
  • M. Jacobsen, P. C. Hansen and M. A. Saunders, Subspace preconditioned LSQR for discrete ill-posed problems, BIT 43, 975-989 (2003). (pdf)

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). (pdf)

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). (pdf)
  • 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. (SIAM archive)

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)