G-2024-64
A proximal modified quasi-Newton method for nonsmooth regularized optimization
, et référence BibTeX
Nous développons R2N, une méthode quasi-Newton modifiée pour minimiser la somme d'une fonction \(\mathcal{C}^1\)
\(f\)
et d'une fonction \(h\)
semi-continue inférieurement et prox-bornée.
Les fonctions \(f\)
et \(h\)
peuvent toutes deux être non convexes.
À chaque itération, notre méthode calcule un pas en minimisant la somme d'un modèle quadratique de \(f\)
, d'un modèle de \(h\)
, et d'un terme de régularisation quadratique adaptatif.
Un pas peut être calculé au moyen d'une variante de la méthode du gradient proximal.
Un avantage de R2N par rapport aux méthodes de région de confiance concurrentes est que les opérateurs proximaux n'impliquent pas d'indicateur de région de confiance supplémentaire.
Nous développons également la variante R2DH, dans laquelle la hessienne du modèle est diagonale, ce qui permet de calculer un pas sans avoir recours à un solveur de sous-problème lorsque \(h\)
est séparable.
R2DH peut être utilisé comme solveur autonome, mais aussi comme solveur pour le sous-problème de R2N.
Nous décrivons également des variantes non monotones de R2N et R2DH.
La convergence globale d’une mesure de stationnarité de premier ordre vers zéro est garantie sans supposer que \(\nabla f\)
est (localement) Lipschitz continue, et sans imposer aux hessiennes du modèle d’être uniformément bornée, une hypothèse particulièrement pertinente pour les modèles quasi-Newton.
Sous l’hypothèse que \(\nabla f\)
est Lipschitz continue, nous établissons une borne de complexité d'évaluation atteinte dans le pire des cas de \(O(1 / \epsilon^{2/(1 - p)})\)
pour amener ladite mesure sous \(\epsilon > 0\)
, où \(0 \leq p < 1\)
contrôle la croissance des hessiennes du modèle.
Plus précisément, ces dernières ne doivent pas diverger plus rapidement que \(|\mathcal{S}_k|^p\)
, où \(\mathcal{S}_k\)
est l'ensemble des itérations réussies jusqu'à l'itération \(k\)
.
Lorsque \(p = 1\)
, nous établissons la borne de complexité exponentielle atteinte \(O(\exp(c \epsilon^{-2}))\)
, où \(c > 0\)
est une constante.
Nous décrivons notre implémentation en Julia et rapportons des expériences numériques sur un problème classique de poursuite de base, un problème de débruitage d'image, un problème de complétion matricielle de rang minimal, et une machine à vecteurs de support non linéaire.
En particulier, le problème de rang minimal ne peut pas être résolu directement à ce jour par une approche de région de confiance car les opérateurs proximaux correspondants ne sont pas connus analytiquement.
Paru en septembre 2024 , 24 pages
Axe de recherche
Application de recherche
Document
G2464.pdf (630 Ko)