Geometric aspects of optimization

概述 几何是高效优化算法的重要工具；相反，几何性质的优化问题在从制造到机器学习和统计学的各种应用中都很常见。这两个事实促使我专注于高维几何对象的算法，包括点集、超平面排列，特别是凸多面体。凸多面体(或简称多面体)是经典柏拉图和阿基米德固体的自然推广，是线性约束优化的基本数学对象，在更一般的优化问题中被广泛用作近似。 优化中的几何图形 在优化中出现的许多多面体都表现出高度的对称性。最近的求解器能够 把某些简单的对称性分解出来；一个自然的问题是如何利用更普遍的对称性 已知会出现对称性。对于工业分支定界求解器来说，这需要极快的速度 测试这些更一般的等价性的方法。推广最近的核心集 算法需要了解候选解(核心集)的结构 改变为更一般的对称性。 对扩展公式的研究始于这样的观察，即许多问题的明显整数规划公式导致一个指数大小的多面体，而许多这些问题具有投影到明显公式上的多项式大小的简单扩展公式。最近发现对于Edmonds匹配多面体不可能有这样的投影，这促使我们更一般地采用扩展公式来放宽投影要求，同时仍然在多面体中表示整个计算。 几何优化问题 某些分类器训练问题可以解释为在凸多面体中寻找最大范数点。众所周知，一般的范数最大化问题是极其困难的；因此，我计划集中在分类算法中出现的多面体的某些特征，以及开发将这些多面体舍入到更容易的多面体的方法。 统计学家已经开发了各种数据深度度量来衡量一个点(测量向量)相对于数据云的中心度。不幸的是，许多具有最令人满意的统计特性的深度度量很难计算。另一方面，像镜头深度这样的度量只依赖于任何维度上的少量数据点，因此计算相对简单。我计划调查在多大程度上可以使用易于计算的深度度量来近似困难的深度度量，无论是解析地还是作为某种精确算法的边界机制。

Overview Geometry is an important tool for efficient optimization algorithms; conversely geometric flavoured optimization problems are common in applications ranging from manufacturing to machine learning and statistics.  These two facts motivate my research focus on algorithms for high dimensional geometric objects, including point sets, hyperplane arrangements, and especially convex polyhedra.  Convex polyhedra (or just polyhedra), natural generalizations of the classical Platonic and Archimedian solids, are the fundamental mathematical objects in linear constrained optimization, and widely used as approximations in more general optimization problems. Geometry in optimization Many polyhedra arising in optimization exhibit a high degree of symmetry.  Recent solvers are able to factor out certain simple kinds of symmetry; a natural question is how to exploit the more general symmetries known to occur.  For industrial branch-and-bound solvers this requires extremely fast methods for testing these more general equivalences.  Generalizing recent core set algorithms requires understanding how the structure of the candidate solutions (the core set) changes for more general symmetries. The study of extended formulations starts from the observation that the obvious integer programming formulation of many problems results in an exponential sized polyhedron, while many of these problems have a simple extended formulation of polynomial size that projects onto the obvious formulation.  The recent discovery of impossibility of such a projection for Edmonds' matching polytope motivates our more general approaches to extended formulations that relax the projection requirement while still representing the entire computation in the polyhedron. Geometric optimization problems Certain classifier training problems can be interpreted as finding the maximum norm point in a convex polyhedron.  The general norm maximization problem is known to be extremely difficult; for this reason I plan to focus on certain features of the polyhedra that arise in classification algorithms, and on developing methods for rounding these polyhedra to easier ones. Various data depth measures have been developed by statisticians to measure the centrality of a point (measurement vector) with respect to a data cloud.  Unfortunately many of the depth measures with the most pleasing statistical properties are difficult to compute.  On the other hand, measures such as lens depth depend on only a small number of data points in any dimension, and are thus relatively trivial to compute.  I plan to investigate to what extent the easy to compute depth measures can be used to approximate the difficult ones, either analytically or as a bounding mechanism in some kind of exact algorithm.