论文标题
$ \ ell_ {p} $基于norm norm的度量问题的有效算法
An efficient algorithm for the $\ell_{p}$ norm based metric nearness problem
论文作者
论文摘要
给定差异矩阵，度量的接近度问题是找到满足三角形不平等的距离的最接近矩阵。此问题具有广泛的应用程序，例如传感器网络，图像处理等。但是，由于$ o（n^{3}）$公制约束和非平滑目标函数，即使获得适度精确的解决方案也是巨大的挑战，通常是加权的$ \ ell_ {p} $基于norm norm norm的距离。在本文中，我们提出了一种延迟的约束生成方法，每个子问题都由基于牛顿的半齿近端增强Lagrangian方法（PALM）解决公制问题。由于对与度量约束相关的矩阵的存储的高内存要求，我们利用了矩阵的特殊结构，而无需存储相应的约束矩阵。我们算法的一个令人愉悦的方面是，我们可以解决这些问题，涉及$ 10^{8} $变量和$ 10^{13} $约束。数值实验证明了我们算法的效率。 从理论上讲，首先，在温和的条件下，我们建立了一个原始的双重误差绑定条件，这对于分析手掌局部收敛速率至关重要。其次，我们证明了对棕榈的内部子问题的双重非修饰条件与非义属性之间的等效性。第三，当$ q（\ cdot）= \ | \ cdot \ | _ {1} $或$ \ | \ | \ cdot \ | _ {\ infty} $，而没有严格的互补条件，我们还证明了双重不合格条件与原始解决方案的独特性之间的等价。
Given a dissimilarity matrix, the metric nearness problem is to find the nearest matrix of distances that satisfy the triangle inequalities. This problem has wide applications, such as sensor networks, image processing, and so on. But it is of great challenge even to obtain a moderately accurate solution due to the $O(n^{3})$ metric constraints and the nonsmooth objective function which is usually a weighted $\ell_{p}$ norm based distance. In this paper, we propose a delayed constraint generation method with each subproblem solved by the semismooth Newton based proximal augmented Lagrangian method (PALM) for the metric nearness problem. Due to the high memory requirement for the storage of the matrix related to the metric constraints, we take advantage of the special structure of the matrix and do not need to store the corresponding constraint matrix. A pleasing aspect of our algorithm is that we can solve these problems involving up to $10^{8}$ variables and $10^{13}$ constraints. Numerical experiments demonstrate the efficiency of our algorithm. In theory, firstly, under a mild condition, we establish a primal-dual error bound condition which is very essential for the analysis of local convergence rate of PALM. Secondly, we prove the equivalence between the dual nondegeneracy condition and nonsingularity of the generalized Jacobian for the inner subproblem of PALM. Thirdly, when $q(\cdot)=\|\cdot\|_{1}$ or $\|\cdot\|_{\infty}$, without the strict complementarity condition, we also prove the equivalence between the the dual nondegeneracy condition and the uniqueness of the primal solution.
