Les fonctions convexes

Introduction

De nombreux problèmes rencontrés en traitement d’images peuvent être abordés en introduisant une fonctionnelle d’énergie qui traduit le modèle considéré, en mesurant l’écart de toute fonction donnée à ce modèle. Si le modèle est suffisamment réaliste, la solution recherchée est logiquement celle qui en est le plus proche, c’est-à-dire celle qui minimise la fonctionnelle associée. Les fonctionnelles sont généralement composées de plusieurs termes séparés, chacun correspondant à une composante du modèle considéré. Ces termes peuvent être différentiables ou non, mais sont généralement convexes 1 . On se concentre dans ce chapitre sur le cas des fonctionnelles convexes, car il offre un cadre de travail naturel pour la minimisation. La convexité assure en effet l’existence d’une solution (donnée par le minimum global), mais surtout la non-existence de minima locaux. Elle permet donc d’envisager des stratégies basiques de descente pour rechercher 1. Ce n’est pas toujours le cas, cf. chapitre 2 11 Optimisation convexe et m´ de descente ethodes un minimum : elles consistent à trouver la direction de descente de l’énergie, qui est donnée par le gradient lorsque la fonctionnelle est différentiable. On verra qu’il est possible d’étendre ce genre de méthodes dans le cas non différentiable. La régularité (au sens large) des fonctionnelles joue un role prépondérant dans le choix et la conception des algorithmes de minimisation. La différentiabilité permet par exemple des calculs explicites dans les schémas de descente de gradient. Néanmoins, la différentiabilité n’est pas toujours acquise. Si la fonctionnelle n’est que partiellement différentiable, on montre qu’il est avantageux d’exploiter la régularité partielle de la fonctionnelle, ce qui conduit à des méthodes dites par éclatement. Dans le cas plus général, on introduit un opérateur dit proximal, qui est à l’origine d’une classe d’algorithmes dit proximaux. Ces derniers comprennent en particulier les méthodes classiques de gradient implicite, gradient explicite ou encore gradient projeté. Une autre sorte de régularité fournit également des résultats intéressants : il s’agit de la forte convexité. Cette propriété permet en outre de proposer des algorithmes accélérés, comme on le verra dans le chapitre 5. Enfin, un dernier aspect important en optimisation convexe reste la complexité des calculs. Pour qu’un algorithme soit utilisable sur des données réelles, il est nécessaire d’en assurer la convergence dans un temps raisonnable. On verra dans le chapitre 6 qu’une stratégie d’éclatement peut en réduire la complexité, en permettant notamment les calculs parallèles. Néanmoins, ce genre d’approches implique des résolutions approchées. L’objectif de ce chapitre est de donc de rappeler et d’établir certains résultats classiques en optimisation convexe continue, en vue de les appliquer dans les deux prochains chapitres. Nous commencerons par des rappels sur le cadre de la convexité (section 1.1). On verra ensuite le cas plus connu des fonctions différentiables, puis on introduira la notion de sous-différentiabilité. Cette notion est au coeur de la théorie des opérateurs proximaux (section 1.3) qui offre une classe très large d’algorithmes, appelés algorithmes proximaux, qui généralisent les méthodes de gradient (section 1.4). Enfin, on présentera des stratégies classiques qui permettent d’exploiter les propriétés de régularité d’une seule partie de la fonctionnelle (méthodes d’éclatement).

Convexité

Dans cette section, on fait quelques rappels sur les fonctions convexes, en considérant le cas général des fonctions à valeurs dans R∪ {±∞}. Ce choix nous permettra en particulier de considérer des problèmes de minimisation sous contraintes, mais sous une forme non contrainte. On rappellera ensuite les résultats d’existence de minimum, puis les conditions d’optimalité du premier ordre, d’abord dans le cas familier des fonctions différentiables, puis dans le cas plus général des fonctions sous-différentiables. Enfin, on introduira les fonctions fortement convexes, pour lesquelles on verra plus tard qu’il est possible de proposer des algorithmes accélérés.

Définitions

Commencons par quelques définitions classiques. Domaine, fonctions propres Soit X un espace hilbertien, de dual noté X ∗ . On va considérer dans ce chapitre des fonctions à valeurs dans la ligne réelle étendue X → R ∪ {±∞}. On appellera alors domaine de la fonction F, noté dom(F) l’ensemble des points x ∈ X tels que f(x) < +∞. 12 Une fonction F : E → R ∪ {±∞} est dite propre si elle ne prend pas la valeur −∞ et si elle n’est pas identiquement égale à +∞. Autrement dit, le domaine d’une fonction propre n’est pas vide. Inégalité de Jensen Un ensemble C ⊂ X est dit convexe si, pour tous élements x1 et x2 de C, le segment [ x1 ; x2 ] défini par {λ x1 + (1 − λ) x2 | λ ∈ [ 0 ; 1 ]} est contenu dans C. Une fonction F : E → R∪{+∞} est dite convexe si son épigraphe (c’est-à-dire l’ensemble des points situés au-dessus de son graphe) est un ensemble convexe. Elle est dite concave si −F est convexe. On montre que F est convexe si et seulement si elle vérifie l’inégalité de Jensen, qui pour tout couple (x1,x2) ∈ (dom(F))2 s’écrit ∀ λ ∈ ] 0 ; 1 [ , F λ x1 + (1 − λ) x2 ≤ λ F(x1) + (1 − λ) F(x2). Si cette inégalité est stricte pour tout x1 6= x2, alors F est dite strictement convexe.

Existence d’un minimiseur

Un des intérêts de l’optimisation convexe repose sur le fait qu’il n’existe pas de minimum local dans lequel les algorithmes de recherche de minimum par descente pourraient être piégés, comme l’atteste le résultat suivant : Proposition 1 Soit F une fonction convexe sur X. Si F admet un minimum local en x ∗ , alors il admet un minimum global en x ∗ . Un autre intérêt des fonctions convexes est l’existence de minimiseurs dans des cas simples à caractériser. Voici dans ce qui suit quelques résultats connus d’existence (et/ou d’unicité) de minimiseurs. Pour plus de détails, le lecteur pourra se reporter par exemple à [10]. Cas général On s’intéresse tout d’abord aux fonctions convexes (non strictement convexes). Commen¸cons par le cas des fonctions continues sur un compact, pour lesquelles l’existence d’un minimiseur est assuré : Proposition 2 Soit F une fonction convexe sur un compact K ⊂ X non vide. On suppose que F est continue sur K. Alors F admet au moins un minimum dans K. On enchaˆıne ensuite avec le cas non borné ; ce cas nécessite de considérer des fonctions dites coercives, c’est-à-dire telles que F(x) → +∞ si kxk → +∞. On peut alors montrer que, dans ce cas, l’existence d’un minimiseur est également assurée : Proposition 3 Soit F une fonction convexe sur X. On suppose que F est continue et coercive sur X. Alors F admet au moins un minimum dans X. Ce résultat se généralise à la minimisation sur un fermé quelconque non vide. 13 Cas de la stricte convexité Lorsqu’on ajoute une hypothèse de stricte convexité, les résultats qui précèdent incluent un résultat d’unicité. En effet, on peut montrer que Proposition 4 Soit F une fonction strictement convexe sur X. Alors F admet au plus un minimum sur X. Cette proposition nous permet donc d’énoncer un résultat important sur la minimisation d’une fonction strictement convexe, lorsque celle-ci est coercive : Théorème 1 Soit F une fonction strictement convexe et coercive sur X. Soit A un fermé non vide. On suppose que F est continue sur A. Alors F admet exactement un minimum dans A. Dans tout ce qui suit, on supposera toujours (sans le préciser) l’existence d’au moins un minimiseur.

Conditions d’optimalité

On présente dans ce paragraphe des résultats utiles permettant de caractériser, lorsqu’ils existent, les minima des fonctions considérées. On se focalise plus particulièrement sur les conditions dites du premier ordre, qui concernent les fonctions différentiables ou sous-différentiables, et qui donnent un critère sur le gradient ou le sous-gradient. Cas différentiable Commen¸cons par traiter le cas plus familier des fonctions différentiables. Les conditions nécessaires d’optimalité sont connus sous le nom d’équation ou d’inégalité d’Euler. Théorème 2 (Equation d’Euler) ´ Soit F une fonction convexe sur X. On suppose que F est différentiable sur X. Alors F admet un minimum en x ∗ si et seulement si x ∗ vérifie l’équation d’Euler ∇F(x ∗ ) = 0. Ce résultat est également valable sur tout ouvert convexe Ω ⊂ X. Il n’est pas valable sur des ensembles fermés (o`u le minimum, s’il existe, peut être atteint sur le bord). C’est l’objet du résultat suivant, généralisable à tout convexe Ω : Proposition 5 (Inégalité d’Euler) Soit F une fonction convexe sur X. On suppose que F est différentiable sur X. Alors F admet un minimum en x ∗ si et seulement si x ∗ vérifie l’inégalité d’Euler ∀ x ∈ X, hx − x ∗ ,∇F(x ∗ )i ≥ 0. 14 Sous-différentiabilité On quitte maintenant le cadre des fonctions différentiables. Commen¸cons par introduire la notion de sous-différentiabilité, qui généralise celle de la différentiabilité dans le cas des fonctions convexes. Soit x0 ∈ X tel que x0 ∈ dom(F) avec F une fonction convexe. On définit le sous-différentiel de F en x0, noté ∂F(x0), comme étant l’ensemble des points p ∈ X ∗ vérifiant ∀ x ∈ X, hx − x0,pi + F(x0) ≤ F(x) appelés, quand ils existent, sous-gradients de F en x0. On dit alors que F est sousdifférentiable en x0 si son sous-différentiel en x0 est non vide. Par convention, on définit le sous-différentiel de F en x0 comme étant l’ensemble vide si F(x0) = +∞. On peut montrer par ailleurs que le sous-différentiel en x0 d’une fonction convexe F différentiable en x0 est donné par le singleton {∇F(x0)}. Réciproquement, on établit que, si le sousdifférentiel de F en x0 est réduit à un vecteur p, alors F est différentiable en x0, de gradient p. Calcul de sous-différentiel Etablissons ici quelques règles de calcul de sous-différentiel ´ qui nous seront utiles par la suite. Commen¸cons par remarquer que, pour tout α > 0, on a ∀ x0 ∈ dom(F), ∂(αF)(x0) = α ∂F(x0). En effet, on a par définition du sous-différentiel x ∈ ∂(αF)(x0) ⇐⇒ ∀ x ∈ X, hx − x0,pi + α F(x0) ≤ α F(x) ⇐⇒ ∀ p ∈ X, x − x0, x α + F(x0) ≤ F(x) x ∈ ∂(αF)(x0) ⇐⇒ x α ∈ ∂F(x0). Supposons à présent que f est une fonction convexe différentiable et F convexe. Posons G = F +f. Calculons ∂G(x0) pour tout x0 ∈ dom(F)∩dom(f). Si p ∈ ∂F(x0), alors ∀ x ∈ X, hx − x0,pi + F(x0) ≤ F(x). On a par ailleurs, puisque ∂f(x0) = {∇f(x0)}, ∀ x ∈ X, hx − x0,∇f(x0)i + f(x0) ≤ f(x). En additionnant les deux, on montre que p + ∇f(x0) ∈ ∂G(x0). Ainsi, on prouve que ∂F(x0)+∇f(x0) ⊂ ∂G(x0) 2 . Supposons maintenant que x ∈ ∂G(x0) et démontrons l’inclusion inverse. On a par définition ∀ x ∈ X,∀ λ ∈ ] 0 ; 1 [ , h[λx + (1 − λ)x0] − x0,pi + G(x0) ≤ G λx + (1 − λ)x0 soit λhx − x0,pi + F(x0) + f(x0) ≤ λ F(x) + (1 − λ) F(x0) + f x0 + λ(x − x0) . En simplifiant et en utilisant la formule de Taylor-Young au premier ordre pour f, on obtient que λhx − x0,pi + f(x0) ≤ λ F(x) − λ F(x0) + f(x0) + λhx − x0,∇f(x0)i +λ kx − x0k ε λ(x − x0) .