Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-09T11:25:37.522Z Has data issue: false hasContentIssue false
  • English
  • Français

Hill-Climbing Algorithm with a Stick for Unconstrained Optimization Problems

Published online by Cambridge University Press:  09 January 2017

Yunqing Huang  and
Kai Jiang
Yunqing Huang*
Affiliation:
Hunan Key Laboratory for Computation and Simulation in Science and Engineering, Key Laboratory of Intelligent Computing & Information Processing of Ministry of Education, School of Mathematics and Computational Science, Xiangtan University, Xiangtan, Hunan 411105, China
Kai Jiang*
Affiliation:
Hunan Key Laboratory for Computation and Simulation in Science and Engineering, Key Laboratory of Intelligent Computing & Information Processing of Ministry of Education, School of Mathematics and Computational Science, Xiangtan University, Xiangtan, Hunan 411105, China
*
*Corresponding author. Email:huangyq@xtu.edu.cn (Y. Q. Huang), kaijiang@xtu.edu.cn (K. Jiang)
*Corresponding author. Email:huangyq@xtu.edu.cn (Y. Q. Huang), kaijiang@xtu.edu.cn (K. Jiang)

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Inspired by the behavior of the blind for hill-climbing using a stick to detect a higher place by drawing a circle, we propose a heuristic direct search method to solve the unconstrained optimization problems. Instead of searching a neighbourhood of the current point as done in the traditional hill-climbing, or along specified search directions in standard direct search methods, the new algorithm searches on a surface with radius determined by the motion of the stick. The significant feature of the proposed algorithm is that it only has one parameter, the search radius, which makes the algorithm convenient in practical implementation. The developed method can shrink the search space to a closed ball, or seek for the final optimal point by adjusting search radius. Furthermore our algorithm possesses multi-resolution feature to distinguish the local and global optimum points with different search radii. Therefore, it can be used by itself or integrated with other optimization methods flexibly as a mathematical optimization technique. A series of numerical tests, including high-dimensional problems, have been well designed to demonstrate its performance.

Keywords

Direct search algorithmstick hill-climbing algorithmsearch radius

MSC classification

Secondary: 90C56: Derivative-free methods and methods using generalized derivatives 90C30: Nonlinear programming

Information

Type
Research Article
Information
Advances in Applied Mathematics and Mechanics , Volume 9 , Issue 2 , April 2017 , pp. 307 - 323
Copyright
Copyright © Global-Science Press 2017 

References

[1] Sun, W. Y. and Yuan, Y., Optimization Theory and Methods: Nonlinear Programming, New York: Springer, 2006.Google Scholar
[2] Conn, A. R., Gould, N. I. M. and Toint, P. L., Trust Region Methods, Philadelphia: SIAM, 2000.CrossRefGoogle Scholar
[3] Nocedal, J. and Wright, S. J., Numerical Optimization, Berlin: Springer-Verlag, 2nd ed., 2006.Google Scholar
[4] Conn, A. R., Scheinberg, K. and Vicente, L. N., Introduction to Derivative-Free Optimization, Philadelphia: SIAM, 2009.Google Scholar
[5] Rios, L. M. and Sahinidis, N. V., Derivative-free optimization: a review of algorithms and comparison of software implementations, J. Global Optim., 56 (2013), pp. 1247–1293.Google Scholar
[6] Powell, M. J. D., UOBYQA: unconstrained optimization by quadratic approximation, Technical Report DAMTP NA2000/14, CMS, University of Cambridge, 2000.Google Scholar
[7] Powell, M. J. D., On trust region methods for unconstrained minimization without derivatives, Technical Report DAMTP NA2002/NA02, CMS, University of Cambridge, February 2002.Google Scholar
[8] Wu, T., Yang, Y., Sun, L., and Shao, H., A heuristic iterated-subspace minimization method with pattern search for unconstrained optimization, Comput. Math. Appl., 58 (2009), pp. 2051–2059.Google Scholar
[9] Zhang, Z., Sobolev seminorm of quadratic functions with applications to derivative-free optimization, Math. Program., 146 (2014), pp. 77–96.Google Scholar
[10] Michalewicz, Z. and Fogel, D. B., How to Solve It: Modern Heuristics, Springer, 2004.Google Scholar
[11] Lecun, Y., Bengio, , Hinton, Y. and Hinton, G., Deep learning, Nature, 521 (2015), pp. 521–436.Google Scholar
[12] Hooke, R. and Jeeves, T. A., “Direct search” solution of numerical and statistical problems, J. ACM, 8 (1961), pp. 212–229.Google Scholar
[13] Lewis, R. M., Torczon, V. and Trosset, M. W., Direct search methods: then and now, J. Comput. Appl. Math., 124 (2000), pp. 191–207.Google Scholar
[14] Nelder, J. A. and Mead, R., A simplex method for function minimization, Comput. J., 7 (1965), pp. 308–313.Google Scholar
[15] Torczon, V., On the convergence of pattern search algorithms, SIAM J. Optim., 7 (1997), pp. 1–25.Google Scholar
[16] Kolda, T. G., Lewis, R. W. and Torczon, V., Optimization by direct search: new perspectives on some classical and modern methods, SIAM Rev., 45 (2003), pp. 385–482.Google Scholar
[17] Dennis, J. E. Jr and Torczon, V., Direct search methods on parallel machines, SIAM J. Optim., 1 (1991), pp. 448–474.Google Scholar
[18] Dieterich, J. M. and Hartke, B., Empirical review of standard benchmark functions using evolutionary global optimization, Appl. Math. 3 (2012), pp. 1552–1564.Google Scholar
[19] Gratton, S., Royer, C. W., Vicente, L. N. and Zhang, Z., Direct search based on probabilistic descent, SIAM J. Optim., 25 (2015), pp. 1515–1541.Google Scholar
[20] Russell, S. J. and Norvig, P., Artificial Intelligence: a Modern Approach, 3rd ed., Prentice Hall, 2010.Google Scholar
[21] Bäck, T., Evolutionary Algorithms in Theory And Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms, Oxford University Press, 1996.Google Scholar
[22] Dennis, J. E. Jr and Woods, D. J., Optimization on microcomputers: The Nelder-Mead simplex algorithm, In: New Computing Environments: Microcomputers in Large-Scale Computing, Wouk, A. ed., Philadelphia: SIAM, 1987.Google Scholar