Higher Order Iteration Schemes for Unconstrained Optimization

Yangyang Shi, Pingqi Pan
DOI: 10.4236/ajor.2011.13011                

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.

Keywords

Unconstrained Optimization, Iteration Scheme, ODE Method, Quasi-Newton Update, Convergence Analysis

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.