Higher Order Iteration Schemes for Unconstrained Optimization

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.

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

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

Cite this paper

nullY. 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.

nullY. Shi and P. Pan, "Higher Order Iteration Schemes for Unconstrained Optimization,"

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.

[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.