Groupe d’études et de recherche en analyse des décisions

G-2019-04

Implementing a smooth exact penalty function for equality-constrained nonlinear optimization

, , et

Nous proposons un algorithm pour les problèmes d’optimisation non linéaire avec contraintes d’égalité basé sur une fonction de pénalité lisse proposée par Fletcher (1970). Bien que celle-ci soit souvent considérée trop coûteuse en pratique, nous montrons que les noyaux de calcul ne sont pas plus coûteux que dans d’autres méthodes typiques d’optimisation non linéaire. Le noyau principal permettant d'évaluer la fonction de pénalité et ses dérivées consiste à résoudre un système linéaire structuré. Nous montrons comment résoudre ce système de façon efficace en mémorisant une seule factorisation par itération lorsque les matrices sont disponibles explicitement. Nous montrons de plus comment adapter la fonction de pénalité au cas sans factorisation par le biais de résolution itérative des systèmes linéaires. La fonction de pénalité est prometteuse lorsqu’il est possible de résoudre les systèmes linéaires efficacement, comme par exemple dans les problèmes sous contraintes d’EDP où des préconditionneurs efficaces sont connus. Nous discutons quelques extensions telles que la régularisation de la fonction de pénalité et l’évaluation inexacte de la fonction de pénalité et de ses dérivées. Nous illustrons les mérites de cette approche et ses caractéristiques sur des problèmes provenant d’une collection standard ainsi que sur des problèmes sous contraintes d’EDP.

, 28 pages