Title: A Projection Method for Metric-Constrained Optimization,
Abstract: We outline a new approach for solving optimization problems which enforce
triangle inequalities on output variables. We refer to this as
metric-constrained optimization, and give several examples where problems of
this form arise in machine learning applications and theoretical approximation
algorithms for graph clustering. Although these problem are interesting from a
theoretical perspective, they are challenging to solve in practice due to the
high memory requirement of black-box solvers. In order to address this
challenge we first prove that the metric-constrained linear program relaxation
of correlation clustering is equivalent to a special case of the metric
nearness problem. We then developed a general solver for metric-constrained
linear and quadratic programs by generalizing and improving a simple projection
algorithm originally developed for metric nearness. We give several novel
approximation guarantees for using our framework to find lower bounds for
optimal solutions to several challenging graph clustering problems. We also
demonstrate the power of our framework by solving optimizing problems involving
up to 10^{8} variables and 10^{11} constraints.