Parallel global optimization in multidimensional scaling. (English) Zbl 1156.65310

Čiegis, Raimondas (ed.) et al., Parallel scientific computing and optimization. Advances and applications. New York, NY: Springer (ISBN 978-0-387-09706-0/hbk). Springer Optimization and Its Applications 27, 69-82 (2009).
Summary: Multidimensional scaling is a technique for exploratory analysis of multidimensional data, whose essential part is optimization of a function possessing many adverse properties including multidimensionality, multimodality, and non-differentiability. In this chapter, global optimization algorithms for multidimensional scaling are reviewed with particular emphasis on parallel computing.
For the entire collection see [Zbl 1151.65001].


65K05 Numerical mathematical programming methods
65Y05 Parallel numerical computation
90C30 Nonlinear programming
90C06 Large-scale problems in mathematical programming
Full Text: DOI


[1] Arabie, P., Was Euclid an unnecessarily sophisticated psychologist?, Psychometrika, 56, 4, 567-587 (1991) · Zbl 0761.92050 · doi:10.1007/BF02294491
[2] Baravykaitė, M.; Čiegis, R., An implementation of a parallel generalized branch and bound template, Mathematical Modelling and Analysis, 12, 3, 277-289 (2007) · Zbl 1176.90652 · doi:10.3846/1392-6292.2007.12.277-289
[3] Baravykaitė, M.; Čiegis, R.; Žilinskas, J., Template realization of generalized branch and bound algorithm, Mathematical Modelling and Analysis, 10, 3, 217-236 (2005) · Zbl 1138.90501
[4] Baravykaitė, M.; Žilinskas, J.; Bogle, I. D.L.; Žilinskas, J., Implementation of parallel optimization algorithms using generalized branch and bound template, Computer Aided Methods in Optimal Design and Operations, Series on Computers and Operations Research, 21-28 (2006), Singapore: World Scientific, Singapore · Zbl 1113.90170 · doi:10.1142/9789812772954_0003
[5] Borg, I.; Groenen, P. J.F., Modern Multidimensional Scaling: Theory and Applications (2005), New York: Springer, New York · Zbl 1085.62079
[6] Brusco, M. J., A simulated annealing heuristic for unidimensional and multidimensional (city-block) scaling of symmetric proximity matrices, Journal of Classification, 18, 1, 3-33 (2001) · Zbl 1040.91080
[7] Cantú-Paz, E., Efficient and Accurate Parallel Genetic Algorithms. (2000), New York: Kluwer Academic Publishers, New York · Zbl 0963.68164
[8] Černý, V., Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm, Journal of Optimization Theory and Applications, 45, 1, 41-51 (1985) · Zbl 0534.90091 · doi:10.1007/BF00940812
[9] Cox, T. F.; Cox, M. A.A., Multidimensional Scaling (2001), Boca Raton: Chapman & Hall/CRC, Boca Raton · Zbl 1004.91067
[10] Floudas, C. A., Deterministic Global Optimization: Theory, Methods and Applications, Nonconvex Optimization and its Applications (2000), New York: Kluwer Academic Publishers, New York · Zbl 1037.90002
[11] Glover, F., Tabu search - Part I, ORSA Journal on Computing, 1, 3, 190-206 (1989) · Zbl 0753.90054
[12] Glover, F., Tabu search - Part II, ORSA Journal on Computing, 2, 1, 4-32 (1990) · Zbl 0771.90084
[13] Goldberg, D. E., Genetic Algorithms in Search, Optimization, and Machine Learning. (1989), Reading, MA: Adison-Wesley, Reading, MA · Zbl 0721.68056
[14] Green, P.; Carmone, F.; Smith, S., Multidimensional Scaling: Concepts and Applications. (1989), Boston: Allyn and Bacon, Boston
[15] Groenen, P.; Mathar, R.; Trejos, J.; Gaul, W.; Opitz, O.; Schander, M., Global optimization methods for multidimensional scaling applied to mobile communication, Data Analysis: Scientific Modeling and Practical Applications, 459-475 (2000), New York: Springer, New York
[16] Groenen, P. J.F., The Majorization Approach to Multidimentional Scaling: Some Problems and Extensions. (1993), Leiden: DSWO Press, Leiden · Zbl 0898.62080
[17] Groenen, P. J.F.; Heiser, W. J., The tunneling method for global optimization in multidimensional scaling, Psychometrika, 61, 3, 529-550 (1996) · Zbl 0866.92028 · doi:10.1007/BF02294553
[18] Groenen, P. J.F.; Mathar, R.; Heiser, W. J., The majorization approach to multidimensional scaling for Minkowski distances, Journal of Classification, 12, 1, 3-19 (1995) · Zbl 0825.92158 · doi:10.1007/BF01202265
[19] Hansen, E.; Walster, G. W., Global Optimization Using Interval Analysis (2003), New York: Marcel Dekker, New York
[20] Horst, R.; Pardalos, P. M.; Thoai, N. V., Introduction to Global Optimization, Nonconvex Optimization and its Applications (2001), New York: Kluwer Academic Publishers, New York
[21] Kirkpatrick, S.; Gelatt, C. D.J.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 4598, 671-680 (1983) · Zbl 1225.90162 · doi:10.1126/science.220.4598.671
[22] Leeuw, J. D., Differentiability of Kruskal’s stress at a local minimum, Psychometrika, 49, 1, 111-113 (1984) · doi:10.1007/BF02294209
[23] Mathar, R.; Klar, R.; Opitz, O., A hybrid global optimization algorithm for multidimensional scaling, Classification and Knowledge Organization, pp. 63-71. (1997), New York: Springer, New York
[24] Mathar, R.; Žilinskas, A., On global optimization in two-dimensional scaling, Acta Applicandae Mathematicae, 33, 1, 109-118 (1993) · Zbl 0792.60023 · doi:10.1007/BF00995497
[25] Michalewich, Z., Genetic Algorithms + Data Structures = Evolution Programs. (1996), Berlin: Springer, Berlin · Zbl 0841.68047
[26] Mockus, J., Bayesian Approach to Global Optimization. (1989), Boston: Kluwer Academic Publishers, Boston · Zbl 0693.49001
[27] Schwefel, H. P., Evolution and Optimum Seeking. (1995), New York: John Wiley & Sons, New York
[28] Törn, A.; Žilinskas, A., Global optimization. Lecture Notes in Computer Science 350, 1-252 (1989), Berlin: Springer-Verlag, Berlin · Zbl 0752.90075
[29] Varoneckas, A.; Žilinskas, A.; Žilinskas, J.; Bogle, I. D.L.; Žilinskas, J., Multidimensional scaling using parallel genetic algorithm, Computer Aided Methods in Optimal Design and Operations, Series on Computers and Operations Research, 129-138 (2006), Singapore: World Scientific, Singapore · Zbl 1113.90173 · doi:10.1142/9789812772954_0014
[30] Vera, J. F.; Heiser, W. J.; Murillo, A., Global optimization in any Minkowski metric: a permutation-translation simulated annealing algorithm for multidimensional scaling, Journal of Classification, 24, 2, 277-301 (2007) · Zbl 1159.91469 · doi:10.1007/s00357-007-0020-1
[31] Žilinskas, A.; Žilinskas, J., Parallel hybrid algorithm for global optimization of problems occurring in MDS-based visualization, Computers & Mathematics with Applications, 52, 1-2, 211-224 (2006) · Zbl 1157.90533 · doi:10.1016/j.camwa.2006.08.016
[32] Žilinskas, A., Žilinskas, J.: Parallel genetic algorithm: assessment of performance in multidimensional scaling. In: GECCO ’07: Proceedings of the 9th annual conference on Genetic and evolutionary computation, pp. 1492-1501. ACM, New York (2007). doi 10.1145/1276958.1277229 · Zbl 1145.90060
[33] Žilinskas, A.; Žilinskas, J., Two level minimization in multidimensional scaling, Journal of Global Optimization, 38, 4, 581-596 (2007) · Zbl 1145.90060 · doi:10.1007/s10898-006-9097-x
[34] Žilinskas, A., Žilinskas, J.: Branch and bound algorithm for multidimensional scaling with city-block metric. Journal of Global Optimization in press (2008). doi 10.1007/s10898-008-9306-x · Zbl 1179.90250
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.