Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Waterloo

$25,000.00

New Efficient Methods for Challenging Computational Optimization Problems

FY 2016-17

Summary
There is a growing interest in, and demand for, efficient and practical computational optimization methods in numerous application domains. Our proposed research will develop methodology, and theoretical underpinnings and understanding, for three such problems in computational optimization. All three problems are hard, and computationally demanding, but progress on developing effective solutions will have broad impact not only in the field of optimization but across scientific computing and applications more generally. The first problem is to develop methods to find efficiency-enhancing structure in a user objective function code to allow for the efficient application of automatic differentiation (AD), applied in a structured way, to compute first and possibly second derivatives. This proposed effort builds on our previous work on AD for sparse problems, but the idea here is to find structure beyond sparsity. Our proposed technique involves understanding and manipulating the underlying computational graph (available through the use of 'reverse mode' AD). The second problem is to develop an effective procedure to find sparse solutions to optimization problems (the optimization themselves may or may not be sparse). This is an important problem because sparse solutions, in turn, yield efficient and robust models for various application modeling problems. Our approach is very novel but is related to a technique developed by the author (and colleagues) in the area of index tracking in finance. A sequence of approximations is created and optimization solutions are tracked from one approximation to the subsequent approximation. The final problem is similar but also different. It is to develop an effective optimization procedure for effective 'feature selection' in the support vector machine area. Effective feature selection can improve model interpretability and robustness. Our approach to 'feature selection' will draw heavily on previous work on piecewise differentiable problems, and problems with box constraints.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
327684-2012
Name nom
Coleman, Thomas
Department département
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
2012
Award amount
25000
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
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2705
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Software and development
Research subject fr
Logiciels et développement
Partie
5
Nb partie
5
Application title
New Efficient Methods for Challenging Computational Optimization Problems
Keyword
NSERC
Application summary
There is a growing interest in, and demand for, efficient and practical computational optimization methods in numerous application domains. Our proposed research will develop methodology, and theoretical underpinnings and understanding, for three such problems in computational optimization. All three problems are hard, and computationally demanding, but progress on developing effective solutions will have broad impact not only in the field of optimization but across scientific computing and applications more generally. The first problem is to develop methods to find efficiency-enhancing structure in a user objective function code to allow for the efficient application of automatic differentiation (AD), applied in a structured way, to compute first and possibly second derivatives. This proposed effort builds on our previous work on AD for sparse problems, but the idea here is to find structure beyond sparsity. Our proposed technique involves understanding and manipulating the underlying computational graph (available through the use of 'reverse mode' AD). The second problem is to develop an effective procedure to find sparse solutions to optimization problems (the optimization themselves may or may not be sparse). This is an important problem because sparse solutions, in turn, yield efficient and robust models for various application modeling problems. Our approach is very novel but is related to a technique developed by the author (and colleagues) in the area of index tracking in finance. A sequence of approximations is created and optimization solutions are tracked from one approximation to the subsequent approximation. The final problem is similar but also different. It is to develop an effective optimization procedure for effective 'feature selection' in the support vector machine area. Effective feature selection can improve model interpretability and robustness. Our approach to 'feature selection' will draw heavily on previous work on piecewise differentiable problems, and problems with box constraints.