Mathematical Sciences: Global Optimization for Multidimensional Scaling

点击翻译按钮获取中文摘要

9622749 Trosset Numerical algorithms for multidimensional scaling (MDS) construct geometric configurations from dissimilarity data by attempting to solve specific optimization problems. It has long been widely believed that most MDS problems are plagued by the existence of local solutions that are not global solutions, and considerable effort has been expended addressing this difficulty. Recently, various researchers have proposed searching for global solutions by such "off-the-shelf" global optimization methods as simulated annealing, tunneling, and continuation. These methods are quite computationally expensive and research by the principal investigator suggests that they may be largely unnecessary. This research involves properly reformulating the structure of many important MDS problems such that local searches, which invariably find global solutions, can be exploited. This research concerns computational methods for multidimensional scaling, a collection of statistical techniques for mathematically constructing geometric configurations of objects from information about the distances between those objects. For example, a chemist might want to "construct" a molecule with certain interatomic distances, or a psychologist might want to geometrically represent a set of stimuli using data about the differences that human subjects perceived between pairs of stimuli. Such problems pose formidable computational challenges. The focus of this research is on developing more efficient methods for computing optimal solutions of these problems.