A multi-sequential number-theoretic optimization algorithm using clustering methods

Abstract

A multi-sequential number-theoretic optimization method based on clustering was developed and applied to the optimization of functions with many local extrema. Details of the procedure to generate the clusters and the sequential schedules were given. The algorithm was assessed by comparing its performance with generalized simulated annealing algorithm in a difficult instructive example and a D-optimum experimental design problem. It is shown the presented algorithm to be more effective and reliable based on the two examples.

Keywords

retention ratio / cluster / contraction / local search

References

[1] AvrielMNonlinear Programming Analysis and Methods [M], 1976, Englewood Cliffs, Prentice-Hall

[2] NashJ CNonlinear Parameter Estimation: an Intergrated System in BASIC [M], 1987, New York, Deker

[3] HorstR, TuyHGlobal Optimization [M], 1990, Berlin, Springer

[4] BertmasD, TsitsiklisJ. Simulated annealing [J]. Statis Sci, 1993, 8(1): 10-15

[5] RubinstainR YMonte Carlo Optimization, Simulation and Sensitivity of Queuing Networks [M], 1986, New York, Wiley

[6] NiederreiterHA quasi-monte carlo method for the approximate of extreme values of a function[A]. Studies in Pure Math[C], 1983, Basel, Birkhauser

[7] FangK T, WangY. A unified approach to maximum likelihood estimation [J]. Chinese J Appl Probab Statist, 1990, 6(4): 412-418(in Chinese)

[8] NiederreiderH, PeartP. Localization of search in quasi-monte carlo methods for global optimization [J]. SIAM J Sci Statist Comput, 1986, 7(6): 660-664

[9] FangK T, WangY. A sequential algorithm for solving a system of nonlinear equations [J]. J Comput Math, 1991, 9(11): 9-16

[10] ZhangL, LiangY Z, YuR Q, et al.. Sequential number-theoretic optimization method applied to chemical quantitative analysis [J]. J Chemometrics, 1997, 11(3): 267-281

[11] GongF, CuiH, ZhangL, et al.. An improved algorithm of sequential number-theoretic optimization based on clustering technique [J]. Chemometrics Intel Lab Syst, 1999, 45(1–2): 339-346

[12] Rinny KanA H J, TimmerG T. Stochastic global optimization methods part II: multi lever methods [J]. Mathematical Programming, 1987, 39(1): 57-78

[13] BohachevskyI O, JonsonM E, SteinM L. Generalized simulated annealing for function optimization [J]. Technometrics, 1986, 28(2): 209-217

[14] FangK T, WangYNumber-theoretic Methods in Statistics [M], 1993, London, Chapman and Hall

[15] HaltonJ H. On the efficiency of certain quasi-random sequences of points in evaluating multi-dimentional integrals [J]. Numer Math, 1960, 2(1): 84-90

[16] NieterreiderH. Quasi-monte carlo methods and pseudo-random numbers [J]. Bull Amer Math Soc, 1978, 84(4): 957-1041

[17] Rinny KanA H J, TimmerG T. Stochastic global optimization methods part I: clustering methods [J]. Mathematical Programming, 1987, 39(1): 27-56

[18] AtkinsonA C, BogackaB. Bogacki, MB D-and T-optimum designs for the kinetics of a reversible chemical reaction [J]. Chemom Lab Syst, 1998, 43(2): 185-198

[19] XuQ S, LiangY Z, FangK T. The effects of different experimental designs on parameter estimation in the kinetics of a reversible chemical reaction [J]. Chemometrics Intel Lab Syst, 2000, 52(2): 155-166

[20] ChernoffH. Locally optimal designs for estimating parameters [J]. Ann Math Statist, 1953, 24(4): 586-602