Pivoting Algorithms and Geometric Optimization Problems

旋转算法和几何优化问题

• 批准号: RGPIN-2014-06371
• 负责人: Stephen, Tamon
• 金额: $ 0.8万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2017
• 资助国家: 加拿大
• 起止时间: 2017-01-01 至 2018-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=635188
• 关键词: Pivoting; Algorithms; Geometric; Optimization; Problems

The main theme for this proposal is pivoting algorithms for discrete optimization. The fundamental objects studied are the diameter of polyhedra and colourful linear programming.The most important geometric optimization problem is linear programming. A linear program (LP) requires to minimize (or maximize) a linear function c^t x over a d-dimensional polyhedron P={Ax <= b}, i.e. the intersection of n half-spaces in R^d. A polyhedron contains finitely many 0- and 1-dimensional faces called vertices and edges. These form a simple graph, called the graph of P, and denoted G_P. The simplex method solves LPs by pivoting along edges through the vertices of G_P. It is very widely used and extremely effective in practice, but its theoretical performance is poorly understood. Pivoting algorithms require at least as many pivots as the diameter of G_P, however it is not even known if this diameter must be polynomial in the input (effectively, in n and d). There is substantial recent progress on this question, highlighted by Santos' counter-example to Hirsch's 1957 conjecture that the diameter is bounded by n-d. However, the key open question, the "polynomial Hirsch conjecture", of whether there is a polynomial upper bound in n and d, remains open.We are interested in various approaches to this problem. An appealing starting point is the recent work of Bonifas et al., who track the volume of normal cones seen at the vertices in a depth-first exploration of G_P. This gives an improved polynomial upper bound for polytopes when the incidence matrix A is totally unimodular. The volume estimates depend critically on the integrality of A. We propose to begin by examining whether their approach can be modified to work if, for instance, we bound the condition numbers of submatrices of A rather than the determinants. More ambitiously, we can try to produce an amortized version of their volume expansion lemma, which could then reduce the dependence on A, at least under suitable conditions. An interesting combinatorial generalization of LP is known as Colourful Linear Programming (CLP). As is well known, LP feasibility can be reduced to a problem of finding a feasible basis, i.e. a set of (d+1) points in R^d whose convex hull contains a point p. In the CLP, points in R^d are given as input data, and are also partitioned into (d+1) colours. The objective is to find a set of (d+1) points, one of each colour, which contains p in its convex hull. Such a set exists, but finding it efficiently is a challenging problem whose tractability is not yet understood.Like LP, this question is naturally approached by geometric pivoting algorithms. Barany and Onn studied two beautiful algorithms for solving the problem, each polynomial in the input and 1/r, where r is the radius of a ball centred at p and contained in the convex hull of each colour. The first of these algorithms relies on repeatedly computing the point of minimum norm on the current simplex, while the second is combinatorial. In previous work, we showed exponential behaviour of the combinatorial algorithm by constructing a family of examples with rapidly decreasing values of r. However the norm-minimization version of the algorithm seems quite robust. A preliminary goal is to get a tight analysis of this algorithm - either show that it is genuinely polynomial, or, more likely, to get a family of examples that clearly shows exponential behaviour.We will further consider whether norm minimization on a simplex can be done in polynomial time using a combinatorial algorithm. This would allow us to implement the robust algorithm using exact arithmetic, and speed up the computation in practice.Finally, we consider questions related to monotone Boolean functions.

这项提议的主题是离散优化的旋转算法。研究的基本对象是多面体的直径和有色线性规划，其中最重要的几何优化问题是线性规划。线性规划(LP)需要最小化(或最大化)d维多面体P={Ax&lt；=b}上的线性函数c^tx，即R^d中n个半空间的交集。多面体包含有限多个0维和1维面，称为顶点和边。单纯形法是一种简单的图，称为P图，记为G_P。单纯形法通过在G_P中的顶点沿边旋转来求解LP。它在实践中应用非常广泛，非常有效，但其理论性能却鲜为人知。旋转算法需要至少与G_P直径一样多的枢轴，然而，甚至不知道这个直径在输入中是否必须是多项式(有效地，在n和d中)。最近在这个问题上有了实质性的进展，桑托斯对赫希1957年的猜想的反例强调了这一点，即直径是由n-d限制的。然而，关于n和d中是否存在多项式上界的关键问题，即“多项式赫希猜想”，仍然是开放的。我们对这个问题的各种方法感兴趣。一个吸引人的起点是Bonifas等人最近的工作，他们在深度优先的G_P探索中跟踪在顶点看到的法锥的体积。当关联矩阵A完全单模时，这给出了改进的多面体的多项式上界。体积估计在很大程度上取决于A的完整性。我们建议首先检查他们的方法是否可以修改为有效，例如，如果我们限制了A的子矩阵的条件数而不是行列式。更雄心勃勃的是，我们可以尝试产生他们的体积扩张引理的摊余版本，这可以减少对A的依赖，至少在适当的条件下是这样。线性规划的一个有趣的组合推广被称为彩色线性规划(CLP)。众所周知，线性规划的可行性可以归结为寻找一个可行基的问题，即R^d中的一组(d+1)点，其凸壳包含一个点p。在CLP中，R^d中的点被作为输入数据给出，并且被划分为(d+1)色。目标是找到一组(d+1)点，每种颜色一种，它的凸壳中包含p。这样的集合是存在的，但有效地找到它是一个具有挑战性的问题，其可处理性还没有被理解。像LP一样，这个问题自然是通过几何旋转算法来解决的。Barany和Onn研究了两个漂亮的算法来解决这个问题，每个多项式都在输入和1/r中，其中r是以p为中心的球的半径，包含在每种颜色的凸壳中。第一种算法依赖于重复计算当前单纯形上的最小范数点，而第二种算法是组合算法。在以前的工作中，我们通过构造一族具有快速递减的r值的例子来证明组合算法的指数行为。然而，该算法的范数最小化版本似乎相当健壮。一个初步的目标是对这个算法进行严格的分析--或者证明它是真正的多项式的，或者更有可能的是得到一族清楚地显示指数行为的例子。我们将进一步考虑是否可以使用组合算法在多项式时间内完成单纯形上的范数最小化。这将使我们能够用精确的算法来实现健壮性算法，并在实际中加快计算速度。最后，我们考虑了与单调布尔函数相关的问题。