论文标题
在尺寸二
Constructing lattice-free gradient polyhedra in dimension two
论文作者
论文摘要
无晶格梯度Polyhedra可用于证明混合凸最小化模型的最优性。我们考虑如何在没有两个整数变量的不受约束模型的模型中构造这些Polyhedra，这是所有级别集均有界的假设。 Bell，Doignon和围巾的经典结果表明，在这种情况下，最多有四个方面的无晶格梯度多面体。我们提出了一种用于创建一系列梯度多面体序列的算法，每个梯度最多具有四个方面，它们有限地收敛到无晶格的梯度多面体。每个更新都需要不断进行许多梯度评估。我们的更新模仿了梯度下降算法，因此，对于两个整数变量的问题，它产生了梯度下降类型的算法。
Lattice-free gradient polyhedra can be used to certify optimality for mixed-integer convex minimization models. We consider how to construct these polyhedra for unconstrained models with two integer variables under the assumption that all level sets are bounded. A classic result of Bell, Doignon, and Scarf states that a lattice-free gradient polyhedron with at most four facets exists in this setting. We present an algorithm for creating a sequence of gradient polyhedra, each of which has at most four facets, that finitely converges to a lattice-free gradient polyhedron. Each update requires constantly many gradient evaluations. Our updates imitate the gradient descent algorithm, and consequently, it yields a gradient descent type of algorithm for problems with two integer variables.
