An efficient CGA_ADMM for the metric nearness problem

The metric nearness problem aims to find a metric matrix nearest to a given dissimilarity matrix with the triangle inequalities valid.In this paper, we consider the metric nearness problem with the distance measured by the vector p (p = 1, 2, ) norm.Due to the O(n 3 ) constraints and O(n 2 ) variables, the main difficulty of solving this kind of large scale problems is the high memory requirement.We design a constraint generation based alternating direction method of multipliers (CGA ADMM) and take full advantage of the special structure of the constraint matrix so that the memory requirement of the CGA ADMM is moderate.Numerical experiments of the real world graph data sets involving up to 10 8 variables and 10 12 constraints demonstrate that our algorithm has a better performance than the current state-of-the-art algorithms.