Article Sidebar

Submitted
Apr 26, 2017
Published
Jun 1, 2007
Download
PDF
Statistic
Read Counter : 522 Download : 335

Main Article Content

Abstract

Quasi-Newton methods are among the most practical and efficient iterative methods for solving unconstrained minimization problems. In this paper we give an overview of some of these methods with focus primarily on the Hessian approximation updates and modifications aimed at improving their performance.

 

 

Keywords

Unconstrained optimization line search technique quasi-newton methods.

Article Details

References

  1. AL-BAALI, M. 1993. Variational quasi-newton methods for unconstrained optimization. JOTA, 77: 127–143.
  2. AL-BAALI, M. 1995. On measure functions for the self–scaling updating formulae for quasi–newton methods. Optimization, 32: 59–69.
  3. AL-BAALI, M. 1998. Global and superliner convergence of a restricted class of self-scaling methods with inexact line searches for convex functions. COAP, 9: 191–203.
  4. AL-BAALI, M. 2003a. Quasi-Newton Algorithms for Large-Scale Nonlinear Least-Squares. In High Performance Algorithms and Software for Nonlinear Optimization, Editors G. Di Pillo and A. Murli, Kluwer Academic, pp. 1-21.
  5. AL-BAALI, M. 2003b. 18th International Symposium on Mathematical Programming, Copenhagen, August 18–22.
  6. AL-BAALI, M., FUDULI, A. and MUSMANNO, R. 2004. On the Performance of Switching BFGS/SR1 Algorithms for Unconstrained Optimization. OMS, 19: 153-164.
  7. AL-BAALI, M. and KHALFAN, H. 2005. A Wide Interval for Efficient Self-Scaling Quasi-Newton Algorithms. OMS, 20: 679–691.
  8. BYRD, R.H., LIU, D.C. and NOCEDAL, J. 1992. On the Behavior of Broyden’s Class of Quasi-Newton Methods. SIAM J. Optim., 2: 533–557.
  9. BYRD, R.H., NOCEDAL, J. and SCHNABEL, R.B. 1994. Representation Matrices and their Use in Limited-Memory Methods. Math. Programming, Series A, 63: 129-156.
  10. BYRD, R.H., NOCEDAL, J. and YUAN, Y. 1987. Global Convergence of a Class of Quasi-Newton Methods on Convex Problems. SIAM J. Numer. Anal., 24: 1171–1190.
  11. CONN, A.R., GOULD, N.I.M. and TOINT, PH.L. 1991. Convergence of Quasi-Newton Matrices Generated by the Symmetric Rank One Update. Math. Programming, 50: 177–195.
  12. CONN, A.R., GOULD, N.I.M. and TOINT, PH.L. 1991. LANCELOT: A Fortran Package for Large-Scale Nonlinear Optimization (Release A), Springer Series in Computational Mathematics, Springer, New York.
  13. CONN, A.R., GOULD, N.I.M. and TOINT, PH.L. 1994. Large-Scale Nonlinear Constrained Optimization: A Current Survey, in Algorithms for Continuous Optimization: The State of the Art (E. Spedicato, ed.), Vol. 434 of NATO ASI Series C: Mathematical and Physical Sciences, Kluwer, Dordrecht, Netherlands, pp. 287–332.
  14. CONN, A.R., GOULD, N.I.M. and TOINT, PH.L. 1996. Large-Scale Nonlinear Optimization 351, ‘Numerical Experiments with the LANCELOT Package (Release A) for Large-Scale Nonlinear Optimization.’ Math. Programming, Ser. A, 73: 73–110.
  15. CONTRERAS, M. and TAPIA, R.A. 1993. Sizing the BFGS and DFP Updates: A Numerical Study. JOTA, 78: 93–108.
  16. DAI, Y. 2002. Convergence Properties of the BFGS Algorithm. SIAM J. Optim., 13: 693–701.
  17. DAVIDON, W.C. 1975. Optimally Conditioned Optimization Algorithms without Line Searches. Math. Programming, 9: 1-30.
  18. DENNIS, J.E. and SCHNABEL, R.B. 1996. Numerical Methods for Unconstrained Optimization and Nonlinear Equations, SIAM Publications.
  19. DIXON, L.C.W. 1972. Quasi-Newton Methods Generate Identical Points. Math. Programming, 2: 383–387.
  20. FIACO, A.V. and MCCORMICK, G.P. 1968. Nonlinear Programming: Sequential Unconstrained Minimization Techniques, Wiley, New York. Reprinted by SIAM Publications, 1990.
  21. FLETCHER, R. 1987. Practical Methods of Optimization (2nd edition), Wiley, Chichester, England. Reprinted in 2000.
  22. FLETCHER, R. 1994. An Overview of Unconstrained Optimization. In E. Spedicato, editor, Algorithms for Continuous Optimization: The state of the Art, Kluwer Academic, Boston, pp. 109–143.
  23. FORD, J.A. and THARMLIKIT, S. 2003. New Implicit Updates in Multi-Step Quasi-Newton Methods for Unconstrained Optimization. J. Compt. Appl. Math., 152: 133–146.
  24. GE, R.-P. and POWELL, M.J.D. 1983. The Convergence of Variable Metric Matrices in Unconstrained Optimization. Math. Programming, 27: 123–143.
  25. GILL, P.E. and LEONARD, M.W. 2003. Limited-Memory Reduced-Hessian Methods for Large-Scale Unconstrained Optimization. SIAM J. Optim., 14: 380–401.
  26. GRIEWANK, A. 1991. The Global Convergence of Partitioned BFGS on Problems with Convex Decomposition and Lipschitzian Gradient. Math. Programming, 50: 141-175.
  27. GRIEWANK, A. and TOINT, PH.L. 1982. On the Unconstrained Optimization of Partially Separable Objective Functions in Nonlinear Optimization. In 1981 (M.J.D. Powell Ed.) Academic Press, (London), 301-302.
  28. GRIEWANK, A. and TOINT, PH.L. 1984. Numerical Experiments with Partially Separable Optimization Problems. In Numerical Analysis Proceedings Dundee 1983, Lecture Notes in Mathematics 1066 (D.F. Griffiths Ed.) Springer Verlag (Berlin), 203-220.
  29. KHALFAN, H.F. 1989. Topics in Quasi-Newton Methods for Unconstrained Optimization, Ph.D. thesis, University of Colorado at Boulder, USA.
  30. KHALFAN, H.F., BYRD, R.H. and SCHNABEL, R.B. 1993. A Theoretical and Experimental Study of the Symmetric Rank One Update. SIAM J. Optim., 3: 1–24.
  31. HU, Y.F. and STOREY, C. 1994. Family of Optimally Conditioned Quasi-Newton Updates for Unconstrained Optimization. JOTA, 83: 421–431.
  32. HUANG, H.Y. 1970. Unified Approach to Quadratically Convergent Algorithms for Function Minimization. JOTA, 5: 405–423.
  33. LI, D. and FUKUSHIMA, M. 2001. A Modified BFGS Method and its Global Convergence in Nonconvex Minimization. J. Compt. Appl. Math., 129: 15–35.
  34. LIU, D.C. and NOCEDAL, J. 1989. On the Limited Memory BFGS Method for Large Scale Optimization. Math. Programming (Series B), 45:503–528.
  35. LUKŠAN, L. and SPEDICATO, E. 2000. Variable Metric Methods for Unconstrained Optimization and Nonlinear Least Squares. J. Compt. Appl. Math., 124: 61–95.
  36. LUKŠAN, L. and VLČEK, J. 2006. Variable Metric Method for Minimization of Partially Separable Nonsmooth Functions. Pacific Journal of Optimization, 2: 59-70.
  37. MASCARENHAS, W.F. 2004. The BFGS Method with Exact Line Searches Fails for Nonconvex Objective Functions. Math. Programming, 99: 49–61.
  38. NOCEDAL, J. 1980. Updating Quasi-Newton Matrices with Limited Storage. Math. Comput., 35: 773–782.
  39. NOCEDAL, J. 1992. Theory of Algorithms for Unconstrained Optimization. Acta Numerica, 1: 199–242.
  40. NOCEDAL, J. and WRIGHT, S.J. 1999. Numerical optimization, Springer, London.
  41. NOCEDAL, J. and YUAN, Y. 1993. Analysis of a Self-Scaling Quasi-Newton Method. Math. Programming, 61: 19–37.
  42. OREN, S.S. and LUENBERGER, D.G. 1974. Self-Scaling Variable Metric (SSVM) Algorithms, Part I: Criteria and Sufficient Conditions for Scaling a Class of Algorithms. Manage. Sci., 20: 845–862.
  43. OREN, S.S. and SPEDICATO, E. 1976. Optimal Conditioning of Self-Scaling Variable Metric Algorithms. Math. Programming, 10: 70–90.
  44. OSBORNE, M.R. and SUN, L.P. 1988. A New Approach to the Symmetric Rank-One Updating Algorithm. Tech. Report, NMO/01, School of Mathematics, Australian National University.
  45. POWELL, M.J.D. 1976. Some Global Convergence Properties of a Variable Metric Algorithm for Minimization without Exact Line Searches. In R.W. Cottle and C.E. Lemke, editors, Nonlinear Programming. SIAM-AMS Proceedings, Vol. IX, SIAM Publications.
  46. POWELL, M.J.D. 1978. Algorithms for Nonlinear Constraints that Use Lagrange Functions. Math. Programming, 14: 224–248.
  47. POWELL, M.J.D. 1986. How Bad are the BFGS and DFP Methods when the Objective Function is Quadratic? Math. Programming, 34: 34–47.
  48. SHANNO, D.F. and PHUA, K.H. 1978. Matrix Conditioning and Nonlinear Optimization. Math. Programming, 14: 149–160.
  49. Spedicato, E. 1978. On a Conjecture of Dixon and Other Topics in Variable Metric Methods. Math. Programming, 15: 123–129.
  50. WEI, Z., YU, G., YUAN, G. and LIAN, Z. 2004. The Superlinear Convergence of a Modified BFGS-Type Method for Unconstrained Optimization. COAP, 29: 315–332.
  51. WOLKOWICZ, H. 1996. An Efficient Region of Optimal Updates for Least Change Secant Methods. SIAM J. Optim., 5: 172–191.
  52. XU, C. and ZHANG, J. 2001. A Survey of Quasi-Newton Equations and Quasi-Newton Methods for Optimization. Annals of Operations research, 103: 213–234.
  53. YABE, H., MARTINEZ, H.J. and TAPIA, R.A. 2004. On Sizing and Shifting the BFGS Update within the Sized-Broyden Family of Secant Updates. SIAM J. Optim., 15: 139–160.
  54. YUAN, Y. 1991. A Modified BFGS Algorithm for Unconstrained Optimization. IMA J. Numerical Analysis, 11: 325–332.
  55. ZHANG, J.Z., DENG, N.Y. and CHEN, L.H. 1999. Quasi-Newton Equation and Related Methods for Unconstrained Optimization. JOTA, 102: 147–167.
  56. ZHANG, L. 2005. A Globally Convergent BFGS Method for Nonconvex Minimization without Line Searches. OMS, 20: 737–747.
  57. ZHANG, Y. and TEWARSON, R.P. 1988. Quasi-Newton Algorithms with Updates from the Preconvex Part of Broyden’s Family. IMA J. Numer. Anal., 8: 487–509.
  58. YUETINGA, Y. and XU, C. 2007. A Compact Limited Memory Method for Large Scale Unconstrained Optimization. European Journal of Operational Research, 180: 48-56.