论文标题
用于非线性二进制优化的切割平面算法
Cutting plane algorithms for nonlinear binary optimization
论文作者
论文摘要
解决离散优化问题的当前最新方法通常仅限于凸设置。在本文中，我们提出了一种基于切割平面的一般方法，用于解决非线性，可能是非凸，二进制优化问题。我们提供了严格的合并分析，该分析量化了不同条件下所需的迭代次数。这与仅证明有限收敛的离散优化中的大多数其他工作不同。此外，使用各种分析中的工具，我们提供了必要和足够的双重最优条件。
Current state-of-the-art methods for solving discrete optimization problems are usually restricted to convex settings. In this paper, we propose a general approach based on cutting planes for solving nonlinear, possibly nonconvex, binary optimization problems. We provide a rigorous convergence analysis that quantifies the number of iterations required under different conditions. This is different to most other work in discrete optimization where only finite convergence is proved. Moreover, using tools from variational analysis, we provide necessary and sufficient dual optimality conditions.
