Geometric aspects of optimization

优化的几何方面

• 批准号: RGPIN-2015-04955
• 负责人: Bremner, David
• 金额: $ 1.31万
• 依托单位: University of New Brunswick
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=676881
• 关键词: Geometric; aspects; 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.***

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