论文标题
一类线性程序可通过坐标最小化解决
A Class of Linear Programs Solvable by Coordinate-Wise Minimization
论文作者
论文摘要
坐标最小化是用于大规模优化的简单流行方法。不幸的是，对于一般（非差异）凸问题而言，它可能找不到全球最小值。我们提供一类线性程序，以协调最小化可以准确求解。我们表明，在此类中，几个众所周知的组合优化问题的双LP松弛是在合理的运行时间中以足够准确的方式找到全球最小值。此外，对于不再在此类问题的这些问题的扩展，该方法产生了相当不错的suboptima。尽管所提出的LP松弛可以通过更有效的方法（例如Max-Flow）来解决，但我们的结果在理论上是非平凡的，将来可能导致新的大规模优化算法。
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.
