×

Symbiosis between linear algebra and optimization. (English) Zbl 0964.65069

Author’s abstract: The efficiency and effectiveness of most optimization algorithms hinges on the numerical linear algebra algorithms that they utilize. Effective linear algebra is crucial to their success, and because of this, optimization applications have motivated fundamental advances in numerical linear algebra. This essay will highlight contributions of numerical linear algebra to optimization, as well as some optimization problems encountered within linear algebra that contribute to a symbiotic relationship.

MSC:

65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
65F20 Numerical solutions to overdetermined systems, pseudoinverses
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andersen, E. D.; Gondzio, J.; Mészáros, C.; Xu, X., Implementation of interior point methods for large scale linear programs, (Terlaky, T., Interior Point Methods of Mathematical Programming (1996), Kluwer Academic Publishers: Kluwer Academic Publishers Boston), 189-252 · Zbl 0874.90127
[2] Anderson, E.; Bai, Z.; Bischof, C.; Blackford, L. S.; Demmel, J.; Dongarra, J.; Du Croz, J.; Greenbaum, A.; Hammarling, S.; McKenney, A.; Sorensen, D., LAPACK Users’ Guide (2000), SIAM: SIAM Philadelphia
[3] Andersen, K. D., A modified Schur-complement method for handling dense columns in interior point methods for linear programming, ACM Trans. Math. Software, 22, 348-356 (1996) · Zbl 0884.65049
[4] Arioli, M.; Demmel, J. W.; Duff, I. S., Solving sparse linear systems with sparse backward error, SIAM J. Matrix Anal. Appl., 10, 165-190 (1989) · Zbl 0684.65022
[5] Bartels, R. H., A stablization of the simplex method, Numer. Math., 16, 414-434 (1971) · Zbl 0197.43305
[6] Bartels, R. H.; Golub, G. H., The Simplex method of linear programming using LU decomposition, Comm. ACM, 12, 266-268 (1969) · Zbl 0181.19104
[7] Bischof, C.; Bouaricha, A.; Khademi, P.; Moré, J., Computing gradients in large-scale optimization using automatic differentiation, INFORMS J. Comput., 9, 185-194 (1997) · Zbl 0885.90100
[12] Boggs, P. T.; Tolle, J. W., Sequential quadratic programming, Acta Numerica, 4, 1-51 (1995) · Zbl 0828.65060
[13] Bunch, J. R.; Kaufman, L.; Parlett, B. N., Decomposition of a symmetric matrix, Numer. Math., 27, 95-109 (1976) · Zbl 0342.65026
[14] Bunch, J. R.; Parlett, B. N., Direct methods for solving symmetric indefinite systems of linear equations, SIAM J. Numer. Anal., 8, 639-655 (1971) · Zbl 0199.49802
[15] Burges, C. J.C., A tutorial on support vector machines for pattern recognition, Data Mining Knowledge Discovery, 2, 121-167 (1998)
[16] Carpenter, T. J.; Shanno, D. F., An interior point method for quadratic programs based on conjugate projected gradients, Comput. Optim. Appl., 2, 5-28 (1993) · Zbl 0778.90048
[17] Censor, Y., Row-action methods for huge and sparse systems and their applications, SIAM Rev., 23, 444-466 (1981) · Zbl 0469.65037
[18] Chandrasekaran, S.; Ipsen, I. C.F., On rank-revealing factorisations, SIAM J. Matrix Anal. Appl., 15, 592-622 (1994) · Zbl 0796.65030
[20] Chui, C. K., An Introduction to Wavelets (1992), Academic Press: Academic Press New York · Zbl 0925.42016
[21] Conn, A. R.; Gould, N. I.M.; Toint, P. L., Methods for nonlinear constraints in optimization calculations, (Duff, I. S.; Watson, G. A., The State of the Art in Numerical Analysis (1997), Clarendon Press: Clarendon Press Oxford, England), 363-390 · Zbl 0881.65056
[22] Cottle, R. W.; Pang, J.-S.; Stone, R. E., The Linear Complementarity Problem (1992), Academic Press: Academic Press New York · Zbl 0757.90078
[23] Cox, M. G., The least squares solution of overdetermined linear equations having band or augmented band structure, IMA J. Numer. Anal., 1, 3-22 (1981) · Zbl 0469.65020
[24] Cybenko, G., Fast Toeplitz orthogonalization using inner products, SIAM J. Sci. Statist. Comput., 8, 734-740 (1987) · Zbl 0689.65022
[25] Dantzig, G. B., Linear Programming and Extensions (1963), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0108.33103
[26] Dembo, R. S.; Eisenstat, S. C.; Steihaug, T., Inexact Newton methods, SIAM J. Numer. Anal., 19, 400-408 (1982) · Zbl 0478.65030
[27] Demeure, C. J., Fast QR factorization of Vandermonde matrices, Linear Algebra Appl., 122, 3/4, 165-194 (1989) · Zbl 0687.65025
[28] Dennis, J. E.; Morè, J. J., Quasi-Newton methods, motivation and theory, SIAM Rev., 19, 46-89 (1977) · Zbl 0356.65041
[29] Duff, I. S.; Erisman, A. M.; Reid, J. K., Direct Methods for Sparse Matrices (1986), Clarendon Press: Clarendon Press Oxford · Zbl 0604.65011
[30] Ellacott, S. W., Aspects of the numerical analysis of neural networks, Acta Numer., 3, 145-202 (1994) · Zbl 0807.65007
[32] Fiacco (Ed.), A. V., Mathematical Programming with Data Perturbations (1998), Marcel Dekker: Marcel Dekker New York
[33] Fletcher, R., Practical Methods of Optimization (1987), Wiley: Wiley New York · Zbl 0905.65002
[34] Fletcher, R.; Reeves, C. M., Function minimization by conjugate gradients, Comput. J., 7, 149-154 (1964) · Zbl 0132.11701
[35] Forsgren, A.; Gill, P. E.; Shinnerl, J. R., Stability of symmetric ill-conditioned systems arising in interior methods for constrained optimization, SIAM J. Matrix Anal. Appl., 17, 187-211 (1996) · Zbl 0878.49021
[37] Gill, P. E.; Murray, W.; Wright, M. H., Practical Optimization (1981.), Academic Press: Academic Press New York
[40] George, J. A.; Liu, J. W.-H., Computer Solution of Large Sparse Positive Definite Systems (1981), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0516.65010
[41] Golub, G., Numerical methods for solving least squares problems, Numer. Math., 7, 206-216 (1965) · Zbl 0142.11502
[42] Golub, G. H.; Van Loan, C. F., Matrix Computations (1996), Johns Hopkins University Press: Johns Hopkins University Press Baltimore, MD · Zbl 0865.65009
[43] Gonzaga, C. C., Path-following methods for linear programming, SIAM Rev., 34, 167-224 (1992) · Zbl 0763.90063
[44] Hansen, P. C.; Gesmar, H., Fast orthogonal decomposition of rank deficient Toeplitz matrices, Numer. Algorithms, 4, 151-166 (1993) · Zbl 0779.65027
[46] Hestenes, M. R.; Stiefel, E., Methods of conjugate gradients for solving linear systems, J. Res. Natl. Bur. Standards, 49, 409-436 (1952) · Zbl 0048.09901
[47] Higham, N. J., Error analysis of the Björck-Pereyra algorithms for solving Vandermonde systems, Numer. Math., 50, 613-632 (1987) · Zbl 0595.65029
[48] Higham, N. J., Accuracy and Stability of Numerical Algorithms (1996), SIAM: SIAM Philadelphia, PA · Zbl 0847.65010
[49] Huber, P. J., Robust estimation of a location parameter, Ann. Math. Statist., 35, 73-101 (1964) · Zbl 0136.39805
[50] Huber, P. J., Robust Statistics (1981), Wiley: Wiley New York · Zbl 0536.62025
[51] Kailath, T.; Sayed, A. H., Displacement structure: theory and applications, SIAM Rev., 37, 297-386 (1995) · Zbl 0839.65028
[52] Karmarkar, N. K., A new polynomial-time algorithm for linear programming, Combinatorica, 4, 373-395 (1984) · Zbl 0557.90065
[53] Karmarkar, N. K.; Ramakrishnan, K. G., Computational results of an interior point algorithm for large scale linear programming, Math. Programming, 52, 555-586 (1991) · Zbl 0739.90042
[54] Kellogg, R. B.; Li, T.-Y.; Yorke, J. A., A constructive proof of the Brouwer fixed-point theorem and computational results, SIAM J. Numer. Anal., 13, 473-483 (1976) · Zbl 0355.65037
[55] Khachian, L. G., A polynomial algorithm in linear programming, Dokl. Akad. Nauk SSSR, 244, 1093-1096 (1979) · Zbl 0414.90086
[57] Kolda, T.; O’Leary, D. P.; Nazareth, L., BFGS with update skipping and varying memory, SIAM J. Optim., 8, 1060-1083 (1998) · Zbl 0918.65044
[58] Kung, H. T.; Leiserson, C. E., Introduction to VLSI systems (1980), Addison-Wesley: Addison-Wesley Reading, MA
[60] Lewis, A. S.; Overton, M. L., Eigenvalue optimization, Acta Numer., 5, 149-190 (1996) · Zbl 0870.65047
[61] Lobo, M.; Vandenberghe, L.; Boyd, S.; Lebret, H., Applications of second-order cone programming, Linear Algebra Appl., 284, 193-228 (1998) · Zbl 0946.90050
[62] Luenberger, D. G., Linear and Nonlinear Programming (1984), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0241.90052
[64] Lustig, I. J.; Marsten, R. E.; Shanno, D. F., Interior point methods for linear programming: computational state of the art, ORSA J. Comput., 6, 1, 1-14 (1994) · Zbl 0798.90100
[65] Mehrotra, S., Implementation of affine scaling methods: Approximate solutions of systems of linear equations using preconditioned conjugate gradient methods, ORSA J. Comput., 4, 2, 103-118 (1992) · Zbl 0782.90067
[66] Murty, K. G., Linear Complementarity, Linear and Nonlinear Programming (1988), Heldermann Verlag: Heldermann Verlag Berlin, Germany · Zbl 0634.90037
[68] Narula, S. C., Optimization techniques in linear regression: a review, TIMS/Stud. Management Sci., 19, 11-29 (1982)
[69] Nash, S. G., Preconditioning of truncated-Newton methods, SIAM J. Sci. Statist. Comput., 6, 599-616 (1985) · Zbl 0592.65038
[70] Nocedal, J., Updating quasi-Newton matrices with limited storage, Math. Comp., 35, 773-782 (1980) · Zbl 0464.65037
[71] Nocedal, J., Theory of algorithms for unconstrained optimization, Acta Numerica, 1, 199-242 (1992) · Zbl 0766.65051
[72] O’Leary, D. P., A discrete Newton algorithm for minimizing a function of many variables, Math. Programming, 23, 20-33 (1982) · Zbl 0477.90055
[73] O’Leary, D. P., Robust regression computation using iteratively reweighted least squares, SIAM J. Matrix Anal. Appl., 11, 466-480 (1990) · Zbl 0704.65027
[74] Ortega, J. M.; Rheinboldt, W. C., Iterative Solution of Nonlinear Equations in Several Variables (1970), Academic Press: Academic Press New York · Zbl 0241.65046
[75] Overton, M.; Wolkowicz, H., Forward: special issue on semidefinite programming, Math. Programming, 77, 105-110 (1997)
[76] Park, H.; Eldén, L., Stability analysis and fast algorithms for triangularization of Toeplitz matrices, Numer. Math., 76, 383-402 (1997) · Zbl 0878.65019
[77] Peters, G.; Wilkinson, J. H., The least squares problem and pseudo-inverses, Comput. J., 13, 309-316 (1970) · Zbl 0195.44804
[78] Polak, E.; Ribière, G., Note sur la convergence de methodes de directions conjugées, Rev. Francaise Informat Recherche Operationelle 3eAnnée, 16, 35-43 (1969) · Zbl 0174.48001
[80] Reid, J. K., A Note on the least squares solution of a band system of linear equations by Householder reductions, Comput J., 10, 188-189 (1967) · Zbl 0168.13305
[81] Saunders, M. A., Cholesky-based methods for sparse least squares: the benefits of regularization, (Adams, L.; Nazareth, J. L., Linear and Nonlinear Conjugate Gradient-Related Methods (1996), SIAM: SIAM Philadelphia, PA), 92-100 · Zbl 0865.65022
[83] Shanno, D. F.; Simantiraki, E. M., Interior point methods for linear and nonlinear programming, (Duff, I. S.; Watson, G. A., The State of the Art in Numerical Analysis (1997), Clarendon Press: Clarendon Press Oxford, England), 339-362 · Zbl 0881.65052
[84] Stewart, G. W., Modifying pivot elements in Gaussian elimination, Math. Comp., 28, 126, 537-542 (1974) · Zbl 0293.65015
[85] Stewart, G. W., On the early history of the singular value decomposition, SIAM Rev., 35, 551-566 (1993) · Zbl 0799.01016
[86] Sweet, D. R., Fast Toeplitz orthogonalization, Numer. Math., 43, 1-21 (1984) · Zbl 0504.65017
[87] Terlaky (Ed.), T., Interior Point Methods of Mathematical Programming (1996), Kluwer Academic Publishers: Kluwer Academic Publishers Boston · Zbl 0866.00024
[88] Vapnik, V., The Nature of Statistical Learning Theory (1995), Springer: Springer New York · Zbl 0833.62008
[90] Varga, R. S., Matrix Iterative Analysis (1962), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0133.08602
[93] Watson, L. T.; Sosonkina, M.; Melville, R. C.; Morgan, A. P.; Walker, H. F., Algorithm 777: HOMPACK90: a suite of Fortran 90 codes for globally convergent homotopy algorithms, ACM Trans. Math. Software, 23, 514-549 (1997) · Zbl 0913.65042
[94] Wedin, P.-Å., Perturbation theory for pseudo-inverses, BIT, 13, 217-232 (1973) · Zbl 0263.65047
[95] Wright, M. H., Interior methods for constrained optimization, Acta Numerica, 1, 341-407 (1992) · Zbl 0766.65053
[96] Ypma, T. J., Historical development of the Newton-Raphson method, SIAM Rev., 37, 531-551 (1995) · Zbl 0842.01005
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.