Grant: Discovery Grants Program - Individual
University of Waterloo
$48,000.00
Mathematical Optimization: Theory and Algorithms
EF 2021-22
Résumé
My research program aims to find tractable mathematical models for problems treated within computer science, and then focuses on the design, mathematical analysis and implementation of efficient and robust algorithms (solution methods) for such problems. These problems arise in many application areas such as information technology (including quantum information and computing), manufacturing, transportation, planning, economics, finance, as well as service sectors. The research program focuses on modelling these problems and their mathematical generalizations as accurately as possible (and reasonable) by mathematical optimization problems. These mathematical optimization problems will typically lie in a special subclass (i.e., with additional special structures) of: (a) 0,1 mixed integer programming, or (b) semidefinite optimization problems where we seek low-rank solutions, or (c) semidefinite optimization problems where there are discrete variables, or (d) semidefinite optimization problems where we seek highest rank solutions,or (e) optimization problems defined by (possibly nonconvex) polynomial equations and inequalities. Since convex optimization problems form a very wide class of tractable mathematical optimization problems (under reasonable assumptions, such problems, when well-posed, can be solved to arbitrary accuracy in polynomial-time), the next step is the construction of a tractable convex approximation to the original, hard mathematical optimization problem. From a theoretical viewpoint, this approach provides a framework to design primal-dual algorithms. This framework then leads to, together with approximately optimal solutions, certificates of optimality. For hard problems, we can only hope for certificates of approximate optimality, hence for those, we focus on efficient approximation algorithms. This research program will advance the design, study and implementation of composite first--order and higher--order algorithms which focus on the big-data regime and adapt to the given data instance. These algorithms will combine the desired features of first--order algorithms: 1. low memory requirements, 2. low complexity per iteration, 3. distributability, 4. parallelizability; with those of second--order and higher--order algorithms: 5. much faster global convergence, 6. much, much faster local convergence, 7. high accuracy solutions, 8. robustness. Whenever feasible, the source codes of the resulting implementations as well as the data used for computational test and benchmarking will be made available on the web.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2020-04324
Name nom
Tuncel, Levent
Department département
Combinatorics and Optimization - Combinatorics and Optimization
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2021
Competition year année de concours
2020
Award amount
48000
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
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
Research subject code
2700
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Information technology
Research subject fr
Technologie de l'information
Installment
inst:2
Partie
1
Nb partie
5
Application title
Mathematical Optimization: Theory and Algorithms
Keyword
NSERC
Application summary
My research program aims to find tractable mathematical models for problems treated within computer science, and then focuses on the design, mathematical analysis and implementation of efficient and robust algorithms (solution methods) for such problems. These problems arise in many application areas such as information technology (including quantum information and computing), manufacturing, transportation, planning, economics, finance, as well as service sectors. The research program focuses on modelling these problems and their mathematical generalizations as accurately as possible (and reasonable) by mathematical optimization problems. These mathematical optimization problems will typically lie in a special subclass (i.e., with additional special structures) of: (a) 0,1 mixed integer programming, or (b) semidefinite optimization problems where we seek low-rank solutions, or (c) semidefinite optimization problems where there are discrete variables, or (d) semidefinite optimization problems where we seek highest rank solutions,or (e) optimization problems defined by (possibly nonconvex) polynomial equations and inequalities. Since convex optimization problems form a very wide class of tractable mathematical optimization problems (under reasonable assumptions, such problems, when well-posed, can be solved to arbitrary accuracy in polynomial-time), the next step is the construction of a tractable convex approximation to the original, hard mathematical optimization problem. From a theoretical viewpoint, this approach provides a framework to design primal-dual algorithms. This framework then leads to, together with approximately optimal solutions, certificates of optimality. For hard problems, we can only hope for certificates of approximate optimality, hence for those, we focus on efficient approximation algorithms. This research program will advance the design, study and implementation of composite first--order and higher--order algorithms which focus on the big-data regime and adapt to the given data instance. These algorithms will combine the desired features of first--order algorithms: 1. low memory requirements, 2. low complexity per iteration, 3. distributability, 4. parallelizability; with those of second--order and higher--order algorithms: 5. much faster global convergence, 6. much, much faster local convergence, 7. high accuracy solutions, 8. robustness. Whenever feasible, the source codes of the resulting implementations as well as the data used for computational test and benchmarking will be made available on the web.