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

G-2018-50

The conjugate residual method in linesearch and trust-region methods

et

La méthode des résidus minimaux (MINRES) de Paige et Saunders (1975), qui est souvent la méthode privilégiée pour les systèmes linéaires symétriques, est une généralisation de la méthode des résidus conjugués (CR) proposée par Hestenes et Stiefel (1952). Tout comme la méthode du gradient conjugué (CG), CR possède des propriétés souhaitables en optimisation sans contraintes mais n'est définie que pour des opérateurs symétriques définis positifs. La principale propriété de cette méthode est qu’elle minimise le résidu, ce qui la rend particulièrement intéressante pour les méthodes de type Newton inexact, généralement utilisées en recherche linéaire. L’utilisation de CR est également pertinente en régions de confiance puisqu’elle fait décroître les modèles quadratiques convexes de manière monotone (Fong et Saunders, 2012). Nous étudions des modifications rendant CR applicable, même en présence de courbure négative, et les comparons avec CG sur des problèmes convexes et non convexes. Notre étude se termine par une extension aux problèmes aux moindres carrés non linéaires. Nos tests révèlent que CR se comporte aussi bien ou mieux que CG, et effectue en général moins de produits opérateur-vecteur.

, 35 pages

Ce cahier a été révisé en mars 2019