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维多面体P={Ax <= B}（即R^d中n个半空间的交集）上的线性函数c^t x。一个多面体包含许多0维和1维的面，称为顶点和边。单纯形法通过沿着边旋转通过G_P的顶点来求解LP。它在实践中使用非常广泛并且非常有效，但其理论性能知之甚少。旋转算法需要至少与G_P的直径一样多的枢轴，然而甚至不知道这个直径是否必须在输入中是多项式（有效地，在n和d中）。最近在这个问题上有了实质性的进展，桑托斯对赫希1957年猜想的反例突出了这一点，赫希猜想的直径以n-d为界。然而，关键的公开问题，“多项式赫希猜想”，是否有一个多项式的上限n和d，仍然开放。 我们对解决这一问题的各种方法感兴趣。一个吸引人的起点是Bonifas等人最近的工作，在深度优先探索G_P的过程中跟踪顶点处所见的法锥的体积。当关联矩阵A是全幺模时，这给出了多面体的改进的多项式上界。体积估计主要依赖于A的完整性。我们建议开始检查他们的方法是否可以修改工作，例如，如果我们绑定的子矩阵的条件数，而不是行列式。更雄心勃勃的是，我们可以尝试产生他们的体积膨胀引理的摊销版本，这可以减少对A的依赖，至少在合适的条件下。 LP的一个有趣的组合推广被称为有色线性规划（CLP）。众所周知，LP可行性可以简化为找到可行基的问题，即R^d中的一组（d+1）个点，其凸船体包含点p。在CLP中，R^d中的点被给定为输入数据，并且还被划分为（d+1）种颜色。目标是找到一组（d+1）点，每种颜色之一，其中包含p在其凸船体。这样一个集合是存在的，但有效地找到它是一个具有挑战性的问题，其可处理性尚未被理解。 像LP一样，这个问题自然是通过几何旋转算法来解决的。Barany和Onn研究了两种漂亮的算法来解决这个问题，输入中的每个多项式和1/r，其中r是以p为中心的球的半径，并且包含在每种颜色的凸船体中。这些算法中的第一个依赖于重复计算当前单纯形上的最小范数点，而第二个是组合的。在以前的工作中，我们通过构建一个具有快速减小的r值的示例族来显示组合算法的指数行为。然而，该算法的范数最小化版本似乎相当稳健。一个初步的目标是得到一个严密的分析这个算法-要么表明它是真正的多项式，或者，更有可能的是，得到一个家庭的例子，清楚地显示指数行为。 我们将进一步考虑是否范数最小化的单纯形可以在多项式时间内使用组合算法。这将使我们能够使用精确的算术实现鲁棒算法，并在实践中加快计算速度。 最后，我们考虑与单调布尔函数有关的问题。