Pivoting Algorithms and Geometric Optimization Problems

本提案的主题是离散优化的旋转算法。研究的基本对象是多面体的直径和彩色线性规划。最重要的几何优化问题是线性规划。一个线性规划（LP）要求在一个d维多面体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的依赖，至少在合适的条件下。彩色线性规划（CLP）是线性规划的一种有趣的组合推广。众所周知，LP的可行性可以简化为寻找可行基的问题，即R^d中的（d+1）个点的集合，其凸包包含一个点p。在CLP中，R^d中的点作为输入数据给出，并且也被划分为（d+1）个颜色。目标是找到一组（d+1）个点，每种颜色一个，其凸包中包含p。这样的集合是存在的，但是有效地找到它是一个具有挑战性的问题，其可追溯性尚未被理解。像LP一样，这个问题自然是通过几何旋转算法来解决的。Barany和Onn研究了两种漂亮的算法来解决这个问题，每个多项式都是输入和1/r，其中r是一个以p为中心的球的半径，包含在每种颜色的凸包中。第一种算法依赖于重复计算当前单纯形上的最小范数点，而第二种算法是组合算法。在之前的工作中，我们通过构造一组r值快速下降的示例来展示组合算法的指数行为。然而，该算法的规范最小化版本似乎相当鲁棒。初步目标是对该算法进行严密的分析——要么表明它是真正的多项式，要么更有可能得到一系列清楚显示指数行为的例子。我们将进一步考虑是否可以使用组合算法在多项式时间内完成单纯形上的范数最小化。这将允许我们使用精确的算法实现鲁棒算法，并在实践中加快计算速度。最后，我们考虑与单调布尔函数有关的问题。

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.