PRP-Type Direct Search Methods for Unconstrained Optimization

Qunfeng Liu, Wanyou Cheng

.

DOI: 10.4236/am.2011.26096                

Abstract

Three PRP-type direct search methods for unconstrained optimization are presented. The methods adopt three kinds of recently developed descent conjugate gradient methods and the idea of frame-based direct search method. Global convergence is shown for continuously differentiable functions. Data profile and performance profile are adopted to analyze the numerical experiments and the results show that the proposed methods are effective.

Keywords

Direct Search Methods, Descent Conjugate Gradient Methods, Frame-Based Methods, Global Convergence, Data Profile, Performance Profile

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	W. C. Davidon, “Variable Metric Method for Minimization,” SIAM Journal on Optimization, Vol. 1, No. 1, 1992, pp. 1-17. doi:10.1137/0801001
[2]	R. Hooke and T. A. Jeeves, “Direct Search Solution of Numerical and Statistical Problems,” Journal of the ACM, Vol. 8, No. 2, 1961, pp. 212-229. doi:10.1145/321062.321069
[3]	M. J. D. Powell, “Direct Search Algorithms for Optimization Calculations,” Acta Numerica, Vol. 7, No. 1, 1998, pp. 287-336. doi:10.1017/S0962492900002841
[4]	A. Conn, K. Scheinberg and P. L. Toint, “On the Convergence of Derivative-Free Methods for Unconstrained Optimization,” In: M. D. Buchmann and A. Iserles, Eds., Approximation Theory and Optimization, Cambridge University Press, Cambridge, 1997.
[5]	B. Karasozen, “Survey of Trust-Region Derivative Free Optimization Methods,” Journal of Industrial and Management Optimization, Vol. 3, No. 2, 2007, pp. 321-334.
[6]	M. J. D. Powell, “A View of Algorithms for Optimization without Derivatives,” Technical Report DAMTP2007/NA03, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Cambridge, 2007.
[7]	R. M. Lewis and V. Torczon, “Rank Ordering and Positive Bases in Pattern Search Algorithms,” Technical Report 96-71, Institute for Computer Applications in Science and Engineering, NASA Langley Research Center, Hampson, 1996.
[8]	V. Torczon, “On the Convergence of the Multidirectional Search Algorithm,” SIAM Journal on Optimization, Vol. 1, No. 1, 1991, pp. 123-145. doi:10.1137/0801010
[9]	V. Torczon, “On the Convergence of Pattern Search Algorithms,” SIAM Journal on Optimization, Vol. 7, No. 1, 1997, pp. 1-25. doi:10.1137/S1052623493250780
[10]	R. M. Lewis and V. Torczon, “Pattern Search Algorithms for Bound Constrained Minimization,” SIAM Journal on Optimization, Vol. 9, No. 4, 1999, pp. 1082-1099. doi:10.1137/S1052623496300507
[11]	R. M. Lewis and V. Torczon, “Pattern Search Methods for Linearly Constrained Minimization,” SIAM Journal on Optimization, Vol. 10, No. 3, 2000, pp. 917-941. doi:10.1137/S1052623497331373
[12]	C. Audet and J. E. Dennis Jr., “Analysis of Generalized Pattern Searches,” SIAM Journal on Optimization, Vol. 13, No. 3, 2003, pp. 889-903. doi:10.1137/S1052623400378742
[13]	C. Audet and J. E. Dennis Jr., “Mesh Adaptive Direct Search Algorithms for Constrained Optimization,” SIAM Journal on Optimization, Vol. 17, No. 1, 2006, pp. 188- 217. doi:10.1137/040603371
[14]	I. D. Coope and C. J. Price, “On the Convergence of Grid-Based Methods for Unconstrained Optimization,” SIAM Journal on Optimization, Vol. 11, No. 4, 2001, pp. 859-869. doi:10.1137/S1052623499354989
[15]	T. G. Kolda, R. M. Lewis and V. Torczon, “Optimization by Direct Search: New Perspectives on Some Classical and Modern Methods,” SIAM Review, Vol. 45, No. 3, 2003, pp. 385-482. doi:10.1137/S003614450242889
[16]	T. G. Kolda, R. M. Lewis and V. Torczon, “Stationary Results for Generating Set Search for Linearly Constrained Optimization,” SIAM Journal on Optimization, Vol. 17, No. 4, 2006, pp. 943-968. doi:10.1137/S1052623403433638
[17]	R. M. Lewis, A. Shepherd and V. Torczon, “Implementing Generating Set Search Methods for Linearly Constrained Minimization,” SIAM Journal on Scientific Computing, Vol. 29, No. 6, 2007, pp. 2507-2530. doi:10.1137/050635432
[18]	I. D. Coope and C. J. Price, “Frame Based Methods for Unconstrained Optimization,” Journal of Optimization Theory and Applications, Vol. 107, No. 2, 2000, pp. 261- 274. doi:10.1023/A:1026429319405
[19]	I. D. Coope and C. J. Price, “A Direct Search Frame-Based Conjugate Gradients Method,” Journal of Computational Mathematics, Vol. 22, No. 4, 2004, pp. 489-500.
[20]	W. Y. Cheng, “A Two-Term Prp-Based Descent Method,” Numerical Functional Analysis and Optimization, Vol. 28, No. 11-12, 2007, pp. 1217-1230. doi:10.1080/01630560701749524
[21]	W. W. Hager and H. Zhang, “A New Conjugate Gradient Method with Guaranteed Descent and an Efficient Line Search,” SIAM Journal on Optimization, Vol. 16, No. 1, 2005, pp. 170-192. doi:10.1137/030601880
[22]	W. W. Hager and H. Zhang, “A Survey of Nonlinear Conjugate Gradient Methods,” Pacific Journal of Optimization, Vol. 2, 2006, pp. 35-58.
[23]	L. Zhang, W. J. Zou and D. H. Li, “A Descent Modified Polad-Ribiere-Polyak Conjugate Gradient Method and Its Global Convergence,” IMA Journal of Numerical Analysis, Vol. 26, 2006, pp. 629-640. doi:10.1093/imanum/drl016
[24]	N. Andrei, “A Modified Polak-Ribiere-Polyak Conjugate Gradient Algorithm for Unconstrained Optimization,” Optimization: A Journal of Mathematical Programming and Operational Research, Accepted.
[25]	C. Davis, “Theory of Positive Linear Dependence,” American Journal of Mathematics, Vol. 76, No. 4, 1954, pp. 733-746. doi:10.2307/2372648
[26]	E. D. Dolan and J. J. More, “Benchmarking Optimization Software with Performance Profiles,” Mathematical Programming, Vol. 91, No. 2, 2002, pp. 201-213. doi:10.1007/s101070100263
[27]	J. J. More and S. M. Wild, “Benchmarking Derivative-Free Optimization Algorithms,” SIAM Journal on Optimization, Vol. 20, No. 1, 2009, pp. 172-191. doi:10.1137/080724083