Variable metric methods for unconstrained optimization and nonlinear least squares. (English) Zbl 0985.65066
This is a review of variable metric methods for unconstrained optimization. A particular attention is focused on the derivation of formulas and their efficient implementation. Suggestions are given based on the authors’ numerical experience.
Reviewer: S.Zlobec (Montreal)
MSC:
| 65K05 | Numerical mathematical programming methods |
| 90C30 | Nonlinear programming |
| 90C53 | Methods of quasi-Newton type |
Keywords:
nonlinear least squares; methods of quasi-Newton type; variable metric methods; unconstrained optimizationReferences:
| [1] | Abaffy, J.; Spedicato, E., ABS Projection Algorithms, Mathematical Techniques for Linear and Nonlinear Equations (1989), Ellis Horwood: Ellis Horwood Chichester · Zbl 0691.65022 |
| [2] | Adachi, N., On variable metric algorithm, J. Optim. Theory Appl., 7, 391-409 (1971) · Zbl 0203.48703 |
| [3] | Al-Baali, M., Highly efficient Broyden methods of minimization with variable parameter, Optim. Methods Software, 1, 301-310 (1992) |
| [4] | Al-Baali, M.; Fletcher, R., Variational methods for nonlinear least squares, J. Optim. Theory Appl., 36, 405-421 (1985) · Zbl 0578.65064 |
| [5] | Axelsson, O., Iterative Solution Methods (1996), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0845.65011 |
| [6] | Betts, J. T., Solving the nonlinear least squares problem: application of a general method, J. Optim. Theory Appl., 18, 469-483 (1976) · Zbl 0304.49024 |
| [7] | Biggs, M. C., Minimization algorithms making use of nonquadratic properties of the objective function, J. Inst. Math. Appl., 8, 315-327 (1971) · Zbl 0226.90045 |
| [8] | Biggs, M. C., A note on minimization algorithms which make use of non-quadratic properties of the objective function, J. Inst. Math. Appl., 12, 337-338 (1973) · Zbl 0268.65040 |
| [9] | Biggs, M. C., The estimation of the Hessian matrix in nonlinear least squares problems with nonzero residuals, Math. Programming, 12, 67-80 (1977) · Zbl 0365.65043 |
| [10] | Broyden, C. G., A class of methods for solving nonlinear simultaneous equations, Math. Comp., 19, 577-593 (1965) · Zbl 0131.13905 |
| [11] | C.G. Broyden, The convergence of a class of double rank minimization algorithms, Part 1 - general considerations, Part 2 - the new algorithm, J. Inst. Math. Appl. 6 (1970) 76-90, 222-231.; C.G. Broyden, The convergence of a class of double rank minimization algorithms, Part 1 - general considerations, Part 2 - the new algorithm, J. Inst. Math. Appl. 6 (1970) 76-90, 222-231. · Zbl 0223.65023 |
| [12] | Buckley, A., A combined conjugate-gradient quasi-Newton minimization algorithm, Math. Programming, 15, 200-210 (1978) · Zbl 0386.90051 |
| [13] | Buckley, A.; LeNir, A., QN-like variable storage conjugate gradients, Math. Programming, 27, 155-175 (1983) · Zbl 0519.65038 |
| [14] | R.H. Byrd, D.C. Liu, J. Nocedal, On the behavior of Broyden’s class of quasi-Newton methods, Report No. NAM 01, Dept. of Electrical Engn. and Computer Science, Northwestern University, Evanston, 1990.; R.H. Byrd, D.C. Liu, J. Nocedal, On the behavior of Broyden’s class of quasi-Newton methods, Report No. NAM 01, Dept. of Electrical Engn. and Computer Science, Northwestern University, Evanston, 1990. · Zbl 0770.90063 |
| [15] | Byrd, R. H.; Nocedal, J.; Schnabel, R. B., Representation of quasi-Newton matrices and their use in limited memory methods, Math. Programming, 63, 129-156 (1994) · Zbl 0809.90116 |
| [16] | Byrd, R. H.; Nocedal, J.; Yuan, Y. X., Global convergence of a class of quasi-Newton methods on convex problems, SIAM J. Numer. Anal., 24, 1171-1190 (1987) · Zbl 0657.65083 |
| [17] | Coleman, M.; Moré, J. J., Estimation of sparse Hessian matrices and graph coloring problems, Math. Programming, 42, 245-270 (1988) · Zbl 0572.65029 |
| [18] | Contreras, M.; Tapia, R. A., Sizing the BFGS and DFP updates: a numerical study, J. Optim. Theory Appl., 78, 93-108 (1993) · Zbl 0796.90054 |
| [19] | W.C. Davidon, Variable metric method for minimisation, A.E.C. Research and Development Report ANL-5990, 1959.; W.C. Davidon, Variable metric method for minimisation, A.E.C. Research and Development Report ANL-5990, 1959. |
| [20] | Davidon, W. C., Optimally conditioned optimization algorithms without line searches, Math. Programming, 9, 1-30 (1975) · Zbl 0328.90055 |
| [21] | Dembo, R. S.; Steihaug, T., Truncated-Newton algorithms for large-scale unconstrained minimization, Math. Programming, 26, 190-212 (1983) · Zbl 0523.90078 |
| [22] | Dennis, J. E., Some computational techniques for the nonlinear least squares problem, (Byrne, G. D.; Hall, C. A., Numerical Solution of Nonlinear Algebraic Equations (1974), Academic Press: Academic Press London) · Zbl 0275.65020 |
| [23] | Dennis, J. E.; Gay, D.; Welsch, R. E., An adaptive nonlinear least squares algorithm, ACM Trans. Math. Software, 7, 348-368 (1981) · Zbl 0464.65040 |
| [24] | Dennis, J. E.; Martinez, H. J.; Tapia, R. A., Convergence theory for the structured BFGS secant method with application to nonlinear least squares, J. Optim. Theory Appl., 61, 161-177 (1989) · Zbl 0645.65026 |
| [25] | J.E. Dennis, H.H.W. Mei, An unconstrained optimization algorithm which uses function and gradient values, Report No. TR-75-246, Dept. of Computer Science, Cornell University, 1975.; J.E. Dennis, H.H.W. Mei, An unconstrained optimization algorithm which uses function and gradient values, Report No. TR-75-246, Dept. of Computer Science, Cornell University, 1975. · Zbl 0317.49041 |
| [26] | Dennis, J. E.; Moré, J. J., A characterization of superlinear convergence and its application to quasi-Newton methods, Math. Comp., 28, 549-560 (1974) · Zbl 0282.65042 |
| [27] | J.E. Dennis, R.B. Schnabel, Least change secant updates for quasi-Newton methods, Report No. TR78-344, Dept. of Computer Sci., Cornell University, Ithaca, 1978.; J.E. Dennis, R.B. Schnabel, Least change secant updates for quasi-Newton methods, Report No. TR78-344, Dept. of Computer Sci., Cornell University, Ithaca, 1978. |
| [28] | Dennis, J. E.; Schnabel, R. B., Numerical Methods for Unconstrained Optimization and Nonlinear Equations (1983), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0579.65058 |
| [29] | Dennis, J. E.; Schnabel, R. B., A view of unconstrained optimization, (Nemhauser, G. L.; Rinnooy Kan, A. H.G.; Todd, M. J., Optimization (1989), North-Holland: North-Holland Amsterdam) · Zbl 0688.90034 |
| [30] | Dixon, L. C.W., Quasi-Newton algorithms generate identical points, Math. Programming, 2, 383-387 (1972) · Zbl 0245.65029 |
| [31] | Fletcher, R., A new approach to variable metric algorithms, Comput. J., 13, 317-322 (1970) · Zbl 0207.17402 |
| [32] | Fletcher, R., Practical Methods of Optimization (1987), Wiley: Wiley New York · Zbl 0905.65002 |
| [33] | Fletcher, R., Low storage methods for unconstrained optimization, (Algower, E. L.; Georg, K., Computational Solution of Nonlinear Systems of Equations, Lectures in Applied Mathematics, Vol. 26 (1990), AMS Publications: AMS Publications Providence, RI) · Zbl 0699.65052 |
| [34] | Fletcher, R., A new variational result for quasi-Newton formulae, SIAM J. Optim., 1, 18-21 (1991) · Zbl 0752.90064 |
| [35] | Fletcher, R., An optimal positive definite update for sparse Hessian matrices, SIAM J. Optim., 5, 192-218 (1995) · Zbl 0824.65038 |
| [36] | Fletcher, R.; Powell, M. J.D., A rapidly convergent descent method for minimization, Comput. J., 6, 163-168 (1963) · Zbl 0132.11603 |
| [37] | Fletcher, R.; Reeves, C. M., Function minimization by conjugate gradients, Comput. J., 7, 149-154 (1964) · Zbl 0132.11701 |
| [38] | Fletcher, R.; Xu, C., Hybrid methods for nonlinear least squares, IMA J. Numer. Anal., 7, 371-389 (1987) · Zbl 0648.65051 |
| [39] | Ford, J. A.; Moghrabi, I. A., Alternative parameter choices for multi-step quasi-Newton methods, Optim. Methods Software, 2, 357-370 (1993) |
| [40] | Ford, J. A.; Moghrabi, I. A., Multi-step quasi-Newton methods for optimization, J. Comput. Appl. Math., 50, 305-323 (1994) · Zbl 0807.65062 |
| [41] | J.A. Ford, I.A. Moghrabi, Minimum curvature multi-step quasi-Newton methods for unconstrained optimization, Report No. CSM-201, Department of Computer Science, University of Essex, Colchester, 1995.; J.A. Ford, I.A. Moghrabi, Minimum curvature multi-step quasi-Newton methods for unconstrained optimization, Report No. CSM-201, Department of Computer Science, University of Essex, Colchester, 1995. · Zbl 0972.65039 |
| [42] | Greenstadt, J., Variations on variable metric methods, Math. Comput., 24, 1-18 (1970) · Zbl 0204.49601 |
| [43] | Gilbert, J. C.; Lemarechal, C., Some numerical experiments with variable-storage quasi-Newton algorithms, Math. Programming, 45, 407-435 (1989) · Zbl 0694.90086 |
| [44] | P.E. Gill, M.W. Leonard, Limited-memory reduced-Hessian methods for large-scale unconstrained optimization, Report NA 97-1, Dept. of Mathematics, University of California, San Diego, La Jolla, 1997.; P.E. Gill, M.W. Leonard, Limited-memory reduced-Hessian methods for large-scale unconstrained optimization, Report NA 97-1, Dept. of Mathematics, University of California, San Diego, La Jolla, 1997. · Zbl 1046.65045 |
| [45] | Gill, P. E.; Murray, W.; Saunders, M. A., Methods for computing and modifying LDV factors of a matrix, Math. Comput., 29, 1051-1077 (1975) · Zbl 0339.65022 |
| [46] | Goldfarb, D., A family of variable metric algorithms derived by variational means, Math. Comput., 24, 23-26 (1970) · Zbl 0196.18002 |
| [47] | Griewank, A., The global convergence of partitioned BFGS on problems with convex decompositions and Lipschitzian gradients, Math. Programming, 50, 141-175 (1991) · Zbl 0736.90068 |
| [48] | Griewank, A.; Toint, P. L., Partitioned variable metric updates for large-scale structured optimization problems, Numer. Math., 39, 119-137 (1982) · Zbl 0482.65035 |
| [49] | Griewank, A.; Toint, P. L., Local convergence analysis for partitioned quasi-Newton updates, Numer. Math., 39, 429-448 (1982) · Zbl 0505.65018 |
| [50] | A. Griewank, P.L. Toint, Numerical experiments with partially separable optimization problems, in: D.F. Griffits (Ed.), Numerical Analysis, Proc. Dundee 1983, Lecture Notes in Mathematics, Vol. 1066, Springer, Berlin, 1984, pp. 203-220.; A. Griewank, P.L. Toint, Numerical experiments with partially separable optimization problems, in: D.F. Griffits (Ed.), Numerical Analysis, Proc. Dundee 1983, Lecture Notes in Mathematics, Vol. 1066, Springer, Berlin, 1984, pp. 203-220. · Zbl 0531.65033 |
| [51] | Hestenes, M. R.; Stiefel, C. M., Methods of conjugate gradient for solving linear systems, J. Res. NBS, 49, 409-436 (1964) · Zbl 0048.09901 |
| [52] | Hoshino, S., A formulation of variable metric methods, J. Inst. Math. Appl., 10, 394-403 (1972) · Zbl 0258.65065 |
| [53] | Huang, H. Y., Unified approach to quadratically convergent algorithms for function minimization, J. Optim. Theory Appl., 5, 405-423 (1970) · Zbl 0184.20202 |
| [54] | Huschens, J., On the use of product structure in secant methods for nonlinear least squares, SIAM J. Optim., 4, 108-129 (1994) · Zbl 0798.65064 |
| [55] | Liu, D. C.; Nocedal, J., On the limited memory BFGS method for large-scale optimization, Math. Programming, 45, 503-528 (1989) · Zbl 0696.90048 |
| [56] | Lukšan, L., Computational experience with improved variable metric methods for unconstrained minimization, Kybernetika, 26, 415-431 (1990) · Zbl 0716.65055 |
| [57] | Lukšan, L., Computational experience with known variable metric updates, J. Optim. Theory Appl., 83, 27-47 (1994) · Zbl 0819.90097 |
| [58] | L. Lukšan, J. Vlček, Simple scaling for variable metric updates, Report No. 611, Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague 1995.; L. Lukšan, J. Vlček, Simple scaling for variable metric updates, Report No. 611, Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague 1995. |
| [59] | Lukšan, L., Hybrid methods for large sparse nonlinear least squares, J. Optim. Theory Appl., 89, 575-595 (1996) · Zbl 0851.90118 |
| [60] | L. Lukšan, Numerical methods for unconstrained optimization, Report DMSIA 12/97, University of Bergamo, 1997.; L. Lukšan, Numerical methods for unconstrained optimization, Report DMSIA 12/97, University of Bergamo, 1997. |
| [61] | L. Lukšan, M. Tůma, M. Šiška, J. Vlček, N. Ramešová, Interactive system for universal functional optimization (UFO) — Version 1998, Report No. 766, Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague, 1998.; L. Lukšan, M. Tůma, M. Šiška, J. Vlček, N. Ramešová, Interactive system for universal functional optimization (UFO) — Version 1998, Report No. 766, Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague, 1998. |
| [62] | L. Lukšan, J.Vlček, Subroutines for testing large sparse and partially separable unconstrained and equality constrained optimization problems, Report No. 767, Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague, 1999.; L. Lukšan, J.Vlček, Subroutines for testing large sparse and partially separable unconstrained and equality constrained optimization problems, Report No. 767, Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague, 1999. |
| [63] | Lukšan, L.; Vlček, J., Globally convergent variable metric method for convex nonsmooth unconstrained minimization, J. Optim. Theory Appl., 102, 593-613 (1999) · Zbl 0955.90102 |
| [64] | Martinez, J. M., A quasi-Newton method with modification of one column per iteration, Computing, 33, 353-362 (1984) · Zbl 0546.90102 |
| [65] | Moré, J. J.; Garbow, B. S.; Hillstrom, K. E., Testing unconstrained optimization software, ACM Trans. Math. Software, 7, 17-41 (1981) · Zbl 0454.65049 |
| [66] | J.J. Moré, D.C. Sorensen, Computing a trust region step, Report ANL-81-83, Argonne National Laboratory, 1981.; J.J. Moré, D.C. Sorensen, Computing a trust region step, Report ANL-81-83, Argonne National Laboratory, 1981. |
| [67] | Nocedal, J., Updating quasi-Newton matrices with limited storage, Math. Comp., 35, 773-782 (1980) · Zbl 0464.65037 |
| [68] | Nocedal, J.; Yuan, Y., Analysis of a self-scaling quasi-Newton method, Math. Programming, 61, 19-37 (1993) · Zbl 0794.90067 |
| [69] | S.S. Oren, D.G. Luenberger, Self scaling variable metric (SSVM) algorithms, Part 1 — criteria and sufficient condition for scaling a class of algorithms, Part 2 — implementation and experiments, Management Sci. 20 (1974) 845-862, 863-874.; S.S. Oren, D.G. Luenberger, Self scaling variable metric (SSVM) algorithms, Part 1 — criteria and sufficient condition for scaling a class of algorithms, Part 2 — implementation and experiments, Management Sci. 20 (1974) 845-862, 863-874. · Zbl 0316.90064 |
| [70] | Oren, S. S.; Spedicato, E., Optimal conditioning of self scaling variable metric algorithms, Math. Programming, 10, 70-90 (1976) · Zbl 0342.90045 |
| [71] | M.R. Osborne, L.P. Sun, A new approach to the symmetric rank-one updating algorithm. Report No. NMO/01, School of Mathematics, Australian National University, Canberra, 1988.; M.R. Osborne, L.P. Sun, A new approach to the symmetric rank-one updating algorithm. Report No. NMO/01, School of Mathematics, Australian National University, Canberra, 1988. · Zbl 0940.65071 |
| [72] | Perry, A., A modified conjugate gradient algorithm, Oper. Res., 26, 1073-1078 (1978) · Zbl 0419.90074 |
| [73] | Polak, E.; Ribiére, G., Note sur la convergence des méthodes de directions conjugées, Rev. Française Inform. Mech. Oper., 16-R1, 35-43 (1969) · Zbl 0174.48001 |
| [74] | Powell, M. J.D., A new algorithm for unconstrained optimization, (Rosen, J. B.; Mangasarian, O. L.; Ritter, K., Nonlinear Programming (1970), Academic Press: Academic Press London) · Zbl 0228.90043 |
| [75] | Powell, M. J.D., On the global convergence of trust region algorithms for unconstrained minimization, Math. Programming, 29, 297-303 (1984) · Zbl 0569.90069 |
| [76] | Pu, D. G.; Tian, W. W., A class of modified Broyden algorithms, J. Comput. Math., 12, 366-379 (1994) · Zbl 0826.65055 |
| [77] | Shanno, D. F., Conditioning of quasi-Newton methods for function minimization, Math. Comp., 24, 647-656 (1970) · Zbl 0225.65073 |
| [78] | Shanno, D. F.; Phua, K. J., Matrix conditioning and nonlinear optimization, Math. Programming, 14, 144-160 (1978) · Zbl 0371.90109 |
| [79] | D. Siegel, Implementing and modifying Broyden class updates for large scale optimization, Report DAMTP NA12, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, 1992.; D. Siegel, Implementing and modifying Broyden class updates for large scale optimization, Report DAMTP NA12, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, 1992. |
| [80] | Spedicato, E., Stability of Huang’s update for the conjugate gradient method, J. Optim. Theory Appl., 11, 469-479 (1973) · Zbl 0243.49013 |
| [81] | Spedicato, E., On condition numbers of matrices in rank-two minimization algorithms, (Dixon, L. C.W.; Szego, G. P., Towards Global Optimization (1975), North-Holland: North-Holland Amsterdam) · Zbl 0318.65029 |
| [82] | Spedicato, E., A bound on the condition number of rank-two corrections and applications to the variable metric method, Calcolo, 12, 185-199 (1975) · Zbl 0318.65029 |
| [83] | E. Spedicato, Parameter estimation and least squares, in: F. Archetti, M. Cugiani (Eds.), Numerical Techniques for Stochastic Systems, North-Holland, Amsterdam, 1980.; E. Spedicato, Parameter estimation and least squares, in: F. Archetti, M. Cugiani (Eds.), Numerical Techniques for Stochastic Systems, North-Holland, Amsterdam, 1980. · Zbl 0472.93079 |
| [84] | Spedicato, E., A class of rank-one positive definite quasi-Newton updates for unconstrained minimization, Math. Operationsforsch. Statist. Ser. Optim., 14, 61-70 (1983) · Zbl 0519.90075 |
| [85] | Spedicato, E., A class of sparse symmetric quasi-Newton updates, Ricerca Operativa, 22, 63-70 (1992) |
| [86] | E. Spedicato, N.Y. Deng, Z. Li, On sparse quasi-Newton quasi-diagonally dominant updates, Report DMSIA 1/96, University of Bergamo, 1996.; E. Spedicato, N.Y. Deng, Z. Li, On sparse quasi-Newton quasi-diagonally dominant updates, Report DMSIA 1/96, University of Bergamo, 1996. |
| [87] | Spedicato, E.; Xia, Z., Finding general solutions of the quasi-Newton equation via the ABS approach, Optim. Methods Software, 1, 243-252 (1992) |
| [88] | Spedicato, E.; Zhao, J., Explicit general solution of the Quasi-Newton equation with sparsity and symmetry, Optim. Methods Software, 2, 311-319 (1993) |
| [89] | Steihaug, T., Local and superlinear convergence for truncated iterated projections methods, Math. Programming, 27, 176-190 (1983) · Zbl 0532.49016 |
| [90] | Steihaug, T., The conjugate gradient method and trust regions in large-scale optimization, SIAM J. Numer. Anal., 20, 626-637 (1983) · Zbl 0518.65042 |
| [91] | Toint, P. L., On sparse and symmetric matrix updating subject to a linear equation, Math. Comp., 31, 954-961 (1977) · Zbl 0379.65034 |
| [92] | Toint, P. L., Global convergence of the partitioned BFGS algorithm for convex partially separable optimization, Math. Programming, 36, 290-306 (1986) · Zbl 0626.90076 |
| [93] | Toint, P. L., On large scale nonlinear least squares calculations, SIAM J. Sci. Statis. Comput., 8, 416-435 (1987) · Zbl 0616.65014 |
| [94] | M. Tůma, Sparse fractioned variable metric updates, Report No. 497, Institute of Computer and Information Sciences, Czechoslovak Academy of Sciences, Prague 1991.; M. Tůma, Sparse fractioned variable metric updates, Report No. 497, Institute of Computer and Information Sciences, Czechoslovak Academy of Sciences, Prague 1991. |
| [95] | Wolkowicz, H., Measures for rank-one updates, Math. Oper. Res., 19, 815-830 (1994) · Zbl 0821.90111 |
| [96] | Wolkowicz, H., An all-inclusive efficient region of updates for least change secant methods, SIAM J. Optim., 5, 172-191 (1996) · Zbl 0832.90112 |
| [97] | Yabe, H.; Takahashi, T., Factorized quasi-Newton methods for nonlinear least squares problems, Math. Programming, 51, 75-100 (1991) · Zbl 0737.90064 |
| [98] | Yuan, Y., Non-quasi-Newton updates for unconstrained optimization, J. Comput. Math., 13, 95-107 (1995) · Zbl 0823.65062 |
| [99] | J. Zhang, N.Y. Deng, L. Chen, A new quasi-Newton equation and related methods for unconstrained optimization, Report MA-96-05, City University of Hong Kong, 1996.; J. Zhang, N.Y. Deng, L. Chen, A new quasi-Newton equation and related methods for unconstrained optimization, Report MA-96-05, City University of Hong Kong, 1996. · Zbl 0991.90135 |
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.
