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

Žilinskas, Antanas; Žilinskas, Julius

J. Glob. Optim. 38, No. 4, 581-596 (2007).

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.

MSC:

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

Keywords:

Multilevel optimization; Multidimensional scaling; Metaheuristics; Global optimization

Software:

Genocop

References:

[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
[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
[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
[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
[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
[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
[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