Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

École Polytechnique de Montréal

$20,000.00

Treatment of degeneracy and preconditioning in nonlinear programming

FY 2011-12

Summary
This proposal adresses some of the difficulties posed by real-world optimization problems. In practice, the regularity assumptions under which optimization algorithms are typically developed may not hold. Elastic methods embed interior-point methods and are effective on problems that do not satisfy a constraint qualification condition, whether they are general nonlinear programs or structured degenerate problems such as mathematical programs with equilibrium constraints and with vanishing constraints. However, little is known about their behavior in the presence of weakly active constraints. Iteratively solving symmetric saddle-point systems is currently difficult because preconditioning systems must be solved to high accuracy. I seek a cheap constraint preconditioner which may be applied via an iterative method and a loose tolerance. When approximating the (1,1) block with a symmetric positive definite matrix, preconditioning systems are equivalent to weighted least-squares problems. The latter can be interrupted before optimality. I believe that after an appropriate projection, the final iterate may be interpreted as the exact solution corresponding to another preconditioner. I am extracting properties of the latter from geometrical and spectral arguments. The solution of large-scale optimization systems governed by sets of discretized partial differential equations is challenging because the problem size makes factorizations unrealistic. Instead, matrix free methods must be employed. I am researching the recently-proposed trust funnel method in which linearized constraints are approximately satisfied by means of a new class of projected Krylov methods for unsymmetric augmented systems. I anticipate that it will open new perspectives on large-scale PDE-constrained problems and their efficient solution.
Program
Discovery Grants Program - Individual
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
299010-2009
Name nom
Orban, Dominique
Department département
Mathématiques et génie industriel
Organization id
64
Institution établissement
École Polytechnique de Montréal
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2011
Competition year année de concours
2009
Award amount
20000
Program id
RGPIN
Program nane 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
20
Committee name en
Industrial Engineering
Committee name fr
Génie industriel
Area of application code
703
Area of application group en
Transportation systems and services
Area of application group fr
Services et systèmes de transport
Area of application en
Aerospace
Area of application fr
Aérospatial
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
3
Nb partie
5
Application title
Treatment of degeneracy and preconditioning in nonlinear programming
Keyword
NSERC
Application summary
This proposal adresses some of the difficulties posed by real-world optimization problems. In practice, the regularity assumptions under which optimization algorithms are typically developed may not hold. Elastic methods embed interior-point methods and are effective on problems that do not satisfy a constraint qualification condition, whether they are general nonlinear programs or structured degenerate problems such as mathematical programs with equilibrium constraints and with vanishing constraints. However, little is known about their behavior in the presence of weakly active constraints. Iteratively solving symmetric saddle-point systems is currently difficult because preconditioning systems must be solved to high accuracy. I seek a cheap constraint preconditioner which may be applied via an iterative method and a loose tolerance. When approximating the (1,1) block with a symmetric positive definite matrix, preconditioning systems are equivalent to weighted least-squares problems. The latter can be interrupted before optimality. I believe that after an appropriate projection, the final iterate may be interpreted as the exact solution corresponding to another preconditioner. I am extracting properties of the latter from geometrical and spectral arguments. The solution of large-scale optimization systems governed by sets of discretized partial differential equations is challenging because the problem size makes factorizations unrealistic. Instead, matrix free methods must be employed. I am researching the recently-proposed trust funnel method in which linearized constraints are approximately satisfied by means of a new class of projected Krylov methods for unsymmetric augmented systems. I anticipate that it will open new perspectives on large-scale PDE-constrained problems and their efficient solution.