A Class of Linear Programs Solvable by Coordinate-Wise Minimization
This work addresses the challenge of applying coordinate-wise minimization to non-differentiable convex problems, offering theoretical insights that could lead to new large-scale optimization algorithms, though it is incremental as it builds on existing methods.
The authors identified a class of linear programs that can be exactly solved using coordinate-wise minimization, a method that typically fails for general convex problems, and demonstrated its application to dual LP relaxations of combinatorial optimization problems, achieving global minima with sufficient accuracy in reasonable runtimes.
Coordinate-wise minimization is a simple popular method for large-scale optimization. Unfortunately, for general (non-differentiable) convex problems it may not find global minima. We present a class of linear programs that coordinate-wise minimization solves exactly. We show that dual LP relaxations of several well-known combinatorial optimization problems are in this class and the method finds a global minimum with sufficient accuracy in reasonable runtimes. Moreover, for extensions of these problems that no longer are in this class the method yields reasonably good suboptima. Though the presented LP relaxations can be solved by more efficient methods (such as max-flow), our results are theoretically non-trivial and can lead to new large-scale optimization algorithms in the future.