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.

  • 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.)

  • 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).

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)

  • 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)

  • 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.

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

  • 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)

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)