Hostname: page-component-745bb68f8f-g4j75 Total loading time: 0 Render date: 2025-01-08T10:12:19.410Z Has data issue: false hasContentIssue false
  • English
  • Français

The Tunneling Method for Global Optimization in Multidimensional Scaling

Published online by Cambridge University Press:  01 January 2025

Patrick J. F. Groenen  and
Willem J. Heiser
Patrick J. F. Groenen*
Affiliation:
Department of Data Theory, Faculty of Social and Behavioural Sciences, Leiden University, The Netherlands
Willem J. Heiser
Affiliation:
Department of Data Theory, Faculty of Social and Behavioural Sciences, Leiden University, The Netherlands
*
Requests for reprints should be sent to Patrick J. F. Groenen, Department of Data Theory, Faculty of Social and Behavioural Sciences, PO Box 9555, 2300 RB Leiden, THE NETHERLANDS.
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper focuses on the problem of local minima of the STRESS function. It turns out that unidimensional scaling is particularly prone to local minima, whereas full dimensional scaling with Euclidean distances has a local minimum that is global. For intermediate dimensionality with Euclidean distances it depends on the dissimilarities how severe the local minimum problem is. For city-block distances in any dimensionality many different local minima are found. A simulation experiment is presented that indicates under what conditions local minima can be expected. We introduce the tunneling method for global minimization, and adjust it for multidimensional scaling with general Minkowski distances. The tunneling method alternates a local search step, in which a local minimum is sought, with a tunneling step in which a different configuration is sought with the same STRESS as the previous local minimum. In this manner successively better local minima are obtained, and experimentation so far shows that the last one is often a global minimum.

Keywords

multidimensional scalingiterative majorizationglobal optimizationtunneling method
Type
Original Paper
Information
Psychometrika , Volume 61 , Issue 3 , September 1996 , pp. 529 - 550
Copyright
Copyright © 1996 The Psychometric Society

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

This paper is based on the 1994 Psychometric Society's outstanding thesis award of the first author. The authors would like to thank Robert Tijssen of the CWTS Leiden for kindly making available the co-citation data of the Psychometric literature. This paper is an extended version of the paper presented at the Annual Meeting of the Psychometric Society at Champaign-Urbana, Illin., June 1994.

References

Arabie, P. (1991). Was Euclid an unnecessarily sophisticated psychologist?. Psychometrika, 56, 567–587.CrossRefGoogle Scholar
Bailey, R. A., Gower, J. C. (1990). Approximating a symmetric matrix. Psychometrika, 55, 665–675.CrossRefGoogle Scholar
Commandeur, J. J. F. (1992). Missing data in the distance approach to Principal Component Analysis, Leiden: Department of Data Theory.Google Scholar
Critchley, F. et al. (1986). Dimensionality theorems in MDS and HCA. In Diday, E. et al. (Eds.), Data analysis and informatics, Vol. 4 (pp. 45–70). Amsterdam: North-Holland.Google Scholar
Defays, D. (1978). A short note on a method of seriation. British Journal of Mathematical and Statistical Psychology, 3, 49–53.CrossRefGoogle Scholar
de Leeuw, J. (1977). Applications of convex analysis to multidimensional scaling. In Barra, J. R., Brodeau, F., Romier, G., van Cutsem, B. (Eds.), Recent development in statistics (pp. 133–145). Amsterdam: North-Holland.Google Scholar
de Leeuw, J. (1988). Convergence of the majorization method for multidimensional scaling. Journal of Classification, 5, 163–180.CrossRefGoogle Scholar
de Leeuw, J. (1993). Fitting distances by least squares. Unpublished manuscript.Google Scholar
de Leeuw, J., Heiser, W. J. (1977). Convergence of correction matrix algorithms for multidimensional scaling. In Lingoes, J. C., Roskam, E., Borg, I. (Eds.), Geometric representations of relational data (pp. 735–752). Ann Arbor: Mathesis Press.Google Scholar
de Leeuw, J., Heiser, W. J. (1980). Multidimensional scaling with restrictions on the configuration. In Krishnaiah, P. R. (Eds.), Multivariate analysis, Vol. V (pp. 501–522). Amsterdam: North-Holland.Google Scholar
De Soete, G., Hubert, L., Arabie, P. (1988). On the use of simulated annealing for combinatorial data analysis. In Gaul, W., Schader, M. (Eds.), Data, expert, knowledge and decisions (pp. 329–340). Berlin: Springer-Verlag.CrossRefGoogle Scholar
Dinkelbach, W. (1967). On nonlinear fractional programming. Management Science, 13, 492–498.CrossRefGoogle Scholar
Funk, S. G., Horowitz, A. D., Lipshitz, R., Young, F. W. (1974). The perceived structure of American ethnic groups: The use of multidimensional scaling in stereotype research. Personality and Social Psychology Bulletin, 1, 66–68.Google Scholar
Gomez, S., Levy, A. V. (1982). In Hennart, J. P. (Eds.), The tunneling method for solving the constrained global optimization problem with non-connected feasible regions (pp. 34–47). Berlin: Springer-Verlag.Google Scholar
Green, P. E., Carmone, F. J. Jr., Smith, S. M. (1989). Multidimensional scaling, concepts and applications, Boston: Allyn and Bacon.Google Scholar
Groenen, P. J. F. (1993). The majorization approach to multidimensional scaling: Some problems and extensions, Leiden: DSWO Press.Google Scholar
Groenen, P. J. F., Heiser, W. J. (1991). An improved tunneling function for finding a decreasing series of local minima, Leiden: Department of Data Theory.Google Scholar
Groenen, P. J. F., de Leeuw, J., Mathar, R. (1996). Least squares multidimensional scaling with transformed distances. In Gaul, W., Pfeifer, D. (Eds.), Studies in classification, data analysis, and knowledge organization (pp. 177–185). Berlin: Springer.Google Scholar
Groenen, P. J. F., Mathar, R., Heiser, W. J. (1995). The majorization approach to multidimensional scaling for Minkowski distances. Journal of Classification, 12, 3–19.CrossRefGoogle Scholar
Hardy, G. H., Littlewood, J. E., Pólya, G. (1952). Inequalities 2nd ed.,, Cambridge: University Press.Google Scholar
Heiser, W. J. (1989). The city-block model for three-way multidimensional scaling. In Coppi, R., Bolasco, S. (Eds.), Multiway data analysis (pp. 395–404). Amsterdam: North-Holland.Google Scholar
Heiser, W. J. (1991). A generalized majorization method for least squares multidimensional scaling of pseudodistances that may be negative. Psychometrika, 56, 7–27.CrossRefGoogle Scholar
Heiser, W. J. (1995). Convergent computation by iterative majorization: Theory and applications in multidimensional data analysis. In Krzanowski, W. J. (Eds.), Recent advances in descriptive multivariate analysis (pp. 157–189). Oxford: Oxford University Press.CrossRefGoogle Scholar
Heiser, W. J., de Leeuw, J. (1977). How to use SMACOF-1, Leiden: Department of Data Theory.Google Scholar
Heiser, W. J., Groenen, P. J. F. (1994). Cluster differences scaling with a within clusters loss component and a fuzzy successive approximation strategy to avoid local minima, Leiden: Department of Data Theory.Google Scholar
Hubert, L. J., Arabie, P. (1986). Unidimensional scaling and combinatorial optimization. In de Leeuw, J., Heiser, W. J., Meulman, J., Critchley, F. (Eds.), Multidimensional data analysis (pp. 181–196). Leiden: DSWO Press.Google Scholar
Hubert, L. J., Arabie, P., Hesson-McInnis, M. (1992). Multidimensional scaling in the city-block metric: A combinatorial approach. Journal of Classification, 9, 211–236.CrossRefGoogle Scholar
Kruskal, J. B. (1964). Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis. Psychometrika, 29, 1–28.CrossRefGoogle Scholar
Kruskal, J. B. (1964). Nonmetric multidimensional scaling: A numerical method. Psychometrika, 29, 115–129.CrossRefGoogle Scholar
Kruskal, J. B., Young, F. W., Seery, J. B. (1977). How to use KYST-2, a very flexible program to do multidimensional scaling and unfolding, Murray Hill, NJ: AT&T Bell Laboratories.Google Scholar
Levy, A. V., Gomez, S. (1985). The tunneling method applied to global optimization. In Boggs, P. T., Byrd, R. H., Schnabel, R. B. (Eds.), Numerical optimization 1984 (pp. 213–244). Philadelphia: SIAM.Google Scholar
Mathar, R., Groenen, P. J. F. (1991). Algorithms in convex analysis applied to multidimensional scaling. In Diday, E., Lechevallier, Y. (Eds.), Symbolic-numeric data analysis and learning (pp. 45–56). Commack, NY: Nova Science Publishers.Google Scholar
Meulman, J. J. (1986). A distance approach to nonlinear multivariate analysis, Leiden: DSWO Press.Google Scholar
Meulman, J. J. (1992). The integration of multidimensional scaling and multivariate analysis with optimal transformations. Psychometrika, 57, 539–565.CrossRefGoogle Scholar
Montalvo, A. (1979). Development of a new algorithm for the global minimization of functions Unpublished doctoral dissertation, Universidad Nacional Autonoma de Mexico.Google Scholar
Robinson, W. S. (1951). A method for chronologically ordering archaeological deposits. American Antiquity, 16, 293–301.CrossRefGoogle Scholar
Shepard, R. N. (1962). Analysis of proximities: Multidimensional scaling with an unknown distance function. Psychometrika, 27, 125–140.CrossRefGoogle Scholar
Tijssen, R. J. W. (1992). Cartography of science: Scientometric mapping with multidimensional scaling methods, Leiden: DSWO Press.Google Scholar
Torgerson, W. S. (1958). Theory and methods of scaling, New York: Wiley.Google Scholar
Tucker, W. S. (1951). A method for synthesis of factor analysis studies, Washington DC: Department of the Army.CrossRefGoogle Scholar
Vilkov, A. V., Zhidkov, N. P., Shchedrin, B. M. (1975). A method of finding the global minimum of a function of one variable. USSR Computational Mathematics and Mathematical Physics, 15, 1040–1042.CrossRefGoogle Scholar
Wagenaar, W. A., Padmos, P. (1971). Quantitative interpretation of stress in Kruskal's multidimensional scaling technique. British Journal of Mathematical and Statistical Psychology, 24, 101–110.CrossRefGoogle Scholar
Weeks, D. G., Bentler, P. M. (1982). Restricted multidimensional scaling models for asymmetric proximities. Psychometrika, 47, 201–208.CrossRefGoogle Scholar
Zielman, B. (1991). Three-way scaling of asymmetric proximities, Leiden: Department of Data Theory.Google Scholar