Méthodes de région de confiance pour l'optimisation non lisse

Dans cette thèse, on s’intéresse aux méthodes de région de confiance utilisées pour la minimisation de la somme d’une fonction lisse f et d’une fonction non lisse h, éventuellement avec des contraintes d’inégalités. Nos contributions se basent sur un algorithme déjà existant, utilisant une méthode de région de confiance avec des approximations quasi-Newton appelée TR (Trust Region en anglais), et à laquelle nous apportons quelques corrections et clarifications. Nous développons une méthode de région de confiance inspirée de TR, mais utilisant des approximations quasi-Newton diagonales, appelée TRDH (Trust Region with Diagonal Hessian approximations en anglais). Cette méthode nous permet de résoudre le sous-problème de région de confiance de manière analytique, contrairement à TR qui utilise un algorithme itératif. TRDH peut également être utilisé comme sous-solveur de TR pour résoudre le sous-problème de région de confiance, à la place de l’algorithme de régularisation quadratique R2. L’analyse de convergence de TR et de TRDH est étendue dans le cas d’approximations de la matrice hessienne non bornées, sous réserve que la norme de ces approximations n’augmente pas trop vite. Nous obtenons une nouvelle borne de complexité, basée sur un paramètre contrôlant la croissance de la norme de ces approximations, qui est également applicable pour les problèmes lisses dans le cas où h = 0. Nous présentons une fonction f avec h = 0 pour laquelle notre nouvelle borne est atteinte. Nous élaborons une méthode de points intérieurs pour minimiser f + h avec des contraintes de bornes, appelée RIPM (Regularized Interior Proximal Method en anglais) Notre algorithme résout une suite de problèmes barrière non contraints, dont les objectifs s’approchent de l’infini à proximité d’une borne du problème initial, en utilisant une méthode de région de confiance similaire à TR ou à TRDH. Nos algorithmes sont disponibles dans les modules Julia RegularizedOptimization.jl et ShiftedProximalOperators.jl. Nos tests sont effectués sur des problèmes du module RegularizedProblems.jl, et nous nous intéressons principalement à limiter le nombre d’évaluations d’objectifs et de gradients de f. Pour l’en-semble des problèmes testés, au moins une des variantes de TRDH ou de TR avec TRDH comme sous-solveur est plus efficace que R2 ou que TR avec R2 comme sous-solveur. Nous constatons que RIPM est le plus performant pour résoudre des problèmes avec contraintes de bornes ayant besoin de beaucoup d’itérations pour converger, et qu’il affiche des performances similaires à celles de TR, TRDH et R2 sur les autres problèmes avec contraintes de bornes.