Aperçu des méthodes de gradient dans les problèmes d'optimisation mathématique

Préface

Cet article se concentrera sur les méthodes de résolution des problèmes d'optimisation mathématique basées sur l'utilisation d'un gradient de fonction. L'objectif principal est de rassembler dans l'article toutes les idées les plus importantes qui sont en quelque sorte liées à cette méthode et à ses diverses modifications.





UPD Dans les commentaires, ils écrivent que sur certains navigateurs et dans les formules d'application mobile ne sont pas affichées. Malheureusement, je ne sais pas comment y faire face. Je peux seulement dire que j'ai utilisé les macros «inline» et «display» de l'éditeur Habrava. Si vous savez soudain comment résoudre ce problème - écrivez dans les commentaires, s'il vous plaît.

Note de l'auteur

Au moment d'écrire ces lignes, j'ai défendu une thèse, dont la tâche m'a obligé à avoir une compréhension approfondie des méthodes fondamentalement théoriques d'optimisation mathématique. Néanmoins, mes yeux (de tout le monde) sont toujours flous des formules longues effrayantes, j'ai donc passé beaucoup de temps à isoler les idées clés qui caractériseraient différentes variations des méthodes de dégradé. Mon objectif personnel est d'écrire un article contenant le minimum d'informations nécessaires à une compréhension plus ou moins détaillée du sujet. Mais préparez-vous, on ne peut pas se passer de formules de toute façon.

Énoncé du problème

Avant de décrire la méthode, vous devez d'abord décrire le problème, à savoir: «Étant donné que $$$\ mathcal {K}$ et fonction $$$f: \ mathcal {K} \ rightarrow \ mathbb {R}$ besoin de trouver un point $$$x ^ * \ in \ mathcal {K}$ tel que $$$f (x) \ geq f (x ^ *)$ pour tous $$$x \ in \ mathcal {K}$ ", Qui est généralement écrit comme ceci

$$

$$f (x) \ rightarrow \ min_ {x \ in \ mathcal {K}}.$$

En théorie , on suppose généralement que $$$f$ Est une fonction différenciable et convexe, et $$$\ mathcal {K}$ - ensemble convexe (et encore mieux, le cas échéant) $$$\ mathcal {K} = \ mathbb {R} ^ n$ ), cela nous permet de donner quelques garanties du succès de l'application de la descente en gradient. En pratique, la descente de gradient est appliquée avec succès même lorsque la tâche ne possède aucune des propriétés ci-dessus (un exemple plus loin dans l'article).

Un peu de maths

Supposons pour l'instant que nous avons juste besoin de trouver un minimum d'une fonction unidimensionnelle

$$

$$f (x) \ rightarrow \ min_ {x \ in \ mathbb {R}}.$$

Au XVIIe siècle, Pierre Fermat propose un critère qui permet de résoudre des problèmes d'optimisation simples, à savoir si $$$x ^ *$ - point minimum $$$f ^ *$ alors

$$

$$f '(x ^ *) = 0$$

où $$$f '$ - dérivé $$$f$ . Ce critère est basé sur une approximation linéaire.

$$

$$f (x) \ environ f (x ^ *) + f '(x ^ *) (x-x ^ *).$$

Plus près $$$x$ à $$$x ^ *$ , plus cette approximation est précise. Sur le côté droit est une expression qui, lorsque $$$f '(x ^ *) \ neq 0$ peut-être comme plus $$$f (x ^ *)$ moins est l'essence principale du critère. Dans le cas multidimensionnel, de façon similaire à partir de l'approximation linéaire $$$f (x) \ environ f (x ^ *) + \ nabla f (x ^ *) ^ T (x-x ^ *)$ (ci-après $$$x ^ Ty = \ sum_ {i = 1} ^ nx_iy_i$ - produit scalaire standard, la forme d'écriture est due au fait que le produit scalaire est le même que le produit matriciel d'un vecteur ligne par un vecteur colonne), le critère est obtenu

$$

$$\ nabla f (x ^ *) = 0.$$

Valeur $$$\ nabla f (x ^ *)$ - gradient de fonction $$$f$ au point $$$x ^ *$ . De plus, l'égalité du gradient à zéro signifie l'égalité de toutes les dérivées partielles à zéro, par conséquent, dans le cas multidimensionnel, on peut obtenir ce critère simplement en appliquant séparément le critère unidimensionnel pour chaque variable.

Il est à noter que ces conditions sont nécessaires, mais pas suffisantes, l'exemple le plus simple est 0 pour $$$f (x) = x ^ 2$ et $$$f (x) = x ^ 3$


Ce critère est suffisant dans le cas d'une fonction convexe, en grande partie grâce à cela il a été possible d'obtenir autant de résultats pour les fonctions convexes.

Fonctions quadratiques

Fonctions quadratiques dans $$$\ mathbb {R} ^ n$ Est fonction du formulaire

$$

$$f (x) = f (x_1, x_2, \ ldots, x_n) = \ frac {1} {2} \ sum_ {i, j = 1} ^ na_ {ij} x_ix_j- \ sum_ {i = 1} ^ n b_ix_i + c$$

Pour économiser de l'espace (et moins gêner avec les index), cette fonction est généralement écrite sous forme matricielle:

$$

$$f (x) = \ frac {1} {2} x ^ TAx-b ^ Tx + c,$$

où $$$x = (x_1, \ ldots, x_n) ^ T$ , $$$b = (b_1, \ ldots, b_n) ^ T$ , $$$A$ Est une matrice à laquelle à l'intersection $$$i$ cordes et $$$j$ la colonne est la valeur
$$$\ frac {1} {2} (a_ {ij} + a_ {ji})$ ( $$$A$ il s'avère symétrique - c'est important). Ensuite. en mentionnant une fonction quadratique, j'aurai la fonction ci-dessus.

Pourquoi je parle de ça? Le fait est que les fonctions quadratiques sont importantes dans l'optimisation pour deux raisons:

1. Ils se produisent également dans la pratique, par exemple, lors de la construction d'une régression linéaire des moindres carrés
2. Le gradient d'une fonction quadratique est une fonction linéaire, en particulier pour la fonction ci-dessus
   

   $$

   $$\ frac {\ partial} {\ partial x_i} f (x_1, x_2, \ ldots, x_n) = a_ {ii} x_i + \ sum_ {j \ neq i} \ frac {1} {2} (a_ {ij } + a_ {ji}) x_j -b_i,$$
   
   Ou sous forme matricielle
   

   $$

   $$\ nabla f (x) = Axe-b,$$
   
   Ainsi, le système $$$\ nabla f (x) = 0$ - système linéaire. Un système plus simple que linéaire n'existe pas. La pensée à laquelle j'essayais d'arriver est l' optimisation d'une fonction quadratique - la classe la plus simple de problèmes d'optimisation . D'un autre côté, le fait que $$$\ nabla f (x ^ *) = 0$ - les conditions minimales nécessaires permettent de résoudre des systèmes linéaires par des problèmes d'optimisation. Un peu plus tard, je vais essayer de vous convaincre que cela a du sens.
   

Propriétés de dégradé utiles

Eh bien, nous semblons avoir découvert que si une fonction est différentiable (elle a des dérivées par rapport à toutes les variables), alors au minimum le gradient doit être égal à zéro. Mais le gradient contient-il des informations utiles lorsqu'il est différent de zéro?

Essayons de résoudre un problème plus simple: le point est donné $$$x$ trouver un point $$$\ bar {x}$ tel que $$$f (\ bar {x}) <f (x)$ . Prenons un point à côté de $$$x$ en utilisant à nouveau une approximation linéaire $$$f (\ bar {x}) \ environ f (x) + \ nabla f (x) ^ T (\ bar {x} -x)$ . Si vous prenez $$$\ bar {x} = x- \ alpha \ nabla f (x)$ , $$$\ alpha> 0$ alors nous obtenons

$$

$$f (\ bar {x}) \ approx f (x) - \ alpha \ | \ nabla f (x) \ | ^ 2 <f (x).$$

De même, si $$$\ alpha <0$ alors $$$f (\ bar {x})$ sera plus $$$f (x)$ (ci-après $$$|| x || = \ sqrt {x_1 ^ 2 + x_2 ^ 2 + \ ldots + x_n ^ 2} ~$ ) Encore une fois, puisque nous avons utilisé l'approximation, ces considérations ne seront vraies que pour les petites $$$\ alpha$ . Pour résumer ce qui précède, si $$$\ nabla f (x) \ neq 0$ , alors le gradient indique la direction de la plus grande augmentation locale de la fonction .

Voici deux exemples de fonctions bidimensionnelles. Des images de ce genre peuvent souvent être vues dans des démonstrations de descente en pente. Les lignes colorées sont les lignes dites de niveau , c'est un ensemble de points pour lesquels la fonction prend des valeurs fixes, dans mon cas ce sont des cercles et des ellipses. J'ai marqué les lignes bleues du niveau avec une valeur inférieure, rouge - avec une valeur supérieure.



Notez que pour une surface définie par une équation de la forme $$$f (x) = c$ , $$$\ nabla f (x)$ définit la normale (chez les gens ordinaires - la perpendiculaire) à cette surface. Notez également que bien que le gradient s'affiche dans le sens de la plus grande augmentation de la fonction, il n'y a aucune garantie que dans la direction opposée au gradient, vous pouvez trouver un minimum (par exemple, l'image de gauche).

Descente en pente

Il ne restait qu'un petit pas à la méthode de descente de gradient de base: nous avons appris du point $$$x$ obtenir un point $$$\ bar {x}$ avec une valeur de fonction inférieure $$$f$ . Qu'est-ce qui nous empêche de répéter cela plusieurs fois? En fait, c'est la descente du gradient: on construit la séquence

$$

$$x_ {k + 1} = x_k- \ alpha_k \ nabla f (x_k).$$

Valeur $$$\ alpha_k$ appelé la taille du pas (dans l'apprentissage automatique - la vitesse d'apprentissage ). Quelques mots sur le choix $$$\ alpha_k$ : si $$$\ alpha_k$ - très petite, la séquence change lentement, ce qui rend l'algorithme peu efficace; si $$$\ alpha_k$ très grand, alors l'approximation linéaire devient médiocre, et peut-être même incorrecte. En pratique, la taille du pas est souvent choisie empiriquement; en théorie, un gradient de Lipschitz est généralement supposé, à savoir, si

$$

$$\ | \ nabla f (x) - \ nabla f (y) \ | \ leq L \ | x-y \ |$$

pour tous $$$x, y$ alors $$$\ alpha_k <\ frac {2} {L}$ garanties diminuent $$$f (x_k)$ .

Analyse des fonctions quadratiques

Si $$$A$ Est une matrice inversible symétrique, $$$Ax ^ * = b$ puis pour la fonction quadratique $$$f (x) = \ frac {1} {2} x ^ TAx-b ^ Tx + c$ pointer $$$x ^ *$ est le point minimum ( UPD . à condition que ce minimum existe) $$$f$ ne prend pas de près $$$- \ infty$ valeurs uniquement si $$$A$ positif défini), et pour la méthode de descente de gradient, nous pouvons obtenir ce qui suit

$$

$$x_ {k + 1} -x ^ * = x_k- \ alpha_k \ nabla f (x_k) -x ^ * = x_k- \ alpha_k (Ax_k-b) -x ^ * =$$

$$

$$(x_k-x ^ *) - \ alpha_kA (x_k-x ^ *) = (I- \ alpha_k A) (x_k-x ^ *),$$

où $$$I$ Est la matrice d'identité, c'est-à-dire $$$Ix = x$ pour tous $$$x$ . Si $$$\ alpha_k \ equiv \ alpha$ ça va finir

$$

$$\ | x_ {k} -x ^ * \ | = \ | (I- \ alpha A) ^ k (x_0-x ^ *) \ | \ leq \ | I- \ alpha A \ | ^ k \ | x_0 -x ^ * \ |.$$

L'expression à gauche est la distance de l'approximation obtenue à l'étape $$$k$ descente de gradient vers le point minimum, à droite - une expression de la forme $$$\ lambda ^ k \ beta$ qui converge vers zéro si $$$| \ lambda | <1$ (la condition sur laquelle j'ai écrit $$$\ alpha$ dans le paragraphe précédent, c'est exactement ce qui garantit). Cette estimation de base garantit la convergence de la descente du gradient.

Modifications de descente de gradient

Maintenant, je voudrais parler un peu des modifications couramment utilisées de la descente de gradient, principalement ce qu'on appelle

Méthodes de gradient inertiel ou accéléré

Toutes les méthodes de cette classe sont exprimées comme suit

$$

$$x_ {k + 1} = x_k- \ alpha_k \ nabla f (x_k) + \ beta_k (x_k-x_ {k-1}).$$

Le dernier terme caractérise cette même «inertie», l'algorithme essaie à chaque pas de se déplacer contre le gradient, mais en même temps il se déplace partiellement par inertie dans le même sens que lors de l'itération précédente. Ces méthodes ont deux propriétés importantes:

1. Ils ne compliquent pratiquement pas la descente de gradient habituelle dans le plan de calcul.
2. Avec une sélection rigoureuse $$$\ alpha_k, \ beta_k$ ces méthodes sont d'un ordre de grandeur plus rapides qu'une descente de gradient ordinaire, même avec une étape sélectionnée de manière optimale.

L'une des premières de ces méthodes est apparue au milieu du 20e siècle et a été appelée la méthode de la balle lourde , qui traduisait la nature de l'inertie de la méthode: dans cette méthode $$$\ alpha_k, \ beta_k$ indépendant de $$$k$ et soigneusement sélectionnés en fonction de la fonction objectif. Il convient de noter que $$$\ alpha_k$ peut être tout sauf $$$\ beta_k$ - généralement un peu moins d'un .

La méthode de la balle lourde est la méthode inertielle la plus simple, mais pas la toute première. Dans ce cas, à mon avis, la toute première méthode est assez importante pour comprendre l'essence de ces méthodes.

Méthode Chebyshev

Oui, oui, la première méthode de ce type a été inventée par Chebyshev pour résoudre des systèmes d'équations linéaires. À un certain moment dans l'analyse de la descente de gradient, l'égalité suivante a été obtenue

$$

$$x_ {k + 1} -x ^ * = (I- \ alpha_k A) (x_k-x ^ *) = \ ldots =$$

$$

$$(I- \ alpha_kA) (I- \ alpha_ {k-1} A) \ ldots (I- \ alpha_1A) (x_0-x ^ *) = P_k (A) (x_0-x ^ *),$$

où $$$P_k$ Est un degré polynomial $$$k$ . Pourquoi ne pas essayer de ramasser $$$\ alpha_k$ pour que $$$P_k (A) (x_0-x ^ *)$ était-il plus petit? Un nœud de polynômes universels qui s'écartent le moins de zéro est le polynôme de Chebyshev. La méthode de Chebyshev consiste essentiellement à sélectionner les paramètres de descente afin que $$$P_k$ était un polynôme de Tchebychev. Il y a vraiment un petit problème: pour une descente à gradient normal, ce n'est tout simplement pas possible. Cependant, pour les méthodes inertielles, cela est possible. Cela est principalement dû au fait que les polynômes de Chebyshev satisfont la relation de récurrence de second ordre

$$

$$T_ {n + 1} (x) = 2xT_n (x) -T_ {n-1} (x),$$

par conséquent, ils ne peuvent pas être construits pour la descente de gradient, qui calcule une nouvelle valeur à partir d'une seule valeur précédente, et pour l'inertie, cela devient possible du fait que les deux valeurs précédentes sont utilisées. Il s'avère que la complexité du calcul $$$\ alpha_k, \ beta_k$ ne dépend pas de $$$k$ ni la taille de l'espace $$$n$ .

Méthode du gradient conjugué

Un autre fait très intéressant et important (une conséquence du théorème de Hamilton-Cayley): pour toute matrice carrée $$$A$ la taille $$$n \ fois n$ il y a un polynôme $$$P$ degré plus $$$n$ pour lequel $$$P (A) = 0$ . Pourquoi est-ce intéressant? C'est la même égalité

$$

$$x_ {k + 1} -x ^ * = P_k (A) (x_0-x ^ *).$$

Si nous pouvions choisir la taille du pas dans la descente du gradient de manière à obtenir exactement ce polynôme de mise à zéro, alors la descente du gradient convergerait pour un nombre d'itération fixe non supérieur à la dimension $$$A$ . Comme nous l'avons déjà découvert, nous ne pouvons pas le faire pour la descente en pente. Heureusement, pour les méthodes inertielles, nous le pouvons. La description et la justification de la méthode sont assez techniques, je me limiterai à l'essentiel: à chaque itération, des paramètres sont sélectionnés qui donnent le meilleur polynôme, qui peut être construit en tenant compte de toutes les mesures effectuées avant l'étape actuelle de la mesure du gradient . En même temps

1. Une itération de descente de gradient (sans tenir compte des calculs de paramètres) contient une multiplication matricielle par un vecteur et 2-3 ajouts de vecteur
2. Le calcul des paramètres nécessite également 1 à 2 multiplications matricielles par vecteur, 2 à 3 multiplications vectorielles scalaires par vecteur et plusieurs ajouts de vecteurs.

La chose la plus difficile dans le plan de calcul est la multiplication de la matrice par un vecteur, cela prend généralement du temps $$$\ mathcal {O} (n ^ 2)$ Cependant, pour une mise en œuvre spéciale, cela peut être fait en $$$\ mathcal {O} (m)$ où $$$m$ - le nombre d'éléments non nuls dans $$$A$ . Étant donné la convergence de la méthode du gradient conjugué, pas plus de $$$n$ les itérations obtiennent la complexité globale de l'algorithme $$$\ mathcal {O} (nm)$ , ce qui dans tous les cas n'est pas pire $$$\ mathcal {O} (n ^ 3)$ pour la méthode Gauss ou Cholesky, mais beaucoup mieux si $$$m << n ^ 2$ ce n'est pas si rare.

La méthode du gradient conjugué fonctionne également bien si $$$f$ n'est pas une fonction quadratique, mais elle ne converge pas en un nombre fini d'étapes et nécessite souvent de petites modifications supplémentaires

Méthode Nesterov

Pour les communautés d'optimisation mathématique et d'apprentissage automatique, le nom "Nesterov" est depuis longtemps un nom familier. Dans les années 80 du siècle dernier, Yu.E. Nesterov est venu avec une version intéressante de la méthode inertielle, qui a la forme

$$

$$x_ {k + 1} = x_k- \ alpha_k \ nabla f (x_k + \ beta_k (x_k-x_ {k-1})) + \ beta_k (x_k-x_ {k-1}),$$

cela n'implique aucun calcul compliqué $$$\ alpha_k, \ beta_k$ comme dans la méthode du gradient conjugué, en général, le comportement de la méthode est similaire à la méthode de la balle lourde, mais sa convergence est généralement beaucoup plus fiable à la fois en théorie et en pratique.

Descente de gradient stochastique

La seule différence formelle par rapport à la descente de gradient habituelle est l'utilisation d'une fonction au lieu d'un gradient $$$g (x, \ thêta)$ tel que $$$E_ \ theta g (x, \ theta) = \ nabla f (x)$ ( $$$E_ \ theta$ - attente aléatoire $$$\ theta$ ), donc la descente du gradient stochastique a la forme

$$

$$x_ {k + 1} = x_k- \ alpha_kg (x_k, \ theta_k).$$

$$$\ theta_k$ - Il s'agit d'un paramètre aléatoire que nous n'affectons pas, mais en même temps en moyenne nous allons à l'encontre du gradient. Par exemple, considérons les fonctions

$$

$$f (x) = \ frac {1} {2m} \ sum_ {j = 1} ^ m \ | x-y_j \ | ^ 2, ~~ \ nabla f (x) = \ frac {1} {m} \ sum_ {j = 1} ^ m (x-y_j)$$

et

$$

$$g (x, i) = x-y_i.$$

Si $$$i$ prend des valeurs $$$1, \ ldots, m$ tout aussi probablement juste moyen $$$g$ Est un dégradé $$$f$ . Cet exemple est également révélateur des éléments suivants: la complexité du calcul du gradient dans $$$m$ fois plus que la complexité de calcul $$$g$ . Cela permet une descente de gradient stochastique en même temps dans $$$m$ fois plus d'itérations. Malgré le fait que la descente de gradient stochastique converge généralement plus lentement que d'habitude, en raison d'une augmentation si importante du nombre d'itérations, il est possible d'améliorer le taux de convergence par unité de temps. Pour autant que je sache, à l'heure actuelle, la descente de gradient stochastique est la méthode de base pour former la plupart des réseaux de neurones, implémentée dans toutes les principales bibliothèques ML: tensorflow, torch, caffe, CNTK, etc.

Il convient de noter que les idées de méthodes inertielles sont utilisées pour la descente de gradient stochastique et, dans la pratique, donnent souvent une augmentation, en théorie, il est généralement supposé que le taux de convergence asymptotique ne change pas car la principale erreur de descente de gradient stochastique est due à la dispersion $$$g$ .

Descente en sous-gradient

Cette variation vous permet de travailler avec des fonctions non différenciables, je vais la décrire plus en détail. Il faudra à nouveau rappeler l'approximation linéaire - le fait est qu'il existe une caractéristique simple de la convexité à travers un gradient, une fonction différenciable $$$f$ convexe si et seulement si $$$f (y) \ geq f (x) + \ nabla f (x) ^ T (y-x)$ pour tous $$$x, y$ . Il s'avère qu'une fonction convexe ne doit pas nécessairement être différenciable, mais en tout point $$$x$ il y a certainement un tel vecteur $$$g$ ça $$$f (y) \ geq f (x) + g ^ T (y-x)$ pour tous $$$y$ . Un tel vecteur $$$g$ communément appelé premier cycle $$$f$ au point $$$x$ , l'ensemble de tous les sous-gradients aux points $$$x$ appelé subdifférentiel $$$x$ et dénote $$$\ partiel f (x)$ (malgré la désignation - cela n'a rien à voir avec les dérivés partiels). Dans le cas unidimensionnel $$$g$ Est un nombre, et la propriété ci-dessus signifie simplement que le graphique $$$f$ se trouve au-dessus de la ligne passant $$$(x, f (x))$ et ayant une pente $$$g$ (voir photos ci-dessous). Je note qu'il peut y avoir plusieurs sous-gradients pour un point, même un nombre infini.



Il n'est généralement pas très difficile de calculer au moins un sous-gradient pour un point; une descente de sous-gradient utilise essentiellement un sous-gradient au lieu d'un gradient. Il s'avère que cela suffit; en théorie, le taux de convergence diminue, cependant, par exemple, dans les réseaux de neurones, une fonction indifférenciable $$$ReLU (x) = \ max (0, x)$ ils aiment l'utiliser juste parce que l'entraînement est plus rapide avec lui (c'est, en passant, un exemple d'une fonction non convexe non différenciable dans laquelle la descente (sub) gradient est appliquée avec succès. La fonction elle-même $$$Relu$ réseau de neurones convexe mais multicouche contenant $$$Relu$ , non convexe et non différenciable). Par exemple, pour une fonction $$$f (x) = | x |$ le sous-différentiel est calculé très simplement

$$

$$\ partial f (x) = \ begin {cases} 1, & x> 0, \\ -1, & x <0, \\ [-1, 1], & x = 0. \ end {cases}$$

La dernière chose importante à savoir est peut-être que la descente en sous-gradient ne converge pas à une taille de pas constante . C'est plus facile à voir pour la fonction ci-dessus. $$$f (x) = | x |$ . Même l'absence d'un dérivé à un moment donné rompt la convergence:

1. Disons que nous sommes partis du point $$$x_0$ .
2. Étape de descente en sous-gradient:
   

   $$

   $$x_ {k + 1} = \ begin {cases} x_ {k} -1, & x> 0, \\ x_k + 1, & x <0, \\ ??? & x = 0. \ end {cases}$$
3. Si $$$x_0> 0$ puis les premières étapes, nous soustraireons un, si $$$x_0 <0$ puis ajoutez. D'une manière ou d'une autre, nous nous retrouverons à un moment donné dans l'intervalle $$$[0, 1)$ d'où nous arrivons $$$[- 1, 0)$ , puis nous sauterons entre deux points de ces intervalles.

En théorie, pour une descente en sous-gradient, il est recommandé de suivre une séquence d'étapes

$$

$$\ alpha_k = \ frac {1} {(k + 1) ^ c}.$$

O Where $$$c$ habituellement $$$1$ ou $$$\ frac {1} {2}$ . Dans la pratique, j'ai souvent vu des étapes réussies $$$\ alpha_k = e ^ {- ck}$ , bien que pour de telles étapes, il n'y ait généralement pas de convergence.

Méthodes proximales

Malheureusement, je ne connais pas une bonne traduction de «proximal» dans le contexte de l'optimisation, c'est pourquoi je vais simplement appeler cette méthode. Les méthodes proximales sont apparues comme une généralisation des méthodes de gradient projectif. L'idée est très simple: s'il y a une fonction $$$f$ représenté comme une somme $$$f (x) = \ varphi (x) + h (x)$ où $$$\ varphi$ Est une fonction convexe différenciable, et $$$h (x)$ - convexe, pour lequel il existe un opérateur proximal spécial $$$prox_h (x)$ (dans cet article je me limiterai uniquement à des exemples, je ne décrirai pas en termes généraux), puis les propriétés de convergence de la descente de gradient pour $$$\ varphi$ rester et pour une descente en pente pour $$$f$ si après chaque itération appliquer cet opérateur proximal pour le point courant $$$x_k$ , en d'autres termes, la forme générale de la méthode proximale ressemble à ceci:

$$

$$x_ {k + 1} = prox _ {\ alpha_kh} (x_k- \ alpha_k \ nabla \ varphi (x_k))$$

Je pense que jusqu'à présent, il est totalement incompréhensible pourquoi cela peut être nécessaire, d'autant plus que je n'ai pas expliqué ce qu'est un opérateur proximal. Voici deux exemples:

1. $$$h (x)$ - fonction indicateur d'un ensemble convexe $$$\ mathcal {K}$ c'est
   

   $$

   $$h (x) = \ begin {cases} 0, & x \ in \ mathcal {K}, \\ + \ infty, & x \ notin \ mathcal {K}. \\ \ end {cases}$$
   
   Dans ce cas $$$prox _ {\ alpha_kh} (x)$ Est une projection sur le plateau $$$\ mathcal {K}$ , c'est-à-dire "le plus proche de $$$x$ point de consigne $$$\ mathcal {K}$ ". Ainsi, nous limitons la descente du gradient uniquement à l'ensemble $$$\ mathcal {K}$ , ce qui nous permet de résoudre des problèmes avec des restrictions. Malheureusement, le calcul de la projection dans le cas général peut être encore plus difficile, donc cette méthode est généralement utilisée si les contraintes sont simples, par exemple, les soi-disant contraintes de boîte: pour chaque coordonnée
   

   $$

   $$l_i \ leq x_i \ leq r_i$$
   
   
2. $$$h (x) = \ lambda \ | x \ | _1 = \ lambda \ sum_ {i = 1} ^ n | x_i |$ - $$$\ ell_1$ -régularisation. Ils aiment ajouter ce terme aux problèmes d'optimisation de l'apprentissage automatique afin d'éviter le recyclage. Une telle régularisation tend également à annuler les composants les moins significatifs. Pour une telle fonction, l'opérateur proximal a la forme (une expression pour une seule coordonnée est décrite ci-dessous):
   

   $$

   $$[prox _ {\ alpha h} (x)] _ i = \ begin {cases} x_i- \ alpha, & x_i> \ alpha, \\ x_i + \ alpha, & x_i <- \ alpha, \\ 0, & x_i \ dans [- \ alpha, \ alpha], \ end {cases}$$
   
   ce qui est assez facile à calculer.

Conclusion

Ceci met fin aux principales variations de la méthode du gradient que je connais. Peut-être qu'à la fin je noterais que toutes ces modifications (sauf peut-être la méthode du gradient conjugué) peuvent facilement interagir les unes avec les autres. Je n'ai délibérément pas inclus la méthode Newton et les méthodes quasi-Newton (BFGS et autres) dans cette liste: bien qu'elles utilisent un gradient, ce sont des méthodes plus complexes et nécessitent des calculs supplémentaires spécifiques, qui sont généralement plus coûteux en calcul que le calcul d'un gradient. Néanmoins, si ce texte est demandé, je serai heureux de faire un examen similaire à leur sujet.

Littérature utilisée / recommandée

Boyd. S, Vandenberghe L. Optimisation convexe
Shewchuk JR Une introduction à la méthode du gradient conjugué sans la douleur agonisante
Théorie d'optimisation convexe DP de Bertsekas

Nesterov Yu. E. Méthodes d'optimisation convexes
Descente à gradient universel Gasnikov A.V.