La méthode des résidus conjugués pour calculer les directions en optimisation continue

La méthode du gradient conjugué (CG) est une méthode proposée par Hestenes et Stiefel afin de résoudre des systèmes linéaires symétriques et définis positifs. En optimisation non linéaire sans contraintes, on y recourt de manière quasi-systématique pour le calcul des directions. Lorsque la matrice du système n'est pas définie positive, la variante en recherche linéaire proposée par Dembo et Steihaug, et celle de Steihaug en régions de confiance, permettent tout de même d'utiliser CG. La méthode des résidus conjugués (CR) est également proposée par Hestenes et Stiefel pour les cas où la matrice est définie positive. Elle partage avec CG la décroissance monotone du modèle quadratique, ce qui en fait un bon candidat pour les méthodes de région de confiance. De plus, les résidus dans CR décroissent de manière monotone, ce qui est intéressant, en particulier pour les méthodes de type Newton inexact, souvent utilisées en recherche linéaire. Dans cet ouvrage, nous proposons des variantes de CR pour les cas où la matrice n'est pas définie positive et étudions la performance de ces modifications dans des contextes de recherche linéaire et de région de confiance. Pour ce faire, nous comparons la performance de nos algorithmes aux variantes de CG correspondantes. Nous nous intéressons également à CRLS qui est l'équivalent de CR pour les moindres carrés linéaires, et suggérons une modification de cette méthode pour traiter le cas de la courbure nulle. Nos résultats montrent que CR est essentiellement équivalente à CG, et parfois meilleur, notamment pour résoudre les problèmes non convexes. CR présente aussi un léger avantage dans la résolution de problèmes convexes en recherche linéaire. Cette méthode permet souvent d'effectuer moins de produits hessien-vecteur que CG. La résolution des problèmes aux moindres carrés non linéaires montre une équivalence en termes de performance entre LSMR et LSQR qui sont les variantes, construites à partir du processus de Lanczos, de CRLS et CGLS pour résoudre l'équation normale. LSMR montre néanmoins un léger avantage en termes d'évaluation du résidu.

Abstract

The conjugate gradient method (CG) is a proven method for computing directions in unconstrained nonlinear optimization. This method, described by Hestenes and Stiefel, solves symmetric positive-definite linear systems. If the operator is not positive definite, the extension proposed by Dembo and Steihaug for linesearch and that of Steihaug for trust regions, make CG suitable again. The conjugate residual method (CR) was also proposed by Hestenes and Stiefel for positivedefinite operators. Like CG, CR makes the quadratic model decrease monotonically, which makes it relevant in a trust-region context. But CR also makes the residual decrease monotonically, a particularly interesting property for inexact Newton methods, often used in a linesearch context. In linesearch and trust-region contexts, we propose modifications of CR when the operator is not positive definite, and compare their performance with those of the corresponding extensions of CG. Our tests show that CR is, for the most part, equivalent to CG. It performs better than CG on nonconvex problems, and slightly better on convex problems in a linesearch context. The advantage is often in terms of operator-vector products. Finally, we consider the CRLS variant of CR for linear least-squares and investigate the case of zero curvature. We perform experiments with LSMR and LSQR, which are the versions of CRLS and CGLS built from the Lanczos process, to solve the normal equation. This reveals that LSMR performs as well as LSQR and enables slight savings in terms of residual evaluations.