Two level minimization in multidimensional scaling. (English) Zbl 1145.90060

Summary: Multidimensional scaling with city block norm in embedding space is considered. Construction of the corresponding algorithm is reduced to minimization of a piecewise quadratic function. The two level algorithm is developed combining combinatorial minimization at upper level with local minimization at lower level. Results of experimental investigation of the efficiency of the proposed algorithm are presented as well as examples of its application to visualization of multidimensional data.


90C29 Multi-objective and goal programming
90C59 Approximation methods and heuristics in mathematical programming


Full Text: DOI


[1] An L., Tao P. (2001) D.C. programing approach to the multidimensional scaling problem. In: Pardalos P., Varbrand P. (eds) From Local to Global Optimization. Kluwer, Dodrecht, pp. 231–276
[2] Borg I., Groenen P. (1997) Modern Multidimensional Scaling. Springer, New York · Zbl 0862.62052
[3] Brusco M.J. (2001) A simulated annealing heuristics for unidimensional and multidimensional (city block) scaling of symmetric proximity matrices. J. Classif. 18, 3–33 · Zbl 1040.91080
[4] Corne D., Dorigo M., Glover F. (eds) (1999) New Ideas in Optimization. McGraw-Hill, Maidenhead, England
[5] Cox T., Cox M. (2001) Multidimensional Scaling. Chapman and Hall/CRC, Boca Raton
[6] De Leeuw J. (1984) Differentiability of Kruskal’s stress at a local minimum. Psychometrika 149, 111–113 · doi:10.1007/BF02294209
[7] De Leeuw J., Heiser W. (1982) Theory of multidimentional scaling. In: Krishnaiah P.R. (eds) Handbook of Statistics, vol. 2. North Holland, Amsterdam, pp. 285–316
[8] Everett J. (2001) Algorithms for multidimensional scaling. In: Chambers L. (eds) The practical handbook of genetic algorithms. Chapman and Hall/CRC, Boca Raton, pp. 2003–2233
[9] Festa P., Pardalos P.M., Resende M.G.C., Ribeiro C.C. (2002) Randomized heuristics for the max-cut problem. Optim. Methods Softw. 7, 1033–1058 · Zbl 1032.90073 · doi:10.1080/1055678021000090033
[10] Groenen, P.: The Majorization Approach to multidimentional scaling, p. 110. DSWO, Amsterdam (1993)
[11] Groenen P., Mathar R., Heiser W. (1995) The majorization approach to multidimensional scaling for minkowski distances. J. Classif. 12, 3–19 · Zbl 0825.92158 · doi:10.1007/BF01202265
[12] Groenen, P., Mathar, R., Trejos, J.: Global optimization methods for MDS applied to mobile communications. In: Gaul, W., Opitz, O., Schander, M. (eds.) Data Analysis: Scientific Models and Practical Applications, pp. 459–475. Springer, (2000)
[13] Horst R., Pardalos P., Thoai N. (1995) Introduction to global optimization. Kluwer, Dodrecht · Zbl 0836.90134
[14] Klock H., Buhmann J. (1999) Data visualization by multidimensional scaling: a deterministic annealing approach. Pattern Recogn. 33(4): 651–669 · doi:10.1016/S0031-3203(99)00078-3
[15] Leng P.L., Lau K. (2004) Estimating the city-block two-dimensional scaling model with simulated annealing. Eur. J. Oper. Res. 158, 518–524 · Zbl 1067.90130 · doi:10.1016/S0377-2217(03)00357-6
[16] Mathar R. (1997) Multidimensionale Skalierung. Teubner, Stuttgart
[17] Mathar R. (1996) A hybrid global optimization algorithm for multidimensional scaling. In: Klar R., Opitz O. (eds) Classification and knowledge organization. Springer, Berlin, 63–71
[18] Mathar R., Žilinskas A. (1993) On global optimization in two-dimensional scaling. Acta Appl. Math. 33, 109–118 · Zbl 0792.60023 · doi:10.1007/BF00995497
[19] Michalewicz Z. (1996) Genetic Algorithms + Data Structures = Evolution Programs. Springer, Berlin · Zbl 0841.68047
[20] Press W. et al. (2002) Numerical Recipes in C++. Cambridge University Press, Cambridge · Zbl 1078.65500
[21] Törn, A., Žilinskas, A.: Global Optimization, Lecture Notes in Computer Science, vol. 350, pp. 1–250 (1989)
[22] Žilinskas A. (2003) On the distribution of the distance between two points in a cube. Random Oper. Stoch. Eqs. 11, 21–24 · Zbl 1020.60001
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.