Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Waterloo

$34,000.00

Theory and Efficient Algorithms for Hard, Large Scale, Numerical Optimization

EF 2014-15

Résumé
The focus of my research will be the proper modelling of hard problems, and the design and implementation of efficient and robust numerical algorithms for large scale, hard, optimization problems. The problems I will deal with arise in many important applications, e.g. molecular conformation (MC), sensor network localization (SNL), inverse imaging and machine learning. In particular, many of these problems arise in the relaxations of hard combinatorial optimization problems. In many instances, the usual modelling approaches result in problems that are both large scale and ill-posed. Therefore, they are hard to solve numerically. Rather than being a disadvantage, one can often take advantage of the ill-posedness to get both a stable problem and one that is smaller in size. In particular, for problems such as SNL one can solve huge problems to high accuracy by exploiting the hidden degeneracy. I plan on applying this technique to MC problems with noisy data as well as to protein design problems. The techniques that I use involve continuous optimization, nonlinear programming (NLP) and in particular, semidefinite programming (SDP). For SDP, my research contributions involve theory, algorithms, and applications, i.e., they include strong duality results, stable algorithms, and the study of relaxations for various applications. Some of the codes that I have designed for the standard form Linear Programming (LP) model have already been implemented in MAPLE. I plan to implement algorithms for more general LP models that include both upper and lower bounds on the variables. As well I plan on implementing codes that solve more general NLP problems. For the NLP problems, I use algorithms for generalized trust region problems to solve large scale unconstrained minimization, as well as solve general NLP using stable sequential quadratic programming methods. The success of these implementations means that researchers in my field will have access to stable, high accuracy, algorithms.
Programme
Discovery Grants Program - Individual
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
9161-2013
Name nom
Wolkowicz, Henry
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
2014
Competition year année de concours
2013
Award amount
34000
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
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
2956
Research subject group en
Applied mathematics
Research subject group fr
Mathématiques appliquées
Research subject en
Optimisation and optimal control theory
Research subject fr
Optimisation et théories de commande optimale
Partie
2
Nb partie
5
Application title
Theory and Efficient Algorithms for Hard, Large Scale, Numerical Optimization
Keyword
NSERC
Application summary
The focus of my research will be the proper modelling of hard problems, and the design and implementation of efficient and robust numerical algorithms for large scale, hard, optimization problems. The problems I will deal with arise in many important applications, e.g. molecular conformation (MC), sensor network localization (SNL), inverse imaging and machine learning. In particular, many of these problems arise in the relaxations of hard combinatorial optimization problems. In many instances, the usual modelling approaches result in problems that are both large scale and ill-posed. Therefore, they are hard to solve numerically. Rather than being a disadvantage, one can often take advantage of the ill-posedness to get both a stable problem and one that is smaller in size. In particular, for problems such as SNL one can solve huge problems to high accuracy by exploiting the hidden degeneracy. I plan on applying this technique to MC problems with noisy data as well as to protein design problems. The techniques that I use involve continuous optimization, nonlinear programming (NLP) and in particular, semidefinite programming (SDP). For SDP, my research contributions involve theory, algorithms, and applications, i.e., they include strong duality results, stable algorithms, and the study of relaxations for various applications. Some of the codes that I have designed for the standard form Linear Programming (LP) model have already been implemented in MAPLE. I plan to implement algorithms for more general LP models that include both upper and lower bounds on the variables. As well I plan on implementing codes that solve more general NLP problems. For the NLP problems, I use algorithms for generalized trust region problems to solve large scale unconstrained minimization, as well as solve general NLP using stable sequential quadratic programming methods. The success of these implementations means that researchers in my field will have access to stable, high accuracy, algorithms.