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 New York · Zbl 0862.62052
[2] Cox, T.; Cox, M., Multidimensional scaling, (2001), Chapman and Hall/CRC Boca Raton, FL · Zbl 1004.91067
[3] De Leeuw, J.; Heiser, W., Theory of multidimensional scaling, (), 285-316
[4] Törn, A.; Žilinskas, A., Global optimization, lecture notes in computer science 350, (), 1-250
[5] Groenen, P., The majorization approach to multidimensional scaling, (1993), DSWO Amsterdam · Zbl 0898.62080
[6] Everett, J.E., Algorithms for multidimensional scaling, (), 203-233
[7] Groenen, P.; Mathar, R.; Trejos, J., Global optimization methods for MDS applied to mobile communications, (), 459-475
[8] Mathar, R., A hybrid global optimization algorithm for multidimensional scaling, (), 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
[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, (submitted).
[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. 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.