MS&E 318/CME 338: LargeScale 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 LargeScale 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., LargeScale Numerical Optimization,
SIAM, Philadelphia, 1990.
A. R. Conn, N. I. M. Gould and Ph. L. Toint, LANCELOT: a Fortran
Package for LargeScale Nonlinear Optimization (Release A), Springer
Verlag, Heidelberg, Berlin and New York, 1992.
W. W. Hager, D. W. Hearn and P. M. Pardalos, eds., LargeScale
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, PrimalDual InteriorPoint Methods,
SIAM, Philadelphia, 1997.
A. R. Conn, N. I. M. Gould and Ph. L. Toint, TrustRegion Methods,
SIAM, Philadelphia, 2000.
See extremely fine review of TrustRegion Methods: Natalia
Alexandrov, SIAM Review 45(1), 128131, 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.
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 SparsityInducing Penalties,
Foundations and Trends in Machine Learning 4(1), 1106 (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):123231, 2014.
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, 562589 (1984).
P. E. Gill, W. Murray, M. A. Saunders and M. H. Wright, Maintaining
LU factors of a general sparse matrix, LAA 88/89, 239270 (1987).
S. K. Eldersveld and M. A. Saunders, A blockLU update for
largescale linear programming, SIMAX 13, 191201 (1992).
P. E. Gill, W. Murray, D. B. PonceleĆ³n and M. A. Saunders,
Preconditioners for indefinite systems arising in optimization,
SIMAX 13, 292311 (1992).
M. A. Saunders, Solution of sparse rectangular systems using LSQR
and CRAIG, BIT 35, 588604 (1995).
P. E. Gill, M. A. Saunders and J. R. Shinnerl, On the stability of
Cholesky factorization for quasidefinite systems, SIMAX 17(1),
3546 (1996).
Sparse Matrix Methods (other authors)
J. K. Reid, A sparsityexploiting variant of the BartelsGolub
decomposition for linear programming bases, Math. Prog. 24, 5569,
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), 187226, 1996. (abstract)
A. Gupta, Recent advances in direct methods for solving unsymmetric
sparse systems of linear equations, ACM TOMS 28(3), 301324,
2002. (abstract)
L. Bergamaschi, J. Gondzio, and G. Zilli, Preconditioning indefinite
systems in interior point methods for optimization, Report
MS02002, 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), 118144,
2004. (Abstract, BibTex entry)
M. Benzi, G. H. Golub, and J. Liesen, Numerical solution of
saddlepoint problems, Acta Numerica 2005, Cambridge University
Press, 1137 (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), 779792 (2006).
(SIAM archive)
Ghussoun AlJeiroudi, Jacek Gondzio, and Julian Hall,
Preconditioning indefinite systems in interior point methods for
large scale linear optimisation, Optimization Methods and Software
23:3 (2008) 345363.
Optimization Methods (Saunders et al.)
B. A. Murtagh and M. A. Saunders, Largescale linearly constrained
optimization, Math. Prog. 14, 4172 (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), 84117 (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, 183209 (1986).
S. S. Chen, D. L. Donoho and M. A. Saunders, Atomic decomposition by
Basis Pursuit, SIAM Review 43(1), 129159 (2001).
(SIAM archive)
P. E. Gill, W. Murray and M. A. Saunders, SNOPT: An SQP algorithm
for largescale constrained optimization, SIAM Review 47(1), 99131,
2005. (SIAM
archive) (SIGEST Introduction)
Optimization Methods (other authors)
R. E. Bixby, Solving realworld linear programs: a decade and more
of progress, Operations Research 50(1), 315, 2002.
Jiming Peng, Cornelis Roos and Tamas Terlaky, SelfRegularity: A New
Paradigm for PrimalDual Interior Point Algorithms, Princeton
University Press, Princeton, NJ, 2002.
E. M. Gertz and S. J. Wright, Objectoriented software for quadratic
programming, ACM TOMS 29(1), 5881, 2003.
N. I. M. Gould, D. Orban and Ph. L. Toint, GALAHAD, a library of
threadsafe Fortran 90 packages for largescale nonlinear
optimization, ACM TOMS 29(4), 353372,
2003. (current
reports)
N. I. M. Gould, D. Orban and Ph. L. Toint, Numerical methods for
largescale nonlinear optimization, Acta Numerica 2005, Cambridge
University Press, 299361,
2005. (current
reports)
