Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Waterloo

$29,000.00

Design, analysis and implementation of algorithms utilizing convex optimization

FY 2016-17

Summary
My research program aims to design, analyze and implement efficient and robust algorithms (solution methods) for problems arising in many application areas such as planning, manufacturing, transportation, finance, as well as service sectors, and information technology (including quantum information and computing). The approach will model these problems and their mathematical generalizations as accurately and reasonably as possible 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) optimization problems defined by (possibly nonconvex) polynomial 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 good solutions, certificates of optimality. For hard problems, we can only hope for certificates of approximate optimality, hence approximation algorithms. 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. On the theoretical side of the research program lies the subjects of: (i) lift-and-project methods, (ii) tractable lifted semidefinite representation and relaxations, (iii) interior-point algorithms for semidefinite optimization, hyperbolic cone programming and beyond, (iv) designing convex relaxations and representations based on hyperbolic cone programming.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2015-05546
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
2016
Competition year année de concours
2015
Award amount
29000
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
801
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
Computer software
Area of application fr
Logiciel
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
Design, analysis and implementation of algorithms utilizing convex optimization
Keyword
NSERC
Application summary
My research program aims to design, analyze and implement efficient and robust algorithms (solution methods) for problems arising in many application areas such as planning, manufacturing, transportation, finance, as well as service sectors, and information technology (including quantum information and computing). The approach will model these problems and their mathematical generalizations as accurately and reasonably as possible 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) optimization problems defined by (possibly nonconvex) polynomial 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 good solutions, certificates of optimality. For hard problems, we can only hope for certificates of approximate optimality, hence approximation algorithms. 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. On the theoretical side of the research program lies the subjects of: (i) lift-and-project methods, (ii) tractable lifted semidefinite representation and relaxations, (iii) interior-point algorithms for semidefinite optimization, hyperbolic cone programming and beyond, (iv) designing convex relaxations and representations based on hyperbolic cone programming.