×

zbMATH — the first resource for mathematics

A new global optimization method for a symmetric Lipschitz continuous function and the application to searching for a globally optimal partition of a one-dimensional set. (English) Zbl 1377.65067
The paper proposes a method for solving a global optimization problem for a symmetric Lipschitz continuous function. The author shows that this problem always has a solution with natural conditions on the data. The proposed method is illustrated by solving a center-based clustering problem with synthetic data. Some numerical experiments are presented by testing the proposed method on the image segmentation problem.

MSC:
65K05 Numerical mathematical programming methods
90C26 Nonconvex programming, global optimization
90C27 Combinatorial optimization
90C56 Derivative-free methods and methods using generalized derivatives
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
05E05 Symmetric functions and generalizations
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bagirov, AM; Ugon, J, An algorithm for minimizing clustering functions, Optimization, 54, 351-368, (2005) · Zbl 1122.90059
[2] Bandyopadhyay, S., Saha, S.: Unsupervised Classification: Similarity Measures, Classical and Metaheuristic Approaches, and Applications. Springer, Berlin (2013) · Zbl 1276.62038
[3] Bezdek, J.C., Keller, J., Krisnapuram, R., Pal, N.R.: Fuzzy models and algorithms for pattern recognition and image processing. Springer, Berlin (2005) · Zbl 0998.68138
[4] Bishop, C.M.: Pattern Recognition and Machine Learning. Springer, Berlin (2006) · Zbl 1107.68072
[5] 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
[6] Evtushenko, Y.G.: Numerical Optimization Techniques (Translations Series in Mathematics and Engineering). Springer, Berlin (1985)
[7] Finkel, D.E.: DIRECT Optimization Algorithm User Guide. Center for Research in Scientific Computation. North Carolina State University. http://www4.ncsu.edu/ ctk/Finkel_Direct/DirectUserGuide_pdf.pdf (2003) · Zbl 1097.65068
[8] Finkel, DE; Kelley, CT, Additive scaling and the DIRECT algorithm, J. Glob. Optim., 36, 597-608, (2006) · Zbl 1142.90488
[9] Floudas, CA; Gounaris, CE, A review of recent advances in global optimization, J. Glob. Optim., 45, 3-38, (2009) · Zbl 1180.90245
[10] Gablonsky, J.M.: DIRECT Version 2.0. Technical Report. Center for Research in Scientific Computation. North Carolina State University (2001) · Zbl 1360.62350
[11] Grbić, R; Nyarko, EK; Scitovski, R, A modification of the DIRECT method for Lipschitz global optimization for a symmetric function, J. Glob. Optim., 57, 1193-1212, (2013) · Zbl 1279.65076
[12] Hansen, E., Walster, G.W.: Global Optimization Using Interval Analysis, 2nd edn. Marcel Dekker, New York (2004) · Zbl 1103.90092
[13] Iyigun, C.: Probabilistic Distance Clustering. Ph.D. thesis. Graduate School - New Brunswick, Rutgers (2007) · Zbl 1300.90031
[14] Iyigun, C; Ben-Israel, A, A generalized weiszfeld method for the multi-facility location problem, Op. Res. Lett., 38, 207-214, (2010) · Zbl 1188.90148
[15] Jones, DR; Perttunen, CD; Stuckman, BE, Lipschitzian optimization without the Lipschitz constant, J. Optim. Theory Appl., 79, 157-181, (1993) · Zbl 0796.49032
[16] Kogan, J.: Introduction to Clustering Large and High-dimensional Data. Cambridge University Press, New York (2007) · Zbl 1183.62106
[17] Kvasov, DE; Sergeyev, YD, A univariate global search working with a set of Lipschitz constants for the first derivative, Optim. Lett., 3, 303-318, (2009) · Zbl 1173.90544
[18] Kvasov, DE; Sergeyev, YD, Lipschitz gradients for global optimization in a one-point-based partitioning scheme, J. Comput. Appl. Math., 236, 4042-4054, (2012) · Zbl 1246.65091
[19] Kvasov, DE; Sergeyev, YD, Univariate geometric Lipschitz global optimisation algorithms, Numer. Algebra Control Optim., 2, 69-90, (2012) · Zbl 1246.90124
[20] Leisch, F, A toolbox for k-centroids cluster analysis, Comput. Stat. Data Anal., 51, 526-544, (2006) · Zbl 1157.62439
[21] Marošević, T; Scitovski, R, Multiple ellipse Fitting by center-based clustering, Croat. Oper. Res. Rev., 6, 43-53, (2015) · Zbl 1359.62256
[22] Morales-Esteban, A; Martínez-Álvarez, F; Scitovski, S; Scitovski, R, A fast partitioning algorithm using adaptive Mahalanobis clustering with application to seismic zoning, Comput. Geosci., 73, 132-141, (2014)
[23] Neumaier, A, Complete search in continuous global optimization and constraint satisfaction, Acta Numerica, 13, 271-369, (2004) · Zbl 1113.90124
[24] Paulavičius, R; Sergeyev, Y; Kvasov, D; Žilinskas, J, Globally-biased DISIMPL algorithm for expensive global optimization, J. Glob. Optim., 59, 545-567, (2014) · Zbl 1297.90130
[25] Paulavičius, R., Žilinskas, J.: Simpl. Glob. Optim. Springer, Berlin (2014a) · Zbl 1401.90017
[26] Paulavičius, R; Žilinskas, J, Simplicial Lipschitz optimization without Lipschitz constant, J. Glob. Optim., 59, 23-40, (2014) · Zbl 1300.90031
[27] Paulavičius, R; Žilinskas, J, Advantages of simplicial partitioning for Lipschitz optimization problems with linear constraints, Optim. Lett., 10, 237-246, (2016) · Zbl 1342.90151
[28] Pintér, J. (ed.): Global Optimization: Scientific and Engineering Case Studies. Springer, Berlin (2006) · Zbl 1103.90011
[29] Pintér, J.D.: Global Optimization in Action (Continuous and Lipschitz Optimization: Algorithms, Implementations and Applications). Kluwer Academic Publishers, Dordrecht (1996) · Zbl 0842.90110
[30] Sabo, K; Scitovski, R, An approach to cluster separability in a partition, Inf. Sci., 305, 208-218, (2015) · Zbl 1360.62350
[31] Sabo, K; Scitovski, R; Vazler, I, One-dimensional center-based \(l_1\)-clustering method, Optim. Lett., 7, 5-22, (2013) · Zbl 1283.90034
[32] 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
[33] Scitovski, R; Marošević, T, Multiple circle detection based on center-based clustering, Pattern Recognit. Lett., 52, 9-16, (2014)
[34] Scitovski, R; Sabo, K, Analysis of the \(k\)-means algorithm in the case of data points occurring on the border of two or more clusters, Knowl. Based Syst., 57, 1-7, (2014)
[35] Scitovski, R; Scitovski, S, A fast partitioning algorithm and its application to earthquake investigation, Comput. Geosci., 59, 124-131, (2013)
[36] Sergeyev, YD; 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
[37] Sergeyev, YD; Kvasov, DE, Global search based on efficient diagonal partitions and a set of Lipschitz constants, SIAM J. Optim., 16, 910-937, (2006) · Zbl 1097.65068
[38] Sergeyev, Y.D., Kvasov, D.E.: Diagonal Global Optimization Methods. FizMatLit, Moscow (2008) · Zbl 1282.90138
[39] Sergeyev, YD; Kvasov, DE; Cochran, J (ed.), Lipschitz global optimization, No. 4, 2812-2828, (2011), New York
[40] Späth, H.: Cluster-Formation und Analyse. R. Oldenburg Verlag, München (1983) · Zbl 0536.62048
[41] Strongin, R.G., Sergeyev, Y.D.: Global Optimization with Non-Convex Constraints: Sequential and Parallel Algorithms. Kluwer Academic Publishers, Dordrecht (2000) · Zbl 0987.90068
[42] Szeliski, R.: Computer Vision: Algorithms and Applications. Springer, Berlin (2011) · Zbl 1219.68009
[43] Theodoridis, S., Koutroumbas, K.: Pattern Recognition, 4th edn. Academic Press, Burlington (2009) · Zbl 0954.68131
[44] Vidović, I; Scitovski, R, Center-based clustering for line detection and application to crop rows detection, Comput. Electron. Agric., 109, 212-220, (2014)
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.