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.

Abstract

This thesis focuses on trust-region methods used to minimize the sum of a smooth function f and a nonsmooth function h, possibly with inequality constraints. Our contributions are based upon an already existing algorithm that uses a quasi-Newton trust-region method named TR (Trust Region), to which we provide some corrections and clarifications. Utilizing TR as a foundation, we develop a new quasi-Newton trust-region method with diagonal Hessian approximations named TRDH (Trust Region with Diagonal Hessian approximations). With this method, we dispose from an analytical expression of a solution of the trust-region subproblem, unlike TR, which requires the use of an iterative solver. TRDH can also be used as a subproblem solver inside TR to solve the trust-region subproblem, instead of a quadratic regularization solver named R2 that is used by default. The convergence analysis of TR and TRDH is extended to unbounded Hessian approximations, provided that those approximations do not grow too quickly. We obtain a new complexity bound that is based upon a parameter controlling the growth of the Hessian approximations. This bound is also valid for smooth problems where h = 0. We show that our bound is sharp by constructing a function f for which it is attained when h = 0. We present an interior-point method used to minimize f + h with inequality constraints, named RIPM (Regularized Interior Proximal Method). Our algorithm uses TR or TRDH to solve a sequence of unconstrained barrier subproblems, whose objectives approach infinity near a bound of the initial problem. Our algorithms are available from the Julia packages RegularizedOptimization.jl and ShiftedProximalOperators.jl. Our tests are performed on problems of the package RegularizedProblems.jl, and our goal is primarily to reduce the number of objective and gradient evaluations of f. For all the tested problems, at least one variant of TRDH or TR with TRDH as subsolver performs better than R2 or TR with R2 as subsolver. We observe that RIPM is the most efficient solver on bound-contrained problems that require many iterations to converge, and that it performs similarly to TR, TRDH, and R2 on the other bound-constrained problems.