×

CGRS – an advanced hybrid method for global optimization of continuous functions closely coupling extended random search and conjugate gradient method. (English) Zbl 1390.90442

Summary: A new hybrid method for global optimization of continuous functions is proposed. It is a combination of an extended random search method and a descent method. Random search is used as the global search strategy. A newly developed distribution-based region control makes use of already detected local minima to refine this search strategy. The approach resembles classical step size control in deterministic optimization. The descent method is embedded as a local search strategy for the detection of local minima. A special realization of this approach is presented in this paper and called CGRS. In CGRS the conjugate gradient method is utilized as descent method. The proof of global convergence in probability for CGRS is given and extended to other descent methods used in the hybrid optimization approach. In order to demonstrate the numerical properties of the approach test sets of multidimensional non-convex optimization problems are solved. The results are compared to well-established hybrid methods for global optimization. The new algorithm shows a high success rate with good and adjustable solution precision. Parameter tuning is not necessary, but of course possible. The new method proves to be efficient in terms of computational costs.

MSC:

90C26 Nonconvex programming, global optimization
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Horst, R.; Pardalos, P. M.; Romeijn, H. E., (Handbook of Global Optimization, no. 2 (2002), Springer)
[2] Floudas, C. A.; Gounaris, C. E., A review of recent advances in global optimization, J. Global Optim., 45, 1, 3-38 (2009) · Zbl 1180.90245
[3] Zhigljavsky, A.; Zilinskas, A., (Stochastic Global Optimization. Stochastic Global Optimization, Springer Optimization and Its Applications (2010), Springer)
[4] Polak, E., Optimization: Algorithms and Consistent Approximations (1997), Springer-Verlag New York, Inc.: Springer-Verlag New York, Inc. New York, NY, USA · Zbl 0899.90148
[5] Geiger, C.; Kanzow, C., Numerische Verfahren Zur Loesung Unrestringierter Optimierungsaufgaben (1999), Springer: Springer Berlin, Heidelberg, New York · Zbl 0934.65062
[6] Conn, A. R.; Scheinberg, K.; Vicente, L. N., Introduction to Derivative-Free Optimization (2009), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA, USA · Zbl 1163.49001
[7] Box, M. J., A new method of constrained optimization and a comparison with other methods, Comput. J., 8, 1, 42-52 (1965) · Zbl 0142.11305
[8] Powell, M. J.D., Direct search algorithms for optimization calculations, Acta Numer., 7, 287-336 (1998) · Zbl 0911.65050
[9] Torczon, V., On the convergence of pattern search algorithms, SIAM J. Optim., 7, 1, 1-25 (1997) · Zbl 0884.65053
[10] Rios, L.; Sahinidis, N., Derivative-free optimization: a review of algorithms and comparison of software implementations, J. Global Optim., 56, 3, 1247-1293 (2013) · Zbl 1272.90116
[11] Rechenberg, I., Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (1973), Frommann-Holzboog
[12] Schwefel, H., Evolutionsstrategie und Numerische Optimierung, Doktorarbeit (1975), Technische Universitaet Berlin: Technische Universitaet Berlin Berlin
[13] Beyer, H.-G.; Schwefel, H.-P., Evolution strategies: A comprehensive introduction, Nat. Comput., 1, 1, 3-52 (2002) · Zbl 1014.68134
[14] Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 671-680 (1983) · Zbl 1225.90162
[15] Henderson, A. J.D.; Jacobson, S. H., The theory and practice of simulated annealing, Handb. Metaheuristics, 57, 1, 287-319 (2003) · Zbl 1102.90381
[16] J. Kennedy, R. Eberhart, Particle swarm optimization, in: IEEE International Conference on Neural Networks, 1995. Proceedings, Vol. 4, 1995, pp. 1942-1948.; J. Kennedy, R. Eberhart, Particle swarm optimization, in: IEEE International Conference on Neural Networks, 1995. Proceedings, Vol. 4, 1995, pp. 1942-1948.
[17] Poli, R., Analysis of the publications on the applications of particle swarm optimisation, J. Artif. Evol. Appl., 2008, 4:1-4:10 (2008)
[18] Anderson, R. L., Recent advances in finding best operating conditions, J. Amer. Statist. Assoc., 48, 264, 789-798 (1953)
[19] Solis, F. J.; Wets, R. J.B., Minimization by random search techniques, Math. Oper. Res., 6, 1, 19-30 (1981) · Zbl 0502.90070
[20] Andradottir, S., A review of random search methods, (Handbook of Simulation Optimization. Handbook of Simulation Optimization, International Series in Operations Research & Management Science, vol. 216 (2014)), 277-292
[21] Moral, P. D.; Miclo, L., On the convergence and applications of generalized simulated annealing, SIAM J. Control Optim., 37, 1222-1250 (1999) · Zbl 0928.60046
[22] Faigle, U.; Kern, W., Note on the convergence of simulated annealing algorithms, SIAM J. Control Optim., 29, 1, 153-159 (1991) · Zbl 0736.90061
[23] Spall, J. C., Introduction to Stochastic Search and Optimization (2003), John Wiley & Sons, Inc.: John Wiley & Sons, Inc. New York, NY, USA · Zbl 1088.90002
[24] Garcia-Palomares, U. M.; Gonzalez-Casta no, F. J.; Burguillo-Rial, J. C., A combined global & local search (cgls) approach to global optimization, J. Global Optim., 34, 3, 409-426 (2006) · Zbl 1149.90426
[25] Olensek, J.; Bürmen, Á.; Puhan, J.; Tuma, T., DESA: a new hybrid global optimization method and its application to analog integrated circuit sizing, J. Global Optim., 44, 1, 53-77 (2009) · Zbl 1172.90494
[26] Wang, Y.-J.; Zhang, J.-S., An efficient algorithm for large scale global optimization of continuous functions, J. Comput. Appl. Math., 206, 2, 1015-1026 (2007) · Zbl 1117.65095
[27] Majig, M.-A.; Hedar, A.-R.; Fukushima, M., A hybrid evolutionary algorithm for global optimization, Optim. Optimal Control, 2010, 39, 169-184 (2010) · Zbl 1204.90076
[28] M. Noel, T. Jannett, Simulation of a new hybrid particle swarm optimization algorithm, in: Proceedings of the Thirty-Sixth Southeastern Symposium on System Theory, 2004. 2004, pp. 150-153.; M. Noel, T. Jannett, Simulation of a new hybrid particle swarm optimization algorithm, in: Proceedings of the Thirty-Sixth Southeastern Symposium on System Theory, 2004. 2004, pp. 150-153.
[29] Yiu, K. F.C.; Liu, Y.; Teo, K. L., A hybrid descent method for global optimization, J. Global Optim., 28, 2, 229-238 (2004) · Zbl 1114.90163
[30] Wang, Y.-J.; Zhang, J.-S.; Zhang, Y.-F., An effective and efficient two stage algorithm for global optimization, (Proceedings of the 4th International Conference on Advances in Machine Learning and Cybernetics. Proceedings of the 4th International Conference on Advances in Machine Learning and Cybernetics, ICMLC’05 (2006), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 487-496
[31] Hedar, A.; Fukushima, M., Hybrid simulated annealing and direct search method for nonlinear unconstrained global optimization, Optim. Methods Softw., 17, 891-912 (2002) · Zbl 1065.90081
[32] Salhi, S.; Queen, N. M., A hybrid algorithm for identifying global and local minima when optimizing functions with many minima, European J. Oper. Res., 155, 1, 51-67 (2004) · Zbl 1053.90058
[33] Martín-Clemente, R.; Puntonet, C. G.; Acha, J. I., A conjugate gradient method and simulated annealing for blind separation of sources, (IWANN’01: Proceedings of the 6th International Work-Conference on Artificial and Natural Neural Networks (2001), Springer-Verlag: Springer-Verlag London, UK), 810-817 · Zbl 0982.68856
[34] Li, Z.; Cedric Yiu, K. F.; Feng, Z., A hybrid descent method with genetic algorithm for microphone array placement design, Appl. Soft Comput., 13, 3, 1486-1490 (2013)
[35] Zhang, Y.; Wang, L.; Wu, Q., Differential annealing for global optimization, (Tan, Y.; Shi, Y.; Ji, Z., Advances in Swarm Intelligence. Advances in Swarm Intelligence, Lecture Notes in Computer Science, vol. 7331 (2012), Springer Berlin Heidelberg), 382-389
[36] Luis Guarracino, D. V., A hybrid simulated annealing and gradient-based algorithm for the estimation of unsaturated soil parameters, Mec. Comput., XXVI, 2061-2071 (2007)
[37] Wan, W.; Birch, J. B., An improved hybrid genetic algorithm with a new local search procedure, J. Appl. Math., 2013 (2013)
[38] Kiran, M. S.; Gndz, M.; Baykan, m. K., A novel hybrid algorithm based on particle swarm and ant colony optimization for finding the global minimum, Appl. Math. Comput., 219, 4, 1515-1521 (2012) · Zbl 1291.90187
[39] E. Zhou, J. Hu, Combining gradient-based optimization with stochastic search, in: Simulation Conference (WSC), Proceedings of the 2012 Winter, 2012, pp. 1-12.; E. Zhou, J. Hu, Combining gradient-based optimization with stochastic search, in: Simulation Conference (WSC), Proceedings of the 2012 Winter, 2012, pp. 1-12.
[40] Vaz, A. I.; Vicente, L. N., A particle swarm pattern search method for bound constrained global optimization, J. Global Optim., 39, 2, 197-219 (2007) · Zbl 1180.90252
[41] Rinnooy Kan, A. H.G.; Timmer, G. T., Stochastic global optimization methods part II: Multi level methods, Math. Program., 39, 1, 57-78 (1987) · Zbl 0634.90067
[42] Locatelli, M.; Schoen, F., Global optimization based on local searches, Ann. Oper. Res., 240, 1, 251-270 (2016) · Zbl 1342.90149
[43] Rastrigin, L., The convergence of the random search method in the extremal control of a many parameter system, Autom. Remote Control, 24, 10, 1337-1342 (1963)
[44] Karnopp, D. C., Random search techniques for optimization problems, Automatica, 1, 2-3, 111-121 (1963)
[45] Zabinsky, Z. B., Random search algorithms, (Cochran, J. J., Wiley Encyclopedia of Operations Research and Management Science (2009), John Wiley & Sons), 1-16
[46] Zabinsky, Z.; Smith, R.; McDonald, J.; Romeijn, H.; Kaufman, D., Improving hit-and-run for global optimization, J. Global Optim., 3, 2, 171-192 (1993) · Zbl 0784.90084
[47] Zhigljavsky, A.; Pintér, J., (Theory of Global Random Search. Theory of Global Random Search, Mathematics and its Applications (1991), Springer Netherlands)
[48] Regis, R. G., Convergence guarantees for generalized adaptive stochastic search methods for continuous global optimization, European J. Oper. Res., 207, 3, 1187-1202 (2010) · Zbl 1209.90295
[49] Hestenes, M. R.; Stiefel, E., Methods of conjugate gradients for solving linear systems, J. Res. Natl. Bur. Stand., 49, 409-436 (1952) · Zbl 0048.09901
[50] Pytlak, R., (Conjugate Gradient Algorithms in Nonconvex Optimization. Conjugate Gradient Algorithms in Nonconvex Optimization, Nonconvex Optimization and Its Applications (2008), Springer: Springer Dordrecht) · Zbl 1171.49002
[51] Golub, G. H.; Van Loan, C. F., Matrix Computations (1996), Johns Hopkins University Press: Johns Hopkins University Press Baltimore, MD, USA · Zbl 0865.65009
[52] Dai, Y.-H., Nonlinear Conjugate Gradient Methods, 21-42 (2000), Shanghai Science and Technology Publisher, (2)
[53] Hager, W.; Zhang, H., A survey of nonlinear conjugate gradient methods, Pac. J. Optim., 2, 35-58 (2006) · Zbl 1117.90048
[54] Wolfe, P., Convergence conditions for ascent methods, SIAM Rev., 11, 2, 226-235 (1969) · Zbl 0177.20603
[55] Shi, Z.-J.; Guo, J., A new family of conjugate gradient methods, J. Comput. Appl. Math., 224, 1, 444-457 (2009) · Zbl 1155.65049
[56] Zhang, L.; Zhou, W.; Li, D., Global convergence of the dy conjugate gradient method with armijo line search for unconstrained optimization problems, Optim. Methods Softw., 22, 3, 511-517 (2007) · Zbl 1133.65035
[57] Dai, Y.; Yuan, Y., A class of globally convergent conjugate gradient methods, Sci. China Ser. A: Math., 46, 251-261 (2003) · Zbl 1217.90159
[58] Maple programming guide, by Maplesoft, a division of Waterloo Maple Inc., Toronto 2011-2015.; Maple programming guide, by Maplesoft, a division of Waterloo Maple Inc., Toronto 2011-2015.
[59] MATLAB documentation, by The MathWorks Inc., Natick, Massachusetts, 2015.; MATLAB documentation, by The MathWorks Inc., Natick, Massachusetts, 2015.
[60] Shiriaev, D., (Fast Automatic Differentiation: An Overview. Fast Automatic Differentiation: An Overview, Lecture Notes in Mathematical Modelling and Scientific Computations (1993))
[61] Griewank, A.; Walther, A., Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation (2008), Society for Industrial and Applied Mathematics · Zbl 1159.65026
[62] Stoer, J., Numerische Mathematik 1 (1999), Springer: Springer Berlin
[63] Gill, P. E.; Murray, W.; Saunders, M. A.; Wright, M. H., Computing forward-difference intervals for numerical optimization, SIAM J. Sci. Stat. Comput., 4, 2, 310-321 (1983) · Zbl 0514.65044
[64] Fornberg, B., Numerical differentiation of analytic functions, ACM Trans. Math. Software, 7, 4, 512-526 (1981) · Zbl 0465.65012
[65] Stepleman, N. W.R. S., Adaptive numerical differentiation, Math. Comp., 33, 1257-1264 (1979) · Zbl 0437.65018
[66] R. Callies, Entwurfsoptimierung und optimale Steuerung. Differential-algebraische Systeme, Mehrgitter-Mehrzielansätze und numerische Realisierung, Habilitationsschrift, Zentrum Mathematik, Technische Universität München, 2000.; R. Callies, Entwurfsoptimierung und optimale Steuerung. Differential-algebraische Systeme, Mehrgitter-Mehrzielansätze und numerische Realisierung, Habilitationsschrift, Zentrum Mathematik, Technische Universität München, 2000.
[67] Fletcher, R.; Reeves, C. M., Function minimization by conjugate gradients, Comput. J., 7, 2, 149-154 (1964) · Zbl 0132.11701
[68] Polak, E.; Ribire, G., Note sur la convergence de mthodes de directions conjugues, Rev. Francaise Inf. Rech. Oper., 16, 35-43 (1969)
[69] Dai, Y. H.; Yuan, Y., A nonlinear conjugate gradient method with a strong global convergence property, SIAM J. Optim., 10, 177-182 (1999) · Zbl 0957.65061
[70] Hager, W. W.; Zhang, H., Algorithm 851: CG DESCENT, a conjugate gradient method with guaranteed descent, ACM Trans. Math. Software (2006) · Zbl 1346.90816
[71] Yu, G.; Guan, L.; Chen, W., Spectral conjugate gradient methods with sufficient descent property for large-scale unconstrained optimization, Optim. Methods Softw., 23, 275-293 (2008) · Zbl 1279.90166
[72] Johnson, N.; Kotz, S.; Balakrishnan, N., (Continuous Univariate Distributions. Continuous Univariate Distributions, Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics, no. Bd. 2 (1995), Wiley & Sons)
[73] Hager, W. W.; Zhang, H., A new conjugate gradient method with guaranteed descent and an efficient line search, SIAM J. Optim., 16, 170-192 (2005) · Zbl 1093.90085
[74] Y.H.D.C.X. Kou, New conjugate gradient methods with an efficient nonmonotone line search, Research Report, LSEC, ICMSEC, Academy of Methematics and Systems Science, 2010.; Y.H.D.C.X. Kou, New conjugate gradient methods with an efficient nonmonotone line search, Research Report, LSEC, ICMSEC, Academy of Methematics and Systems Science, 2010.
[75] Hager, W. W.; Zhang, H., The limited memory conjugate gradient method, SIAM J. Optim., 23, 4, 2150-2168 (2013) · Zbl 1298.90129
[76] Source Code of CG-Descent Version 6.8, (accessed 09.07.16) on page http://users.clas.ufl.edu/hager/papers/Software/; Source Code of CG-Descent Version 6.8, (accessed 09.07.16) on page http://users.clas.ufl.edu/hager/papers/Software/
[77] Szu, R. H. H., Fast simulated annealing, Phys. Lett. A, 122, 3, 157-162 (1987)
[78] Moler, C., Numerical Computing with MATLAB (2004), Society for Industrial and Applied Mathematics · Zbl 1059.68162
[79] Nocedal, J.; Wright, S. J., Numerical Optimization (2000), Springer
[80] Billingsley, P., (Convergence of Probability Measures. Convergence of Probability Measures, Wiley Series in Probability and Mathematical Statistics (1968), Wiley: Wiley New York) · Zbl 0172.21201
[81] Zoutendijk, G., Nonlinear programming, computational methods, (Abadie, J., Integer and Nonlinear Programming (1970), North-Holland: North-Holland Amsterdam), 37-86 · Zbl 0336.90057
[82] Conn, A. R.; Scheinberg, K.; Vicente, L. N., Global convergence of general derivative-free trust-region algorithms to first- and second-order critical points, SIAM J. Optim., 20, 1, 387-415 (2009) · Zbl 1187.65062
[83] Garmanjani, R.; Judice, D.; Vicente, L. N., Trust-region methods without using derivatives: worst case complexity and the nonsmooth case, SIAM J. Optim., 26, 4, 1987-2011 (2016) · Zbl 1348.90572
[84] Powell, M., On trust region methods for unconstrained minimization without derivatives, Math. Program., 97, 3 (2003) · Zbl 1106.90382
[85] Floudas, C.; Pardalos, P., (A Collection of Test Problems for Constrained Global Optimization Algorithms. A Collection of Test Problems for Constrained Global Optimization Algorithms, Lecture Notes in Computer Science (1990), Springer-Verlag) · Zbl 0718.90054
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.