On global optimization in two-dimensional scaling. (English) Zbl 0792.60023

Summary: We consider multidimensional scaling for embedding dimension two, which allows the detection of structures in dissimilarity data by simply drawing two-dimensional figures. The corresponding objective function, called STRESS, is generally nondifferentiable and has many local minima. We investigate several features of this function, and discuss the application of different global optimization procedures. A method based on combining a local search algorithm with an evolutionary strategy of generating new initial points is proposed, and its efficiency is investigated by numerical examples.


60F05 Central limit and other weak theorems
60F17 Functional limit theorems; invariance principles
62L20 Stochastic approximation


Full Text: DOI


[1] Floudas, C. and Pardalos, P.:A Collection of Test Problems for Constrained Global Optimization Algorithms, Lecture Notes in Computer Science 455, Springer, Berlin, 1990. · Zbl 0718.90054
[2] Goldberg, D.:Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, Reading, Mass., 1989. · Zbl 0721.68056
[3] Green, P.,et al.,: Multidimensional Scaling, Concepts and Applications, Allyn and Bacon, Boston, 1989.
[4] Groenen, P. and Heiser, W.: An improved tunneling function for finding a decreasing series of local minima in MDS, Research Report RR-91-06, Department of Data Theory, University of Leiden, 1991.
[5] Groenen, P., Mathar, R. and Heiser, W.: The majorization approach to multidimensional scaling for Minkowski distances,J. Classification (to appear). · Zbl 0825.92158
[6] Horst, R. and Tui, H.:Global Optimization: Deterministic Approach, Springer, Berlin, 1990.
[7] Mathar, R.: Algorithms in multidimensional scaling, in O. Opitz (ed.),Conceptual and Numerical Analysis of Data, Springer, Berlin, 1989. · Zbl 0728.92029
[8] Mathar, R. and Groenen, P.: Algorithms in convex analysis applied to multidimensional scaling, in E. Diday and Y. Lechevallier (eds),Symbolic-Numeric Data Analysis and Learning, Nova Science Publishers, New York, 1991.
[9] Mathar, R. and Meyer, R.: (1992), Algorithms in convex analysis to fit p -distance matrices, Technical Report, RWTH Aachen, submitted for publication. · Zbl 0806.62051
[10] Sammon, J.: On nonlinear mapping for data structure analysis,IEEE Trans. Comput. 18 (1969), 401–409. · doi:10.1109/T-C.1969.222678
[11] Schittkovski, K.: NLPQL: A Fortran subroutine solving constrained nonlinear programming problems,Ann. Oper. Res. 5 (1985), 485–500.
[12] Schwefel, H.-P.:Numerical Optimization of Computer Models, Wiley, Chichester, 1981. · Zbl 0451.65043
[13] Törn, A. and Žilinskas, A.:Global Optimization, Lecture Notes in Computer Science 350, Springer, Berlin, 1989.
[14] Zhigljavsky, A. and Žilinskas, A.:Methods for Searching of Global Optimum, Nauka, Moscow, 1991 (in Russian).
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.