<  Back to the Polytechnique Montréal portal

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

Marie-Ange Dahito

Masters thesis (2018)

[img]
Preview
Terms of Use: All rights reserved.
Download (1MB)
Cite this document: Dahito, M.-A. (2018). La méthode des résidus conjugués pour calculer les directions en optimisation continue (Masters thesis, École Polytechnique de Montréal). Retrieved from https://publications.polymtl.ca/3281/
Show abstract Hide abstract

Abstract

RÉSUMÉ : 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.

Open Access document in PolyPublie
Department: Département de mathématiques et de génie industriel
Academic/Research Directors: Dominique Orban and Serge Prudhomme
Date Deposited: 19 Nov 2018 11:39
Last Modified: 16 Jun 2021 17:10
PolyPublie URL: https://publications.polymtl.ca/3281/

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Repository Staff Only