×

A modification of the DIRECT method for Lipschitz global optimization for a symmetric function. (English) Zbl 1279.65076

Summary: We consider a global optimization problem for a symmetric Lipschitz continuous function. An efficient modification of the well-known DIRECT (DIviding RECTangles) method called SymDIRECT is proposed for solving this problem. The method is illustrated and tested on several standard test functions. The application of this method to solving complex center-based clustering problems for the data having only one feature is particularly presented.

MSC:

65K05 Numerical mathematical programming methods
90C26 Nonconvex programming, global optimization
90C27 Combinatorial optimization
65C60 Computational problems in statistics (MSC2010)
62H30 Classification and discrimination; cluster analysis (statistical aspects)
90C56 Derivative-free methods and methods using generalized derivatives
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alolyan, I.: A new exclusion test for finding the global minimum. J. Comput. Appl. Math. 200, 491-502 (2007) · Zbl 1113.65060 · doi:10.1016/j.cam.2006.01.028
[2] Auger, A., Doerr, B.: Theory of Randomized Search Heuristics, Vol. 1 of Theoretical Computer Science. World Scientific, Danvers (2011) · Zbl 1233.90005
[3] Chiter, L.: Direct algorithm: a new definition of potentially optimal hyperrectangles. Appl. Math. Comput. 179, 742-749 (2006) · Zbl 1102.65067 · doi:10.1016/j.amc.2005.11.127
[4] Chiter, L.: A new sampling method in the direct algorithm. Appl. Math. Comput. 175, 297-306 (2006) · Zbl 1088.65057 · doi:10.1016/j.amc.2005.07.051
[5] di Serafino, D., Liuzzi, G., Piccialli, V., Riccio, F., Toraldo, G.: A modified dividing rectangles algorithm for a problem in astrophysics. J. Optim. Theory Appl. 151, 175-190 (2011) · Zbl 1226.90082 · doi:10.1007/s10957-011-9856-9
[6] Evtushenko, Y.G.: Numerical Optimization Techniques (Translations Series in Mathematics and Engineering). Springer, Berlin (1985) · doi:10.1007/978-1-4612-5022-7
[7] Finkel, D.E.: DIRECT Optimization Algorithm User Guide, Center for Research in Scientific Computation. North Carolina State University, 2003, http://www4.ncsu.edu/definkel/research/index.html · Zbl 1222.90081
[8] Finkel, D.E., Kelley, C.T.: Convergence analysis of the direct algorithm crsc-tr04-28. Center for Research in Scientific Computation, North Carolina State University, Technical Report (2004) · Zbl 1180.90245
[9] Finkel, D.E., Kelley, C.T.: Additive scaling and the DIRECT algorithm. J. Glob. Optim. 36, 597-608 (2006) · Zbl 1142.90488 · doi:10.1007/s10898-006-9029-9
[10] Floudas, C.A., Gounaris, C.E.: A review of recent advances in global optimization. J. Glob. Optim. 45, 3-38 (2009) · Zbl 1180.90245 · doi:10.1007/s10898-008-9332-8
[11] Gablonsky, J. M.: Direct version 2.0, Technical report, Center for Research in Scientific Computation. North Carolina State University (2001) · Zbl 1198.90397
[12] Gablonsky, J.M.: Modifications of the DIRECT Algorithm, Ph.D. thesis, North Carolina State University (2001) · Zbl 1039.90049
[13] Gablonsky, J.M., Kelley, C.T.: A locally-biased form of the direct algorithm. J. Glob. Optim. 21, 27-37 (2001) · Zbl 1039.90049 · doi:10.1023/A:1017930332101
[14] Gan, G., Ma, C., Wu, J.: Data Clustering: Theory, Algorithms, and Applications. SIAM, Philadelphia (2007) · Zbl 1185.68274 · doi:10.1137/1.9780898718348
[15] Gaviano, M., Lera, D.: A global minimization algorithm for Lipschitz functions. Optim. Lett. 2, 1-13 (2008) · Zbl 1147.90032 · doi:10.1007/s11590-006-0036-z
[16] Griffin, J.D., Kolda, T.G.: Asynchronous parallel hybrid optimization combining DIRECT and GSS. Optim. Methods Softw. 25, 797-817 (2010) · Zbl 1198.90397 · doi:10.1080/10556780903039893
[17] Hansen, E., Walster, G.W.: Global Optimization using Interval Analysis, 2nd edn. Marcel Dekker, New York (2004) · Zbl 1103.90092
[18] Horst, R., Pardalos, P.M. (eds.): Handbook of Global Optimization, vol. 1. Kluwer Academic Publishers, Dordrecht (1995) · Zbl 0805.00009
[19] Huyer, W., Neumaier, A.: Global optimization by multilevel coordinate search. J. Glob. Optim. 14, 331-355 (1999) · Zbl 0956.90045 · doi:10.1023/A:1008382309369
[20] Iyigun, C.: Probabilistic distance clustering, Ph.D. thesis, Graduate School—New Brunswick, Rutgers (2007) · Zbl 1088.65057
[21] Iyigun, C., Ben-Israel, A.: A generalized weiszfeld method for the multi-facility location problem. Oper. Res. Lett. 38, 207-214 (2010) · Zbl 1188.90148 · doi:10.1016/j.orl.2009.11.005
[22] Jones, D.R.: A taxonomy of global optimization methods based on response surfaces. J. Glob. Optim. 21, 345-383 (2001) · Zbl 1172.90492 · doi:10.1023/A:1012771025575
[23] Jones, D.R., Perttunen, C.D., Stuckman, B.E.: Lipschitzian optimization without the Lipschitz constant. J. Optim. Theory Appl. 79, 157-181 (1993) · Zbl 0796.49032 · doi:10.1007/BF00941892
[24] Kogan, J.: Introduction to Clustering Large and High-Dimensional Data. Cambridge University Press, Cambridge (2007) · Zbl 1183.62106
[25] Kolda, T.G., Lewis, R.M., Torczon, V.: Optimization by direct search: New perspectives on some classical and modern methods. SIAM Rev. 45, 385-482 (2003) · Zbl 1059.90146 · doi:10.1137/S003614450242889
[26] Kvasov, D.E., Sergeyev, Y.D.: A univariate global search working with a set of Lipschitz constants for the first derivative. Optim. Lett. 3, 303-318 (2009) · Zbl 1173.90544 · doi:10.1007/s11590-008-0110-9
[27] Kvasov, D.E., Sergeyev, Y.D.: Univariate geometric Lipschitz global optimisation algorithms. Numer. Algebra Control Optim. 2, 69-90 (2012) · Zbl 1246.90124 · doi:10.3934/naco.2012.2.69
[28] Kvasov, D.E., Sergeyev, Y.D.: Lipschitz gradients for global optimization in a one-point-based partitioning scheme. J. Comput. Appl. Math. 236, 4042-4054 (2012) · Zbl 1246.65091 · doi:10.1016/j.cam.2012.02.020
[29] Leisch, F.: A toolbox for k-centroids cluster analysis. Comput. Stat. Data Anal. 51, 526-544 (2006) · Zbl 1157.62439 · doi:10.1016/j.csda.2005.10.006
[30] Liuzzi, G., Lucidi, S., Piccialli, V.: A direct-based approach for large-scale global optimization problems. Comput. Optim. Appl. 45, 353-375 (2010) · Zbl 1187.90275 · doi:10.1007/s10589-008-9217-2
[31] Mockus, J.: On the pareto optimality in the context of lipschitzian optimization. Informatica 22, 524-536 (2011) · Zbl 1272.90061
[32] Neumaier, A.: Complete search in continuous global optimization and constraint satisfaction, Acta Numerica 13, 271-369 (2004) · Zbl 1113.90124
[33] Nyarko, E.K., Scitovski, R.: Solving the parameter identification problem of mathematical model using genetic algorithms. Appl. Math. Comput. 153, 651-658 (2004) · Zbl 1048.65075 · doi:10.1016/S0096-3003(03)00661-1
[34] Pardalos, P.M., Coleman, T.F. (eds.): Lectures on global optimization, Fields Institute Communications Series, vol. 55. AMS (2009) · Zbl 1172.90492
[35] Pijavskij, S.A.: An algorithm for searching for a global minimum of a function. USSR Comput. Math. Math. Phys. 12, 888-896 (1972). (in Russian) · Zbl 0249.65046
[36] Pintér, J.D.: Global Optimization in Action (Continuous and Lipschitz Optimization: Algorithms, Implementations and Applications). Kluwer Academic Publishers, Dordrecht (1996) · Zbl 0842.90110
[37] Sabo, K., Scitovski, R., Vazler, I.: One-dimensional center-based \[l_1\]-clustering method. Optim. Lett. (accepted) doi:10.1007/s11590-011-0389-9 · Zbl 1283.90034
[38] Schöbel, A., Scholz, D.: The big cube small cube solution method for multidimensional facility location problems. Comput. Oper. Res. 37, 115-122 (2010) · Zbl 1171.90451 · doi:10.1016/j.cor.2009.03.031
[39] Sergeyev, Y.D., Kvasov, D.E.: Diagonal Global Optimization Methods. FizMatLit, Moscow (2008) (in Russian)
[40] Sergeyev, YD; Kvasov, DE; Cochran, J. (ed.), Lipschitz global optimization, No. 4, 2812-2828 (2011), New York
[41] Sergeyev, Y.D., Famularo, D., Pugliese, P.: Index branch-and-bound algorithm for Lipschitz univariate global optimization with multiextremal constraints. J. Glob. Optim. 21, 317-341 (2001) · Zbl 1033.49038 · doi:10.1023/A:1012391611462
[42] Sergeyev, Y.D., Kvasov, D.E.: Global search based on efficient diagonal partitions and a set of Lipschitz constants. SIAM J. Optim. 16, 910-937 (2006) · Zbl 1097.65068 · doi:10.1137/040621132
[43] Shubert, B.: A sequential method seeking the global maximum of a function. SIAM J. Numer. Anal. 9, 379-388 (1972) · Zbl 0251.65052 · doi:10.1137/0709036
[44] Späth, H.: Cluster-Formation und Analyse. R. Oldenburg Verlag, München (1983) · Zbl 0536.62048
[45] Strongin, R.G.: Numerical Methods in Multiextremal Problems. Nauka, Moscow (1978). (in Russian) · Zbl 0458.65062
[46] Strongin, R.G., Sergeyev, Y.D.: Global Optimization with Non-Convex Constraints: Sequential and Parallel Algorithms. Kluwer Academic Publishers, Dordrecht (2000) · Zbl 0987.90068
[47] Teboulle, M.: A unified continuous optimization framework for center-based clustering methods. J. Mach. Learn. Res. 8, 65-102 (2007) · Zbl 1222.68318
[48] Vanderbei, R.J.: Extension of piyavskii’s algorithm to continuous global optimization. J. Glob. Optim. 14, 205-216 (1999) · Zbl 0946.90065 · doi:10.1023/A:1008395413111
[49] Volkovich, V., Kogan, J., Nicholas, C.: Building initial partitions through sampling techniques. Eur. J. Oper. Res. 183, 1097-1105 (2007) · Zbl 1135.90042 · doi:10.1016/j.ejor.2005.12.045
[50] Wood, G.R., Zhang, B.P.: Estimation of the Lipschitz constant of a function. J. Glob. Optim. 8, 91-103 (1996) · Zbl 0856.90105 · doi:10.1007/BF00229304
[51] Wu, Y., Ozdamar, L., Kumar, A.: Triopt: A triangulation-based partitioning algorithm for global optimization. J. Comput. Appl. Math. 177, 35-53 (2005) · Zbl 1062.65066 · doi:10.1016/j.cam.2004.08.005
[52] Yang, X.S.: Firefly algorithms for multimodal optimization. In: Proceedings of the 5th International Conference on Stochastic Algorithms: Foundations and Applications, pp. 169-178 (2009) · Zbl 1260.90164
[53] Zhang, Y., Xua, Y., Zhang, L.: A filled function method applied to nonsmooth constrained global optimization. J. Comput. Appl. Math. 232, 415-426 (2009) · Zbl 1175.90422 · doi:10.1016/j.cam.2009.06.020
[54] Zhigljavsky, A., Žilinskas, A.: Stochastic Global Optimization. Springer, Berlin (2008) · Zbl 1136.90003
[55] Zlobec, S.: The fundamental theorem of calculus for Lipschitz functions. Math. Commun. 13, 215-232 (2008) · Zbl 1160.26005
[56] Zlobec, S.: Equivalent formulations of the gradient. J. Glob. Optim. 50, 549-553 (2011) · Zbl 1222.90081 · doi:10.1007/s10898-011-9648-7
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.