Integer Convex Minimization in Low Dimensions
Integer Convex Minimization in Low Dimensions
复制标题
低维整数凸最小化
DOI：
10.3929/ethz-a-010295887
复制
发表时间：
2014
影响因子：
2.7
通讯作者：
Timm Oertel
中科院分区：
文献类型：
--
作者：
Timm Oertel
在本文中，我们讨论了几种求解整数和混合整数凸极小化问题的方法。也就是说，我们试图最小化凸集上的一个凸函数，并附加一个约束条件，即少数变量必须是整数的。本文由四个部分组成。在第一部分中，我们将镜像下降法从连续凸优化应用到混合整数设置。这种方法的主要特点是迭代次数与维度无关，但是这种方法依赖于一个强大的预言，即所谓的改进预言。对于只需要两个变量积分的情况，我们给出了这种预言的一种有效实现。第二部分包含两种不同的、简短的几何激励的证明，证明了在有界凸集的整点上最小化一个凸函数是固定维多项式的这一众所周知的结果。特别地，我们提出了一种基于混合整数线性优化预言的预言多项式算法。然后，在第三部分中，我们将重心方法推广到整数和混合整数设置。关键的一步在于用更一般的中心点代替重心，允许我们使用体积以外的测量。我们引入了中心点和近似中心点的概念。对于特殊情况，我们证明了(近似)中心点的性质。在整数设置下，当维度固定时，我们给出了一个计算近似中心点的算法。此外，我们建立了基于无格多面体的(混合)整数极小化问题的最优性证书，并给出了一个基于中心点的算法，该算法以这样的最优性证书终止。在最后一部分中，我们考虑了一类特殊的、不一定是凸的变维最优化问题。我们的目标是优化集合P∩Z上的f(Wx)，其中f是一个非线性函数，P⊂R是一个多面体，W∈Zd×n。我们得到了从后一类问题到整数线性问题的一个有效的转化。核心结果是表示
In this dissertation we discuss several approaches to solve integer and mixedinteger convex minimization problems. That is, we try to minimize a convex function over a convex set with the additional constraint that a small number variables must be integral. The thesis consists of four parts. In the first part we apply the Mirror-Descent Method from continuous convex optimization to the mixed-integer setting. The main feature of this method is that the number of iterations is independent of the dimension, however, this method relies on a strong oracle, the so called improvement oracle. We present an efficient realization of such an oracle for the case when only two variables are required to be integral. The second part contains two alternative, short, and geometrically motivated proofs of the well known result that minimizing a convex function over the integral points of a bounded convex set is polynomial in fixed dimension. In particular, we present an oracle-polynomial algorithm that is based on a mixed-integer linear optimization oracle. Then, in the third part, we extend the Method of Centers of Gravity to the integer and mixed-integer setting. The crucial step consists in replacing the points of center of gravity by more general center-points, allowing us to use measures other than the volume. We introduce the concepts of center-points and approximate center-points. For special instances we prove properties of the (approximate) center-points. In the integer setting and when the dimension is fixed, we present an algorithm to compute approximate center-points. Furthermore, we establish optimality certificates for (mixed-) integer minimization problems based on lattice free polyhedra and we present a algorithm based on center-points that terminates with such an optimality certificate. In the last part we consider a special class of, not necessarily convex, optimization problems in variable dimension. We aim to optimize f(Wx) over a set P ∩ Z, where f is a non-linear function, P ⊂ R is a polyhedron and W ∈ Zd×n. The dimension n may vary, however, we assume that the dimension d is fixed. We obtain an efficient transformation from the latter class of problems to integer linear problems. The core result is a representation