Abstract
In this paper, we analyze the global convergence of the least-change secant method proposed by Dennis and Wolkowicz, when applied to convex objective functions. One of the most distinguished features of this method is that the Dennis-Wolkowicz update doesn't necessarily belong to the Broyden convex family and can be close to the DFP update, but it still has the self-correcting property. We prove that, for convex objective functions, this method with the commonly used Wolfe line search is globally convergent. We also provide some numerical results.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
M. Al-Baali, “Highly efficient Broyden methods of minimization with variable parameter, ” Optimization Methods and Software, vol. 1, pp. 301–310, 1992.
R.H. Byrd, D.C. Liu, and J. Nocedal, “On the behavior of Broyden's class of quasi-Newton methods, ” SIAM J. Opt., vol. 2, pp. 533–557, 1992.
R.H. Byrd and J. Nocedal, “A tool for the analysis of quasi-Newton methods with application to unconstrained minimization, ” SIAM J. Numer. Anal., vol. 26, pp. 727–739, 1989.
R.H. Byrd, J. Nocedal, and Y. Yuan, “Global convergence of a class of quasi-Newton methods on convex problems, ” SIAM J. Numer. Anal., vol. 24, pp. 1171–1191, 1987.
R.H. Byrd, J. Nocedal, and C. Zhu, “Towards a discrete Newton method with memory for large-scale optimization, ” Technical Report OTC 95/01, 1996.
A.R. Conn, N.I.M. Gould, and Ph. L. Toint, “Convergence of quasi-Newton matrices generated by the symmetric rank one update, ” Math. Prog., vol. 2, pp. 177–195, 1991.
M. Contreras and R.A. Tapia, “Sizing the BFGS and DFP updates: Numerical study, ” JOTA, vol. 78, pp. 93–108, 1993.
W.C. Davidon, “Optimally conditioned optimization algorithms without line searches, ” Math. Prog, vol. 9, pp. 1–30, 1975.
J.E. Dennis Jr., D.M. Gay, and R.E. Welsch, “An adaptive nonlinear least-squares algorithm, ” TOMS, vol. 7, pp. 348–368, 1981.
J.E. Dennis Jr. and R.B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice-Hall: Englewood Cliffs, NJ, 1983 (in English). Mir Publishing Office, Moscow, 1988 (in Russian).
J.E. Dennis Jr. and H. Wolkowicz, “Sizing and least-change secant methods, ” SIAM J. Numer. Anal., vol. 30, pp. 1291–1314, 1993.
R. Fletcher, “A new variational result for quasi-Newton formulae, ” SIAM J. Opt., vol. 1, pp. 18–21, 1991.
R. Fletcher, Practical Methods of Optimization, 2nd ed., John Wiley and Sons: New York, 1987.
J.C. Gilbert and J. Nocedal, “Global convergence properties of conjugate gradient methods for optimization, ” SIAM J. Optimization, vol. 2, pp. 21–42, 1992.
L.X. Han and G.H. Liu, “Global analysis of the Dennis-Wolkowicz least-change secant algorithm, ” SIAM J. Opt., vol. 8, pp. 813–832, 1998.
H. Khalfan, R.H. Byrd, and R.B. Schnabel, “A theoretical and experimental study of the symmetric rank one update, ” University of Colorado, Boulder, Technical Report CU-CS-489-90, 1990.
D. Li and M. Fukushima, “On the global convergence of BFGS method for nonconvex unconstrained optimization problems, ” Department of Applied Mathematics and Physics, Kyoto University, Technical Report 99007, 1999.
L. Luksan, “Computational experience with known variable metric updates, ” JOTA, vol. 83, pp. 27–47, 1994.
J. Nocedal, “Theory of algorithms for unconstrained optimization, ” in Acta Numerica, A. Iserles, (Ed.), Cambridge University Press: Cambridge, England, 1992, pp. 199–242.
S.S. Oren and D.G. Luenberger, “Self-scaling veriable metric (SSVM)algorithms, Part I. Criteria and sufficient conditions for scaling a class of algorithms, ” Management Sci., vol. 20, pp. 845–862, 1974.
S.S. Oren and E. Spedicato, “Optimal conditioning of self-scaling variable metric algorithms, ” Math. Prog., vol. 10, pp. 70–90, 1976.
J.D. Pearson, “Variable metric methods of minimization, ” The Computer J., vol. 12, pp. 171–178, 1969.
K.H. Phua and D.F. Shanno, “Numerical comparison of several variable metric algorithms, ” JOTA, vol. 25, pp. 507–518, 1978.
M.J.D. Powell, “Some properties of the variable metric algorithm, ” in Numerical Methods for Nonlinear Optimization, F.A. Lootsma, (Ed.), Academia Press: London, 1972.
M.J.D. Powell, “Some global convergence properties of a variable metric algorithm for minimization without exact line searches in Nonlinear Programming, ” in SIAM-AMS Proceedings, 1976, vol. IX., R.W. Cottle and C.E. Lemke (Eds.), American Mathematical Society: Providence, RI.
D. Pu and W. Tian, “A class of modified Broyden algorithms, ” J. of Computational Mathematics, vol. 12, pp. 366–379, 1994.
J.Werner, “Global convergence of quasi-Newton methods with practical line searches, ” NAM-Bericht Nr. 67, Marz, Technical Report, 1989.
H. Wolkowicz, “Measures for symmetric rank-one updates, ” Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Tech. Report CORR 90-03, 1990.
Y. Zhang and R.P. Tewarson, “Quasi-Newton algorithms with updates from the pre-convex part of Broyden's family, ” IMA J. Numer. Anal., vol. 8, pp. 487–509, 1988.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Liu, G., Han, L. A Study of the Dennis-Wolkowicz Method on Convex Functions. Computational Optimization and Applications 19, 297–317 (2001). https://doi.org/10.1023/A:1011212022308
Issue Date:
DOI: https://doi.org/10.1023/A:1011212022308