Parallel hybrid algorithm for global optimization of problems occurring in MDS-based visualization. (English) Zbl 1157.90533

Summary: Multidimensional scaling is a widely used technique for visualization of multidimensional data. For the implementation of a multidimensional scaling technique a difficult global optimization problem should be solved. To attack such problems a hybrid global optimization method is developed combining evolutionary global search with local descent. A parallel version of the proposed method is implemented to enable solution of large scale problems in acceptable time. The results of the experimental investigation of the efficiency of the proposed method are presented.


90C30 Nonlinear programming
90C59 Approximation methods and heuristics in mathematical programming
90C90 Applications of mathematical programming
Full Text: DOI


[1] Borg, I.; Groenen, P., Modern. Multidimensional Scaling (1997), Springer: Springer New York · Zbl 0862.62052
[2] Cox, T.; Cox, M., Multidimensional Scaling (2001), Chapman and Hall/CRC: Chapman and Hall/CRC Boca Raton, FL · Zbl 1004.91067
[3] De Leeuw, J.; Heiser, W., Theory of multidimensional scaling, (Krishnaiah, P. R., Handbook of Statistics (1982), North-Holland: North-Holland Amsterdam), 285-316 · Zbl 0511.62076
[4] Törn, A.; Žilinskas, A., Global Optimization, Lecture Notes in Computer Science 350, ((1989), Springer: Springer Berlin), 1-250 · Zbl 0752.90075
[5] Groenen, P., The Majorization Approach to Multidimensional Scaling (1993), DSWO: DSWO Amsterdam · Zbl 0898.62080
[6] Everett, J. E., Algorithms for multidimensional scaling, (Chambers, L., The Practical Handbook of Genetic Algorithms (2001), Chapman and Hall/CRC: Chapman and Hall/CRC Boca Raton, FL), 203-233
[7] Groenen, P.; Mathar, R.; Trejos, J., Global optimization methods for MDS applied to mobile communications, (Gaul, W.; Opitz, O.; Schander, M., Data Analysis: Scientific Models and Practical Applications (2000), Springer), 459-475
[8] Mathar, R., A hybrid global optimization algorithm for multidimensional scaling, (Klar, R.; Opitz, O., Classification and Knowledge Organization (1996), Springer: Springer Berlin), 63-71
[9] Mathar, R.; Zilinskas, A., On global optimization in two-dimensional scaling, Acta Applicandae Mathematicae, 33, 109-118 (1993) · Zbl 0792.60023
[10] Press, W., Numerical Recipes in C++ (2002), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1078.65500
[11] Kearsley, A.; Tapia, R.; Trosset, M., The solution of the metric STRESS and SSTRESS problems in multidimensional scaling using Newton’s method, Computational Statistics, 13, 369-396 (1998) · Zbl 0926.92002
[12] Lange, K.; Hunter, D.; Yang, I., Optimization transfer using surrogate objective functions, Journal of Computational and Graphical Statistics, 9, 1, 1-59 (2000), (with discussion)
[13] De Leeuw, J., Differentiability of Kruskal’s stress at a local minimum, Psychometrika, 149, 111-113 (1984)
[14] A. Žilinskas and J. Žilinskas, Two level minimization in multidimensional scaling, Journal of Global Optimization; A. Žilinskas and J. Žilinskas, Two level minimization in multidimensional scaling, Journal of Global Optimization · Zbl 1145.90060
[15] Cantú-Paz, E., Efficient and Accurate Parallel Genetic Algorithms (2000), Kluwer Academic · Zbl 0963.68164
[16] Message Passing Interface Forum, MPI: A message-passing interface standard (version 1.1), Technical Report (1995)
[17] Fisher, R. A., The use of multiple measurements in taxonomy problems, Annals of Eugenics, 7, 179-188 (1936)
[18] Brusco, M. J., A simulated annealing heuristics for unidimensional and multidimensional (city block) scaling of symmetric proximity matrices, Journal of Classification, 18, 3-33 (2001) · Zbl 1040.91080
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.