An efficient CGA_ADMM for the metric nearness problem

Journal:Journal of Nonlinear and Variational Analysis

Key Words:Alternating direction method of multipliers; Constraint generation algorithm; Metric nearness problem

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 lp (p = 1;2;\infinity) 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.

Co-author:Chengjing Wang,Yangkai Wu

First Author:Bo Jiang

Correspondence Author:Peipei Tang

Volume:9

Issue:6

Page Number:885-906

Translation or Not:no

Date of Publication:2025-09-01

Included Journals:SCI