Grant: Discovery Grants Program - Individual
University of New Brunswick
$18,000.00
Geometric aspects of optimization
FY 2016-17
Summary
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.
Program
Discovery Grants Program - Individual
Recipient
Location
New Brunswick, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2015-04955
Name nom
Bremner, David
Department département
Office of Research Services (ORS) - Fredericton - Office of Research Services (O
Organization id
75
Institution établissement
University of New Brunswick
Province en
New Brunswick
Province fr
Nouveau-Brunswick
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2016
Competition year année de concours
2015
Award amount
18000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
800
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information and communication services
Area of application fr
Services d'information et de télécommunications
Research subject code
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
2
Nb partie
5
Application title
Geometric aspects of optimization
Keyword
NSERC
Application summary
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.