The tunneling method for global optimization in multidimensional scaling

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.This paper is based on the 1994 Psychometric Society's outstanding thesis award of the first author. The authros 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.