×

zbMATH — the first resource for mathematics

A new constructing auxiliary function method for global optimization. (English) Zbl 1145.90434
Summary: A new auxiliary function method based on the idea which executes a two-stage deterministic search for global optimization is proposed. Specifically, a local minimum of the original function is first obtained, and then a stretching function technique is used to modify the objective function with respect to the obtained local minimum. The transformed function stretches the function values higher than the obtained minimum upward while it keeps the ones with lower values unchanged. Next, an auxiliary function is constructed on the stretched function, which always descends in the region where the function values are higher than the obtained minimum, and it has a stationary point in the lower area. We optimize the auxiliary function and use the found stationary point as the starting point to turn to the first step to restart the search. Repeat the procedure until termination. A theoretical analysis is also made. The main feature of the new method is that it relaxes significantly the requirements for the parameters. Numerical experiments on benchmark functions with different dimensions (up to 50) demonstrate that the new algorithm has a more rapid convergence and a higher success rate, and can find the solutions with higher quality, compared with some other existing similar algorithms, which is consistent with the analysis in theory.

MSC:
90C26 Nonconvex programming, global optimization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Powell, M.J.D., On the convergence of the variable metric algorithms, Journal of the institute of mathematics and its applications, 7, 21-36, (1971) · Zbl 0217.52804
[2] Dennis, J.E.; Schnabel, R.B., Numerical methods for unconstrained optimization and nonlinear equations, (1983), Prentice-Hall Englewood Cliffs, NJ · Zbl 0579.65058
[3] Fletcher, R., Practical methods of optimization, (1987), Wiley New York · Zbl 0905.65002
[4] Horst, R.; Tuy, H., Global optimization - deterministic approaches, (1996), Springer-Verlag New York · Zbl 0867.90105
[5] Boender, C.G.E.; Rinnooy Kan, A.H.G., A Bayesian analysis of the number of cells of a multinomial distribution, Statistician, 32, 240-248, (1983)
[6] Rinnooy Kan, A.H.G.; Timmer, G.T., Stochastic global optimization methods, part I: clustering methods, Mathematical programming, 39, 27-56, (1987) · Zbl 0634.90066
[7] Rinnooy Kan, A.H.G.; Timmer, G.T., Stochastic global optimization methods, part II: multi-level methods, Mathematical programming, 39, 57-78, (1987) · Zbl 0634.90067
[8] Boender, C.G.E.; Rinnooy Kan, A.G.H., Bayesian stopping rules for multistart global optimization methods, Mathematical programming: series A and B, 37, 1, 59-80, (1987) · Zbl 0626.90079
[9] Holland, J.H., Genetic algorithms, Scientific American, 4, 44-50, (1992)
[10] Kirkpatrick, S.; Gelatt, C.D; Vecchi, M.P., Optimization by simulate annealing, Science, 220, 671-680, (1983) · Zbl 1225.90162
[11] R.C. Eberhart, J. Kennedy, A new optimizer suing particle swarm theory, in: Proc. 6th Symp. Micro Machine and Human Science, Nagoy, Japan, 1995, pp. 39-43
[12] Panos, M.; Pardalos, H.; Edwin, Romeijn; Hoang, Tuy, Recent developments and trends in global optimization, Journal of computational and applied mathematics, 124, 1-2, 209-228, (2000) · Zbl 0969.90067
[13] Ge, R., A filled function method for finding a global minimizer of a function of several variables, Mathematical programming, 46, 191-204, (1990) · Zbl 0694.90083
[14] Ge, R.; Qin, Y., The globally convexized filled functions for global optimization, Applied mathematics and computation, 35, 131-158, (1990) · Zbl 0752.65052
[15] Levy, A.; Montalvo, A., The tunneling algorithm for the global minimization of functions, SIAM journal of scientific and statistical computing, 6, 15-29, (1985) · Zbl 0601.65050
[16] Kostuwichi, J.; Pidla, L., Diffusion equation method of global minimization: performance for standard test functions, Journal of optimization theory and applications, 69, 2, 97-126, (1991)
[17] Kostrowicki, J.; Piela, L.; Cherayil, B.J.; Scheraga, A., Performance of the diffusion equation method in searches for optimum structures of clusters of lennard – jones atoms, Journal of physical chemistry, 95, 4113-4119, (1991)
[18] T. Coleman, D. Shalloway, Z. Wu, Isotropic effective energy simulated annelaing searches for low energy molecular cluster states, Technical Report CTC-92-Tr113, Center for Theory and Simulation in Science and Engineering, Cornell University, 1992, 1993 · Zbl 0785.90098
[19] Cetin, B.C.; Barhne, J.; Burdick, J.W., Terminal repeller unconstrained subenergy tunneling (TRUST) for fast global optimization, Journal of optimization theory and applications, 77, 1, 97-126, (1993) · Zbl 0801.49001
[20] Pinaki, RoyChowdhury; Singh, Y.P.; Chansarkar, R.A., Hybridization of gradient descent algorithm with dynamic tunneling method for global optimization, IEEE transaction on system, man and cybernetics, 30, 3, 384-390, (2001)
[21] Parsopoulos, K.E.; Plagianakos, V.P.; Magoulas, G.D.; Vrahatis, M.N., Improving particle swarm optimizer by function “stretching”, (), 445-457 · Zbl 1015.90064
[22] Parsopoulos, K.E.; Vrahatis, M.N., On the computation of all global optimizers through particle swarm optimization, IEEE transactions on evolutionary computation, 8, 211-223, (2004)
[23] Liu, X., The impelling function method applied to global optimization, Applied mathematics and computation, 151, 745-754, (2004) · Zbl 1055.65077
[24] Liu, X.; Xu, W., A new filled function applied to global optimization, Computers & operation research, 31, 61-80, (2004) · Zbl 1039.90099
[25] Wang, X.L.; Zhou, G.B., A new filled function for unconstrained global optimization, Applied mathematics and computation, 174, 419-429, (2006) · Zbl 1120.90042
[26] Yang, R.J.; Shang, Y.L., A new filled function for unconstrained global optimization, Applied mathematics and computation, 173, 501-512, (2006) · Zbl 1094.65063
[27] Zhu, W.; Fu, Q., A sequential convexification method (SCM) for continuous global optimization, Journal of global optimization, 26, 167-182, (2003) · Zbl 1049.90069
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.