Practical Techniques for Metric-Constrained Optimization

Nate Veldt (Center for Applied Mathematics, Cornell)

An optimization problem is called metric-constrained if it involves triangle inequality constraints of the form $x_{ij} \leq x_{ik} + x_{jk},$ where $x_{ij}$ is a variable representing distance between two objects in a dataset. These problems arise in numerous settings, from sensor location to theoretical approximation algorithms for graph clustering. However, they are extremely difficult to solve on a large scale due to their high memory requirement. Here we develop a new approach for metric optimization based on iterative projection methods, which come with a smaller memory footprint than traditional optimization techniques. We also show how our techniques can be parallelized by grouping disjoint metric constraints into blocks and performing a large number of projection steps simultaneously. Our techniques enable us to address optimization problems involving nearly 3 trillion constraints.