An algorithm for minimizing clustering functions. (English) Zbl 1122.90059
Summary: The problem of cluster analysis is formulated as a problem of nonsmooth, nonconvex optimization. An algorithm for solving the latter optimization problem is developed which allows one to significantly reduce the computational efforts. This algorithm is based on the so-called discrete gradient method. Results of numerical experiments are presented which demonstrate the effectiveness of the proposed algorithm.
MSC:
| 90C26 | Nonconvex programming, global optimization |
| 49M25 | Discrete approximations in optimal control |
| 49M37 | Numerical methods based on nonlinear programming |
| 49J52 | Nonsmooth analysis |
| 65K05 | Numerical mathematical programming methods |
Keywords:
clustering functions; cluster analysis; nonsmooth; nonconvex optimization; discrete gradient methodReferences:
| [1] | Hansen P, Mathematical Programming 79 pp 191– (1997) |
| [2] | DOI: 10.1145/331499.331504 · doi:10.1145/331499.331504 |
| [3] | Bock HH, Automatische Klassifikation (1974) |
| [4] | Bock HH, Advances in Data Science and Classification pp pp. 265–277– (1998) |
| [5] | Spath H, Cluster Analysis Algorithms (1980) |
| [6] | DOI: 10.1016/0031-3203(76)90045-5 · doi:10.1016/0031-3203(76)90045-5 |
| [7] | DOI: 10.1016/S0031-3203(99)00216-2 · Zbl 1012.68873 · doi:10.1016/S0031-3203(99)00216-2 |
| [8] | Houkins DM, Topics in Applied Multivariate Analysis (1982) · doi:10.1017/CBO9780511897375 |
| [9] | DOI: 10.1287/opre.17.6.1034 · Zbl 0183.49103 · doi:10.1287/opre.17.6.1034 |
| [10] | DOI: 10.1137/0906020 · Zbl 0561.65097 · doi:10.1137/0906020 |
| [11] | DOI: 10.1016/0377-2217(85)90012-8 · Zbl 0565.90011 · doi:10.1016/0377-2217(85)90012-8 |
| [12] | DOI: 10.1109/T-C.1975.224336 · Zbl 0308.68039 · doi:10.1109/T-C.1975.224336 |
| [13] | Reeves CR, Modern Heuristic Techniques for Combinatorial Problems (1993) · Zbl 0942.90500 |
| [14] | DOI: 10.1016/0031-3203(92)90088-Z · doi:10.1016/0031-3203(92)90088-Z |
| [15] | DOI: 10.1016/0031-3203(91)90097-O · doi:10.1016/0031-3203(91)90097-O |
| [16] | DOI: 10.1016/0097-8485(94)85003-8 · Zbl 0825.92149 · doi:10.1016/0097-8485(94)85003-8 |
| [17] | DOI: 10.1016/0031-3203(95)00022-R · doi:10.1016/0031-3203(95)00022-R |
| [18] | DOI: 10.1016/0167-8655(95)00122-0 · doi:10.1016/0167-8655(95)00122-0 |
| [19] | DOI: 10.1137/S1064827597328327 · Zbl 1049.90129 · doi:10.1137/S1064827597328327 |
| [20] | DOI: 10.1023/A:1011336210885 · Zbl 1041.68623 · doi:10.1023/A:1011336210885 |
| [21] | DOI: 10.1016/S0031-3203(02)00060-2 · doi:10.1016/S0031-3203(02)00060-2 |
| [22] | Hansen P, Journal of Classification |
| [23] | DOI: 10.1023/A:1020911318981 · Zbl 1035.90060 · doi:10.1023/A:1020911318981 |
| [24] | Bagirov AM, European Journal of Operational Research |
| [25] | Bagirov AM, TOP: Spanish Operations Research Journal 11 pp 1– (2003) |
| [26] | Clarke FH, Optimization and Nonsmooth Analysis (1983) |
| [27] | Demyanov VF, Constructive Nonsmooth Analysis (1995) |
| [28] | DOI: 10.1137/0315061 · Zbl 0376.90081 · doi:10.1137/0315061 |
| [29] | Hiriart-Urruty J-P, Convex Analysis and Minimization Algorithms 1 (1993) |
| [30] | Kiwiel KC, Methods of Descent for Nondifferentiable Optimization 1133 (1985) · Zbl 0561.90059 · doi:10.1007/BFb0074500 |
| [31] | Makela MM, Nonsmooth Optimization (1992) · doi:10.1142/1493 |
| [32] | DOI: 10.1007/s101070100290 · Zbl 1014.65050 · doi:10.1007/s101070100290 |
| [33] | Nelder JA, Computer Journal 7 pp 308– (1965) · Zbl 0229.65053 · doi:10.1093/comjnl/7.4.308 |
| [34] | Bagirov AM, Progress in Optimization: Contribution from Australasia pp pp. 147–175– (1999) |
| [35] | DOI: 10.1080/10556780290027837 · Zbl 1040.90038 · doi:10.1080/10556780290027837 |
| [36] | DOI: 10.1023/A:1023227716953 · doi:10.1023/A:1023227716953 |
| [37] | Bagirov AM, Russian Journal of Computational Mathematics and Mathematical Physics 35 pp 403– (1995) |
| [38] | DOI: 10.1007/BF01580381 · Zbl 0352.90046 · doi:10.1007/BF01580381 |
| [39] | DOI: 10.1111/j.1469-1809.1936.tb02137.x · doi:10.1111/j.1469-1809.1936.tb02137.x |
| [40] | Murphy PM, University of California (1992) |
| [41] | Reinelt G, ORSA J. Comput. 3 pp 319– (1991) · Zbl 0775.90293 · doi:10.1287/ijoc.3.4.376 |
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.
