Abstract
This paper studies subspace properties of trust region methods for unconstrained optimization, assuming the approximate Hessian is updated by quasi- Newton formulae and the initial Hessian approximation is appropriately chosen. It is shown that the trial step obtained by solving the trust region subproblem is in the subspace spanned by all the gradient vectors computed. Thus, the trial step can be defined by minimizing the quasi-Newton quadratic model in the subspace. Based on this observation, some subspace trust region algorithms are proposed and numerical results are also reported.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bongartz I., Conn A.R., Gould N.I.M., Toint Ph.L.(1995): CUTE: constrained and unconstrained testing environment. ACM Trans. Math. Softw. 21, 123–160
Byrd R., Schnabel R.B., Shultz G.A.(1988): Approximation solution of the trust region problem by minimization over two-dimensional subspaces. Math. Prog. 40, 247–263
Conn A.R., Gould N.I.M., Sartenaer A., Toint Ph.L.(1996): On the iterated-subspace minimization methods for nonlinear optimization with a combination of general equality and constraints. In: Adams L., Nazareth J.L. (eds). Proceedings on Linear and Nonlinear Conjugate Gradient-Related Methods, pp. 50–78. SIAM
Conn A.R., Gould N.I.M., Toint Ph.L.(1988): Testing a class of methods for solving minimization problems with simple bounds on the variables. Math. Comput. 50, 399–430
Conn A.R., Gould N.I.M., Toint Ph.L.(2000): Trust-Region Methods. SIAM Publications, Philadelphia, Pennsylvania
Daniel W., Gragg W.B., Kaufman L., Stewart G.W.(1976): Reorthogonalization and stable algorithms for updating the Gram–Schmidt QR factorization. Math. Comput. 30, 772–795
Dennis J.E., Mei H.H.W.(1979): Two new unconstrained optimization algorithms which use function and gradient values. J. Optim. Appl. 28, 453–482
Dennis J.E., Schnabel R.B.(1983): Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Prentice-Hall, Englewood Cliffs, NJ
Dolan E.D., Moré J.J.(2002): Benchmarking optimization software with performance profiles. Math. Prog. 91, 201–213
Fletcher R.(1987): Practical Methods of Optimization, 2nd edn. Wiley, New York
Gay D.M.(1981): Computing optimal locally constrained steps. SIAM J. Sci. Stat. Comput. 2, 186–197
Gill P.E., Leonard M.W.(2001) : Reduced-Hessian quasi-Newton methods for unconstrained optimization. SIAM J. Optim. 12, 209–237
Golub G.H., Van Loan C.F.(1996): Matrix Computations, 3rd edn. Johns Hopkins University Press, Baltimore
Gould N.I.M., Orban D., Toint Ph.L.(2003): CUTEr and SifDec: a constrained and unconstrained testing environment, revisited. ACM Trans. Math. Softw. 29, 373–394
Liu D.C., Nocedal J.(1989): On the limited memory BFGS method for large scale optimization. Math. Prog. 45, 503–528
Moré J.J., Sorensen D.C.(1983): Computing a trust region step. SIAM J. Sci. Stat. Comput. 4, 553–572
Nocedal J., Yuan Y.(1998): Combining trust region and line search techniques. In: Yuan Y. (eds). Advances in Nonlinear Programming, Proceedings of the 1996 International Conference on Nonlinear Programming. Kluwer, Dordrecht, pp. 153–176
Powell M.J.D. (1970): A new algorithm for unconstrained optimization. In: Rosen J.B., Mangasarian O.L., Ritter K.(eds). Nonlinear Programming. Academic, New York, pp. 31–66
Powell M.J.D.(1970): A hybrid method for nonlinear equations. In: Robinowitz P. (eds). Numerical Methods for Nonlinear Algebraic Equations. Gordon and Breach Science, London, pp. 87–144
Powell M.J.D.(1975): Convergence properties of a class of minimization algorithms. In: Mangasarian O.L., Meyer R.R., Robinson S.M. (eds). Nonlinear Programming, 2. Academic, New York, pp. 1–27
Powell M.J.D.(1984): On the global convergence of trust region algorithms for unconstrained minimization. Math. Prog. 29, 297–303
Siegel, D.: Implementing and modifying Broyden class updates for large scale optimization. Report DAMPT 1992/NA12, University of Cambridge, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Cambridge, England (1992)
Siegel D.(1994): Modifying the BFGS update by a new column scaling technique. Math. Prog. 66, 45–78
Sorensen D.C.(1982): Newton’s method with a model trust region modifications. SIAM J. Numer. Anal. 19, 409–426
Steihaug T.(1983): The conjugate gradient method and trust regions in large scale optimization. SIAM J. Numer. Anal. 20, 626–637
Stewart G.W.(1998): Matrix Algorithms. Volume 1: Basic Decompostions. SIAM, Philadelphia, PA
Stoer J., Yuan Y.(1995): A subspace study on conjugate gradient algorithms. ZAMM Z. Angew. Math. Mech. 75, 69–77
Vl \(\tilde{c}\)ek, J., Luk \(\tilde{s}\)an, L.: New variable metric methods for unconstrained minimization covering the large-scale case. Technical Report No. V876, October 2002, Institute of Computer Science, Academy of Sciences of the Czech Republic (2002)
Yuan Y.(1994): Numerical Methods for Nonlinear Optimization. Shanghai Science and Technology Press, Shanghai
Yuan Y. (2000): A review of trust region algorithms for optimization. In: Ball J.M., Hunt J.C.R. (eds). ICM99: Proceedings of the Fourth International Congress on Industrial and Applied Mathematics. Oxford University Press, Oxford, pp. 271–282
Yuan Y.(2000): On the truncated conjugate gradient method. Math. Prog. 87, 561–571
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Wang, ZH., Yuan, YX. A subspace implementation of quasi-Newton trust region methods for unconstrained optimization. Numer. Math. 104, 241–269 (2006). https://doi.org/10.1007/s00211-006-0021-6
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00211-006-0021-6