×

Sizing the BFGS and DFP updates: Numerical study. (English) Zbl 0796.90054

Summary: We develop and test a strategy for selectively sizing (multiplying by an appropriate scalar) the approximate Hessian matrix before it is updated in the BFGS and DFP trust-region methods for unconstrained optimization. Our numerical results imply that, for use with the DFP update, the Oren- Luenberger sizing factor is completely satisfactory and selective sizing is vastly superior to the alternatives of never sizing or first-iteration sizing and is slightly better than the alternative of always sizing. Numerical experimentation showed that the Oren-Luenberger sizing factor is not a satisfactory sizing factor for use with the BFGS update. Therefore, based on our newly acquired understanding of the situation, we propose a centered Oren-Luenberger sizing factor to be used with the BFGS update. Our numerical experimentation implies that selectively sizing the BFGS update with the centered Oren-Luenberger sizing factor is superior to the alternatives. These results contradict the folk axiom that sizing should be done only at the first iteration. They also show that, without sufficient sizing, DFP is vastly inferior to BFGS; however, when selectively sized, DFP is competitive with BFGS.

MSC:

90C30 Nonlinear programming

Software:

minpack
Full Text: DOI

References:

[1] Dennis, J. E., Jr., andSchnabel, R. B.,Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice-Hall, Englewood Cliffs, New Jersey, 1983.
[2] Oren, S. S., andLuenberger, D. G.,Self-Scaling Variable Metric (SSVM) Algorithms, Management Science, Vol. 20, pp. 845-862, 1974. · Zbl 0316.90064 · doi:10.1287/mnsc.20.5.845
[3] Oren, S. S., andSpedicato, E.,Optimal Conditioning of Self-Scaling Variable Metric Algorithms, Mathematical Programming, Vol. 10, pp. 70-90, 1976. · Zbl 0342.90045 · doi:10.1007/BF01580654
[4] Shanno, D. F., andPhua, K.,Matrix Conditioning and Nonlinear Optimization, Mathematical Programming, Vol. 14, pp. 149-160, 1978. · Zbl 0371.90109 · doi:10.1007/BF01588962
[5] Dennis, J. E., Jr., Gay, D., andWelsh, R. E.,An Adaptive Nonlinear Least-Squares Algorithm, ACM Transactions on Mathematical Science, Vol. 7, pp. 348-368, 1981. · Zbl 0464.65040 · doi:10.1145/355958.355965
[6] Huschens, J.,On the Use of Product Structure in Secant Methods for Nonlinear Least Squares Problems, Unpublished Manuscript, Universität Trier, Trier, Germany, 1991. · Zbl 0798.65064
[7] Dennis, J. E., Jr., Martinez, H. J., andTapia, R. A.,Convergence Theory for the Structured BFGS Secant Method with an Application to Nonlinear Least Squares, Journal of Optimization Theory and Applications, Vol. 61, pp. 161-178, 1989. · Zbl 0645.65026 · doi:10.1007/BF00962795
[8] McLeod, R. M.,Mean-Value Theorems for Vector-Valued Functions, Proceedings of the Edinburgh Mathematics Society, Vol. 14, pp. 197-209, 1964. · Zbl 0135.34301 · doi:10.1017/S0013091500008786
[9] Dennis, J. E., Jr., andWolkowicz, H.,Sizing and Least Change Secant Methods, Technical Report TR90-5, Department of Mathematical Sciences, Rice University, 1990.
[10] Carter, R.,Safeguarding Hessian Approximations in Trust Region Algorithms, Technical Report TR87-12, Department of Mathematical Sciences, Rice University, 1987.
[11] Al-Baali, M.,Partial Self Scaling Variable Metric Algorithms, Report 80, Dipartimento dei Sistemi, Universitá della Calabria, 1988. · Zbl 0851.65048
[12] Luksan, L.,Computational Experience with Improved Variable Metric Methods for Unconstrained Minimization, Kybernetika, Vol. 26, pp. pp. 415-431, 1990. · Zbl 0716.65055
[13] Byrd, R. H., Tapia, R. A., andZhang, Y.,An SQP Augmented Lagrangian BFGS Algorithm for Constrained Optimization, SIAM Journal on Optimization, Vol. 2, pp. 210-241, 1992. · Zbl 0773.90065 · doi:10.1137/0802012
[14] Nocedal, J., andYuan, Y.,Analysis of Self-Scaling Quasi-Newton Method, Report, Department of Electrical Engineering and Computer Science, Northwestern University, 1990.
[15] Moré, J. J., Garbow, B. S., andHillstrom, K. E.,Testing Unconstrained Optimization Software, Technical Report ANL-78-324, Applied Mathematics Division, Argonne National Laboratories, 1978. · Zbl 0454.65049
[16] Raydan, M.,On the Barzilai and Borwein Choice of Steplength for the Gradient Method, Technical Report TR90-11, Department of Mathematical Sciences, Rice University, 1990. · Zbl 0778.65045
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.