Geometric aspects of optimization

概述 几何是高效优化算法的重要工具;相反，几何优化问题在从制造到机器学习和统计的应用中很常见。 这两个事实促使我的研究重点放在高维几何对象的算法，包括点集，超平面安排，特别是凸多面体。 凸多面体（或只是多面体），自然推广的经典柏拉图和阿基米德的固体，是基本的数学对象在线性约束优化，并广泛用作近似在更一般的优化问题。 几何优化 在优化中产生的许多多面体都具有高度的对称性。 最近的求解器能够 来分解出某些简单的对称性;一个自然的问题是如何利用更普遍的对称性。 已知的对称性 对于工业分支定界求解器，这需要非常快的 测试这些更一般的等价性的方法。 归纳最近的核心数据集 算法需要理解候选解的结构（核心集） 更一般的对称性的变化。 扩展配方的研究开始于观察到，许多问题的明显整数规划配方导致指数大小的多面体，而这些问题中的许多问题有一个简单的多项式大小的扩展配方，投影到明显的配方。 最近发现的不可能性，这样一个投影埃德蒙兹匹配多面体激励我们更一般的方法扩展配方，放松投影的要求，同时仍然代表整个计算的多面体。 几何优化问题 某些分类器训练问题可以解释为在凸多面体中寻找最大范数点。 一般的范数最大化问题是非常困难的，因此，我计划把重点放在分类算法中出现的多面体的某些特征上，并开发将这些多面体舍入为更容易的多面体的方法。 统计学家已经开发了各种数据深度度量，以测量点（测量向量）相对于数据云的中心性。 不幸的是，许多具有最令人满意的统计特性的深度测量很难计算。 另一方面，诸如透镜深度之类的测量仅取决于任意维度上的少量数据点，因此计算起来相对微不足道。 我计划调查在何种程度上容易计算的深度措施可以用来近似困难的，无论是分析或作为某种精确算法的边界机制。

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.