Nous étendons les analyses de complexité traditionnelles des méthodes de régions de confiance pour l'optimisation sans contrainte, possiblement non convexe. Alors que la plupart des analyses de complexité supposent que les hessiennes du modèle sont uniformément bornées, nous travaillons avec des hessiennes de modèle potentiellement non bornées. La bornitude n'est pas garantie dans les implémentations pratiques, en particulier celles basées sur des mises à jour quasi-Newton telles que PSB, BFGS et SR1. Notre analyse est menée pour une famille de méthodes de régions de confiance qui inclut la plupart des méthodes connues comme cas particuliers. Nous examinons deux régimes de croissance de la Hessienne : l'un borné par une puissance du nombre d'itérations réussies, et l'autre borné par une puissance du nombre d'itérations total. Cela nous permet de formaliser et d'adresser l'intuition de Powell (2010), qui a étudié la convergence sous un cas spécial de nos hypothèses, mais dont la preuve contenait des arguments de complexité. Plus précisément, pour \(0 \leq p < 1\), nous établissons une complexité d'évaluation en \(O([(1-p)\epsilon^{-2}]^{1/(1-p)})\) pour trouver un point \(\epsilon\)-stationnaire lorsque les hessiennes du modèle sont en \(O(|\mathcal{S}_{k-1}|^p)\), où \(|\mathcal{S}_{k-1}|\) est le nombre d'itérations réussies jusqu'à l'itération \(k-1\). Pour \(p = 1\), qui est le cas étudié par Powell, nous établissons une complexité d'évaluation \(O(\exp(c_1\epsilon^{-2}))\) pour une certaine constante \(c_1 > 0\). C'est bien mieux que la borne exponentielle double que Powell soupçonnait, et c'est bien pire que d'autres bornes supposées ailleurs dans la littérature. Nous établissons des bornes similaires lorsque les hessiennes du modèle sont en \(O(k^p)\), où k est le compteur d'itérations, pour \(0 \leq p < 1\). Cependant, lorsque \(p = 1\), la complexité peut atteindre \(O((1 - \log(\epsilon))\exp(c_2\epsilon^{-2}))\), pour une certaine constante \(c_2 > 0\). Nous établissons des nouvelles bornes de complexité pour le cas spécial des objectifs (fortement) sous les mêmes hypothèses.