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.***