Bo Jiang, Peipei Tang, Chengjing Wang, Yangkai Wu, An efficient CGA_ADMM for the metric nearness problem

Full Text: PDF
DOI: 10.23952/jnva.9.2025.6.04

Volume 9, Issue 6, 1 December 2025, Pages 885-906

Abstract. 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 $\ell_{p}$ ( $p=1,2,\infty$ ) 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.

How to Cite this Article:
B. Jiang, P. Tang, C. Wang, Y. Wu, An efficient CGA_ADMM for the metric nearness problem, J. Nonlinear Var. Anal. 9 (2025), 885-906.