Pivoting Algorithms and Geometric Optimization Problems

旋转算法和几何优化问题

• 批准号: RGPIN-2014-06371
• 负责人: Stephen, Tamon
• 金额: $ 0.8万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2016
• 资助国家: 加拿大
• 起止时间: 2016-01-01 至 2017-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=612185
• 关键词: 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维polyhedron p = {ax <= b}上最小化（或最大化）线性函数c^t x，即r^d中n个半空间的交点。多面体包含有限的许多0和1维面，称为顶点和边缘。这些形成一个简单的图，称为p的图，并表示为g_p。单纯形方法通过沿着G_P的顶点沿边缘旋转来解决LP。它在实践中被广泛使用且极有效，但其理论性能知之甚少。枢轴算法至少需要与G_P直径一样多的枢轴，但是甚至还不知道该直径是否必须在输入中是多项式（实际上，在N和D中）。桑托斯（Santos）对赫希（Hirsch）1957年的猜想，直径是由n-d界定的。但是，关键的开放问题是“多项式赫希猜想”，即n和d中是否存在多项式上限。 我们对解决此问题的各种方法感兴趣。一个吸引人的起点是Bonifas等人最近的工作，他在G_P的深度探索中跟踪了在顶点上看到的正常锥体的体积。当入射率A完全不产物时，这给出了多项式的多项式上限。量估计值主要取决于A的完整性A，我们建议首先检查是否可以修改其方法以工作以工作，例如，如果我们绑定了一个而不是确定因素的一量的条件数。更加雄心勃勃，我们可以尝试生成其体积膨胀引理的摊销版本，然后至少在适当的条件下可以减少对A的依赖。 LP的有趣组合概括称为彩色线性编程（CLP）。众所周知，可以将LP的可行性降低到找到可行的基础的问题，即在其凸面船体包含一个点p的r^d中的一组（d+1）点。在CLP中，R^d中的点作为输入数据，也将其分配为（d+1）颜色。目的是找到一组（d+1）点，每种颜色之一，其中包含P中的p。存在这样的集合，但是有效地发现它是一个具有挑战性的问题，其障碍性尚未理解。 像LP一样，几何透视算法自然而然地解决了这个问题。 Barany和Onn研究了两种精美的算法来解决问题，每个多项式在输入和1/R中，其中r是一个以p为中心的球的半径，并包含在每种颜色的凸面中。这些算法中的第一种依赖于反复计算当前单纯形上的最小规范点，而第二个是组合。在先前的工作中，我们通过构建一个迅速降低r值的示例家族来显示组合算法的指数行为。但是，该算法的规范最小化版本似乎很强大。一个初步的目标是对该算法进行严格的分析 - 表明它是真正的多项式，或者更有可能获得一个清楚地显示出指数行为的示例家庭。 我们将进一步考虑使用组合算法在多项式时间内可以在单纯形上进行规范最小化。这将使我们能够使用精确的算术实现强大的算法，并在实践中加快计算加速。 最后，我们考虑与单调布尔功能有关的问题。