Mathematical Sciences: Global Optimization for Multidimensional Scaling

多维尺度（MDS）的数值算法通过求解特定的优化问题，从不同的数据中构造几何构型。长期以来，人们普遍认为，大多数MDS问题的困扰是存在局部解决方案而不是全局解决方案，并且已经花费了相当大的努力来解决这一困难。近年来，许多研究者提出了通过模拟退火、隧道和延续等“现成”的全局优化方法来寻找全局解。这些方法在计算上非常昂贵，首席研究员的研究表明，它们可能在很大程度上是不必要的。本研究涉及到对许多重要MDS问题的结构进行适当的重新表述，这样就可以利用总是找到全局解决方案的局部搜索。这项研究涉及多维尺度的计算方法，这是一套统计技术的集合，用于从这些物体之间的距离信息中以数学方式构建物体的几何构型。例如，化学家可能想要“构建”具有一定原子间距离的分子，或者心理学家可能想要使用有关人类受试者在对刺激之间感知差异的数据以几何方式表示一组刺激。这些问题构成了巨大的计算挑战。本研究的重点是开发更有效的方法来计算这些问题的最优解。

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.