The tunneling method for global optimization in multidimensional scaling

Patrick J.F. Groenen*, Willem J. Heiser

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

57 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)529-550
Number of pages22
Issue number3
Publication statusPublished - Sept 1996


Dive into the research topics of 'The tunneling method for global optimization in multidimensional scaling'. Together they form a unique fingerprint.

Cite this