Higher Order Iteration Schemes for Unconstrained Optimization

.
DOI: 10.4236/ajor.2011.13011   PDF   HTML     5,794 Downloads   9,793 Views   Citations

Abstract

Using a predictor-corrector tactic, this paper derives new iteration schemes for unconstrained optimization. It yields a point (predictor) by some line search from the current point; then with the two points it constructs a quadratic interpolation curve to approximate some ODE trajectory; it finally determines a new point (corrector) by searching along the quadratic curve. In particular, this paper gives a global convergence analysis for schemes associated with the quasi-Newton updates. In our computational experiments, the new schemes using DFP and BFGS updates outperformed their conventional counterparts on a set of standard test problems.

Share and Cite:

Y. Shi and P. Pan, "Higher Order Iteration Schemes for Unconstrained Optimization," American Journal of Operations Research, Vol. 1 No. 3, 2011, pp. 73-83. doi: 10.4236/ajor.2011.13011.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1] W. C. Davidon, “Variable Metric Method for Minimization,” Technical Report ANLC5990 (Revised), Argonne National Laboratory, Argonne, 1959.
[2] W. C. Davidon, “Variable Metric Method for Minimization,” SIAM Journal on Optimization, Vol. 1, No. 1, 1991, pp. 1-17. doi:10.1137/0801001
[3] R. Fletcher and M. J. D. Powell, “A Rapidly Convergent Descent Method for Minimization,” The Computer Journal, Vol. 6, No. 2, 1963, pp. 163-168.
[4] C. G. Broyden, “The Convergence of a Class of Double Rank Minimization Algorithms 2. The New Algorithms,” IMA Journal of Applied Mathematics, Vol. 6, No. 3, 1970, pp. 222-231. doi:10.1093/imamat/6.3.222
[5] R. Fletcher, “A New Approach to Variable Matric Algorithm,” The Computer Journal, Vol. 13, No. 3, 1970, pp. 317-322. doi:10.1093/comjnl/13.3.317
[6] C. G. Broyden, “The Convergence of a Class of Double Rank Minimization Algorithms 1. General Consideration,” IMA Journal of Applied Mathematics, Vol. 6, No. 1, 1970, pp. 76-90. doi:10.1093/imamat/6.1.76
[7] D. Goldfarb, “A Family of Variable Metric Methods Derived by Variational Means,” Mathematics of Computation, Vol. 24, No. 109, 1970, pp. 23-26. doi:10.1090/S0025-5718-1970-0258249-6
[8] D. F. Shanno, “Conditioning of Quasi-Newton Methods for Function on Minimization,” Mathematics of Computation, Vol. 24, No. 111, 1970, pp. 647-656. doi:10.1090/S0025-5718-1970-0274029-X
[9] K. J. Arrow, L. Hurwicz and H. Uzawa, “Studies in Linear and Nonlinear Programming,” Stanford University Press, Palo Alto, 1958.
[10] F. H. Branin and S. K. Hoo, “A Method for Finding Multiple Extreme of a Function of n Variables,” In: F. A. Lootsman, Ed., Numerical Method for Nonlinear Optimization, Academic Press, Cambridge, 1972.
[11] P. Q. Pan, “Differential Equation Methods for Unconstrained Optimization,” Nanjing University Journal of Computational Mathematics, in Chinese, Vol. 4, 1982, pp. 338-349.
[12] P. Q. Pan, “New ODE Methods of Equality Constrained Optimization (1): Equations,” Journal of Computational Mathematics, Vol. 10, No. 1, 1992, pp. 77-92.
[13] P. Q. Pan, “New ODE Methods for Equality Constrained Optimization (2): Algorithm,” Journal of Computational Mathematics, Vol. 10, No. 2, 1992, pp. 129-146.
[14] J. Nocedal and S. J. Wright, “Numerical Optimization,” Science Press, Beijing, 2006.
[15] J. J. More, B. S. Garbow and K. E. Hillstrome, “Testing Unconstrained Optimization Software,” ACM Transactions on Mathematical Software, Vol. 7, No. 1, 1981, pp. 17-41. doi:10.1145/355934.355936
[16] N. Andrei, “Unconstrained Optimization Test Function,” Advanced Modeling and Optimization, Vol. 10, No. 1, 2008, pp. 147-161.

  
comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.