Algorithmes du premier ordre

Algorithmes du premier ordre

l n’y pas d’algorithme meilleur que tout autre quel que soit le critère de performance que l’on adopte, même dans le champ restreint de l’optimisation sans contrainte. Les critères d’appréciation sont en effet multiples : vitesse de convergence des suites générées ou de la valeur optimale, coût interne (nombre d’opérations) ou externe (nombre d’évaluations de fonctions) de l’itération, complexité itérative de l’algorithme (nombre total d’itérations pour atteindre un seuil donné), espace mémoire requis, etc. On trouve plutôt tout un éventail de méthodes plus ou moins bien adaptées à des problèmes particuliers. Il faut donc bien connaître les caractéristiques de ces algorithmes pour qu’en présence d’un problème donné, l’on puisse faire un choix à bon escient. Ce chapitre présente un premier ensemble de techniques qui sont toutes utiles à des degrés divers et selon le contexte ; cela sera précisé aux cours des sections qui leur sont consacrées. Elles ont la caractéristique d’être du premier ordre, c’est-à-dire de n’utiliser de la fonction à minimiser, que sa valeur et sa dérivée première. L’algorithme du gradient est une bien mauvaise méthode (elle converge trop lentement), mais son analyse sert de référence à l’étude d’autres algorithmes plus complexes; nous l’aborderons à la section 7.1. Le chapitre étudie l’algorithme proximal pour la minimisation de fonctions convexes (section 7.2). Celui-ci, bien que non implémentable en pratique, sera utilisé pour interpréter certains algorithmes de dualité au chapitre 14. Connaissances supposées. La section 7.2 sur l’algorithme proximal suppose connues les notions de sous-différentiabilité de fonctions convexes, de point proximal et de régularisée de Moreau-Yosida (sections 3.6 et 3.7).

Algorithme du gradient

On ne le répétera sans doute jamais assez : l’algorithme du gradient est une très mauvaise méthode d’optimisation ! La preuve en est qu’elle requiert génériquement un nombre infini d’itérations pour minimiser une fonction quadratique strictement convexe de deux variables. Sachant que ce problème est équivalent à la résolution d’un système linéaire de deux équations à deux inconnues, dont la solution peut s’obtenir manuellement par élimination d’une des deux variables, on comprend l’ampleur de l’inefficacité. Pire, si le rapport des valeurs propres du hessien de la fonction est grand (mauvais conditionnement du problème), une précision raisonnable sur la solution ne peut jamais être atteinte en un temps de calcul supportable. L’opinion la plus couramment rencontrée est qu’il est toujours préférable d’utiliser l’algorithme de BFGS à mémoire limitée (section 11.2.5), qui a un champ d’application à peu près identique implémenter. Cette opinion reste vraie selon nous, mais ne condamne pas pour autant l’algorithme du gradient. D’abord, on ne peut se passer de son étude, car elle sert de base à celle d’algorithmes plus complexes. Ensuite, il permet d’interpréter d’autres algorithmes qui ne se présentent pas dans leur conception comme un algorithme de gradient, mais qui y sont apparentés (nous pensons à la relaxation lagrangienne et à la méthode des multiplicateurs). Enfin, l’utilisation de l’optimisation dans de nouvelles applications (traitement du signal, analyse des données massives, apprentissage, etc [470, 568]) a remis cet algorithme et ses variantes au goût du jour. Dans cette section, E est un espace euclidien, dont le produit scalaire est noté h·, ·i et la norme associée est notée k · k. L’espace vectoriel E étant supposé de dimension finie, le nombre de variables des problèmes d’optimisation posés sur E en est la dimension n := dim E. 

Définition

On s’intéresse dans cette section au problème de minimisation sans contrainte f∗ := inf x∈E f(x), où f : Ω → R est une fonction définie et différentiable sur un ouvert Ω ⊆ E. L’algorithme du gradient (ou de la plus profonde descente) a déjà été introduit à la section 6.2.1. Il génère une suite {xk} ⊆ E par la récurrence xk+1 = xk − αkgk, (7.1) où gk = ∇f(xk) est le gradient de f pour le produit scalaire de E et αk > 0 est un pas déterminé par recherche linéaire (section 6.3). Il s’agit donc d’un algorithme à directions de descente (chapitre 6), dont les directions sont les antigradients −gk, des directions opposées au gradient. Ces directions ont la particularité d’avoir un angle de descente θk défini en (6.2) qui est nul, si bien que son cosinus vaut un : ∀ k > 1 : cos θk = 1. (7.2) Cette particularité implique des résultats de convergence et de complexité itérative aisé à déterminer. Le lemme suivant est utilisé pour étudier la vitesse de convergence de la méthode du gradient.

Algorithme proximal 

Définition 

Soit E un espace euclidien (produit scalaire h·, ·i et norme associée k · k). À un opérateur auto-adjoint défini positif M, on associe le produit scalaire h·, ·iM : (u, v) ∈ E × E 7→ hu, viM := hMu, vi et la norme k · kM : u ∈ E 7→ kukM := hu, ui 1/2 M . On s’intéresse dans cette section à la minimisation d’une fonction f ∈ Conv(E) (c.-à-d., propre, convexe et fermée), qui n’est pas nécessairement différentiable. Soit {Mk} une suite d’opérateurs auto-adjoints définis positifs, qui seront utilisés comme préconditionneurs de l’algorithme proximal présenté ci-après, et peuvent être générés au fur et à mesure que l’algorithme progresse. Rappelons que le point proximal d’un point x ∈ E, associé à la fonction f et à l’opérateur Mk, est le point noté et défini par Pk(x) := arg min y∈E  f(y) + 1 2 ky − xk 2 R −1 k  . (7.3) Cette notion a été introduite à la section 3.7.1. Nous ferons évidemment souvent référence aux résultats de cette section. Par la condition nécessaire et suffisante d’optimalité du problème dans (7.3), on a xp = Pk(x) ⇐⇒ ∃ gp ∈ ∂f(xp) : xp = x − Rkgp. 328 7. Algorithmes du premier ordre où le sous-différentiel ∂f(x) est calculé pour le produit scalaire originel h·, ·i. L’algorithme proximal génère une suite {xk} par la formule xk+1 := Pk(xk) = xk − Rkgk+1, où gk+1 ∈ ∂f(xk+1). (7.4) On peut interpréter cet algorithme de diverses manières. 1) C’est une méthode de sous-gradient implicite pour minimiser f. Le sous-gradient gk+1 est en effet évalué en xk+1 (qui est inconnu), plutôt qu’en xk (dans l’algorithme du gradient de la section 7.1). Donc l’équation (7.4) est non linéaire en xk+1, si bien que le nouvel itéré xk+1 s’obtiendra en général par un procédé itératif, par exemple celui qui consiste à résoudre itérativement le problème d’optimisation dans (7.3). 2) C’est un algorithme à directions de descente sur f avec pas unité. La direction −Rkgk+1 est en effet une direction de descente de f en xk parce que Rkgk+1 est une direction de montée en xk+1 et que f est convexe. On a en effet f ′ (xk+1; Rkgk+1) > hgk+1, Rkgk+1i > 0, (7.5) où la première inégalité vient du fait que gk+1 ∈ ∂f(xk+1) (point (i) de la proposition 3.55). Puis, par le point (iv) de la proposition 3.19 et (7.4) : f ′ (xk; xk+1−xk) 6 −f ′ (xk+1; xk−xk+1) = −f ′ (xk+1; Rkgk+1) 6 0. On observe aussi que l’algorithme s’impose systématiquement un pas unité le long de la direction −Rkgk+1. On constate aussi que ce pas fait décroître f à chaque itération, puisqu’en prenant y = xk dans (7.3), on obtient f(xk+1) 6 f(xk+1) + 1 2 kxk+1 − xkk 2 R −1 k 6 f(xk). (7.6) 3) C’est l’algorithme du gradient, pour le produit scalaire h·, ·iR −1 k , avec pas unité, pour minimiser la régularisée de Moreau-Yosida de f, à savoir la fonction ˜f : x ∈ E 7→ ˜f(x) := inf y∈E  f(y) + 1 2 ky − xk 2 R −1 k  . En effet, d’après la proposition 3.80, le gradient de ˜f pour le produit scalaire h·, ·i s’écrit ∇ ˜f(xk) = R −1 k (xk − xk+1) = gk+1. Dès lors Rkgk+1 est le gradient de ˜f en xk+1 pour le produit scalaire h·, ·iR −1 k . Notons que les itérés générés font aussi décroître ˜f de façon monotone. En effet, (7.6) se récrit f(xk+1) 6 ˜f(xk) 6 f(xk), si bien que l’on a ˜f(xk+1) 6 f(xk+1) 6 ˜f(xk). 

Convergence 

Les propositions 7.3 et 7.4 ci-desous explorent quelques propriétés de convergence de l’algorithme proximal, dans des situations de plus en plus restrictives. Un des rôles de l’opérateur Rk dans l’itération de l’algorithme proximal peut se comprendre en examinant l’influence de son ordre de grandeur dans le problème (7.3) dont xk+1 est la solution. Si Rk est très petit, la pénalité introduite par le terme quadratique est très grande, si bien que le déplacement xk+1 − xk peut devenir très petit au point d’empêcher le progrès vers une solution (de ce point de vue, l’opérateur Rk = +∞I conviendrait parfaitement, puisqu’il permettrait de résoudre le problème de minimisation en une seule itération). Comme nous le verrons dans la démonstration de la proposition 7.3 ci-dessous, la condition suivant est suffisante. L’algorithme proximal à métrique variable Rk est difficile à analyser du fait de la modification de Rk à chaque itération, qui empêche d’utiliser les relations de monotonie issues de la formule (3.67), permettant de comparer deux itérations successives ou les itérés de l’itération courante à une solution du problème (un argument classique du cas où Rk = rkI). Le résultat de convergence de la proposition 7.3 repose alors sur la monotonie suivante, observée au point 2 de la page 328 : l’algorithme proximal fait décroître la fonction f à chaque itération. On note ˜f(xk) la valeur optimale dans (7.3), qui est la valeur de la régularisée de Moreau-Yosida en xk. Comme xk minimise f si, et seulement si, ˜f(xk) = f(xk), il est naturel de s’intéresser à l’écart entre ces deux valeurs, que l’on note