Grant: Discovery Grants Program - Individual
The University of British Columbia
$26,000.00
A unified approach to optimization complexity via realization spaces
EF 2024-25
Résumé
The goal of optimization (or mathematical programming) is to maximize or minimize a function, often subject to constraints. Universities may wish to maximize the courses they can offer subject to the capacity of their campus. A machine learning algorithm that classifies objects in a photo tries to minimize its classification error rate. Airlines want to maximize profit subject to equipment and crew constraints. The complexity of an optimization problem is a measure of how efficiently we can find the desired maximum or minimum. To study this complexity and design algorithms to solve these problems, we can take into account the structure of the function we are optimizing, as well as the structure of the solution set defined by the constraints. In this proposal we focus on developing tools to gain a better understanding of these constraint sets.
At the inception of mathematical programming as a field of research, prompted by work of George Dantzig in the 1940s, the main interest was in linear programs, where the objective function and constraints are all linear. The constraint set of a linear program is known as a polyhedron or polytope (when bounded). Polytopes are part of a larger class of important constraint sets known as convex sets. A vast body of research exists in the study of polytopes, and it includes the use of various combinatorial, algebraic, and computational techniques.
Our own past research contributes to this body of knowledge by studying the realization space of a polytope; that is, the set of all concrete geometric instances of a fixed abstract facial structure. The optimal solutions to an optimization problem always occur on the faces of a convex constraint set, so it is important to understand the structure of the faces. However, the efficiency with which one can find these solutions often depends on the specific realization of the set.
The long-term vision of this research program is to provide a novel unified approach to studying convex sets by taking inspiration from the study of polytopes. We will build upon our understanding of realization spaces to better understand the complexity of certain optimization problems. We will show that these realization spaces and other tools used in the study of polytopes can be extended to a larger class of constraint sets.
Over the next 5 years we propose 3 topics in pursuit of this goal:
1. Circuit diameters of polytopes and the Circuit Hirsch Conjecture (towards resolving the complexity of linear programming);
2. Psd-minimal polytopes and integer lifts of polytopes (towards better bounds for relaxations of integer programming);
3. Classification of spectratopes (towards further understanding of the feasible regions of semidefinite programs).
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
British Columbia, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2024-04643
Name nom
Wiebe, Amy
Department département
Okanagan Department of Computer Science, Mathematics, Physics and Statistics
Organization id
2
Institution établissement
The University of British Columbia
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2024
Award amount
26000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2914
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Combinatorics
Research subject fr
Combinatoire
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
A unified approach to optimization complexity via realization spaces
Keywords
polyhedral combinatorics; realization spaces; linear programming; semidefinite programming; circuit diameter; convex geometry; computational geometry; psd rank; combinatorial optimization; applied algebraic geometry
Application summary
The goal of optimization (or mathematical programming) is to maximize or minimize a function, often subject to constraints. Universities may wish to maximize the courses they can offer subject to the capacity of their campus. A machine learning algorithm that classifies objects in a photo tries to minimize its classification error rate. Airlines want to maximize profit subject to equipment and crew constraints. The complexity of an optimization problem is a measure of how efficiently we can find the desired maximum or minimum. To study this complexity and design algorithms to solve these problems, we can take into account the structure of the function we are optimizing, as well as the structure of the solution set defined by the constraints. In this proposal we focus on developing tools to gain a better understanding of these constraint sets.
At the inception of mathematical programming as a field of research, prompted by work of George Dantzig in the 1940s, the main interest was in linear programs, where the objective function and constraints are all linear. The constraint set of a linear program is known as a polyhedron or polytope (when bounded). Polytopes are part of a larger class of important constraint sets known as convex sets. A vast body of research exists in the study of polytopes, and it includes the use of various combinatorial, algebraic, and computational techniques.
Our own past research contributes to this body of knowledge by studying the realization space of a polytope; that is, the set of all concrete geometric instances of a fixed abstract facial structure. The optimal solutions to an optimization problem always occur on the faces of a convex constraint set, so it is important to understand the structure of the faces. However, the efficiency with which one can find these solutions often depends on the specific realization of the set.
The long-term vision of this research program is to provide a novel unified approach to studying convex sets by taking inspiration from the study of polytopes. We will build upon our understanding of realization spaces to better understand the complexity of certain optimization problems. We will show that these realization spaces and other tools used in the study of polytopes can be extended to a larger class of constraint sets.
Over the next 5 years we propose 3 topics in pursuit of this goal:
1. Circuit diameters of polytopes and the Circuit Hirsch Conjecture (towards resolving the complexity of linear programming);
2. Psd-minimal polytopes and integer lifts of polytopes (towards better bounds for relaxations of integer programming);
3. Classification of spectratopes (towards further understanding of the feasible regions of semidefinite programs).