论文标题
可行性和欧几里得距离矩阵优化的快速算法和序数约束
Feasibility and A Fast Algorithm for Euclidean Distance Matrix Optimization with Ordinal Constraints
论文作者
论文摘要
欧几里得距离矩阵优化具有顺序约束（EDMOC）已发现在传感器网络定位和分子构象中的重要应用。它也可以看作是多维缩放的矩阵公式，即在$ r $维空间中嵌入n个点，以使所得距离遵循序数约束。尽管事实证明，序数约束虽然非常有用，但在添加太多的情况下可能仅导致零解决方案，而EDMOC的可行性是一个问题。在本文中，我们首先会系统地研究EDMOC的可行性。我们表明，如果$ r \ ge n-2 $，Edmoc总是承认一个非平凡的解决方案。否则，它可能仅具有零解决方案。后者解释了“拥挤现象”的数值观察。 Next we overcome two obstacles in designing fast algorithms for EDMOC, i.e., the low-rankness and the potential huge number of ordinal constraints.我们将开发的技术应用于将低级约束作为有条件的正等级半圆锥，并切成等级。这导致了多数罚款方法。序数约束留给子问题，这正是加权的等渗回归，可以通过增强池相邻违规者算法（PAVA）的实现来解决。广泛的数值结果证明了{}所提出的方法优于某些最先进的求解器。
Euclidean distance matrix optimization with ordinal constraints (EDMOC) has found important applications in sensor network localization and molecular conformation. It can also be viewed as a matrix formulation of multidimensional scaling, which is to embed n points in a $r$-dimensional space such that the resulting distances follow the ordinal constraints. The ordinal constraints, though proved to be quite useful, may result in only zero solution when too many are added, leaving the feasibility of EDMOC as a question. In this paper, we first study the feasibility of EDMOC systematically. We show that if $r\ge n-2$, EDMOC always admits a nontrivial solution. Otherwise, it may have only zero solution. The latter interprets the numerical observations of 'crowding phenomenon'. Next we overcome two obstacles in designing fast algorithms for EDMOC, i.e., the low-rankness and the potential huge number of ordinal constraints. We apply the technique developed to take the low rank constraint as the conditional positive semidefinite cone with rank cut. This leads to a majorization penalty approach. The ordinal constraints are left to the subproblem, which is exactly the weighted isotonic regression, and can be solved by the enhanced implementation of Pool Adjacent Violators Algorithm (PAVA). Extensive numerical results demonstrate {the} superior performance of the proposed approach over some state-of-the-art solvers.
