VII.3. La convexification d’une fonction
– Soient des fonctions f 1 , . . . , f k ∈ Γ 0 (R n ) et x un point intérieur à tous les
dom f i , i = 1, . . . , k (par exemple x est quelconque si les f i sont partout finies
sur R n ). Alors :
∂( max
i=1,...,k
f i )(x) = conv
⎧
⎨
⎩
i∈I(x)
∂f i (x)
⎫
⎬
⎭
,
(7.8)
où I(x) := {i | f i (x) = f (x)} . En d’autres termes, un sous-gradient de
max i=1,...,k f i en x est une combinaison convexe de sous-gradients de f i en x, où
l’on ne retient que les indices i pour lesquels f i (x) = f (x) (« là où ça touche »). La
règle de calcul (7.8), sans équivalent dans le monde des fonctions différentiables,
est sans doute la plus importante du royaume des fonctions convexes.
VII.3. La convexification d’une fonction
Étant donnée une fonction f (toujours vérifiant (7.1)), on se pose la question de construire l’enveloppe convexe de f , c’est-à-dire la plus grande fonction
convexe minorant f sur R n ; laquelle fonction est notée conv f (ou co f plus traditionnellement). La construction analytique de conv f est comme suit :
(conv f )(x) = inf
n+1
i=1
α i f (x i ) | x =
n+1
i=1
α i x i , α i 0 pour tout i
et
n+1
i=1
α i = 1
;
parmi toutes les décompositions possibles de x comme combinaisons convexes
de points x i , on prend l’infimum des combinaisons convexes correspondantes des
valeurs f (x i ) de la fonction. (Mais attention ! l’épigraphe de conv f peut être
légèrement plus gros que l’enveloppe convexe de epi f.)
Plus utile que conv f est son enveloppe semi-continue inférieure, c’est-à-dire
la fonction obtenue en fermant l’épigraphe de conv f (ce qui revient in fine à
prendre l’enveloppe convexe fermée de epi f ) ; cette nouvelle fonction est notée
conv f (ou co f plus traditionnellement). Outre la construction « interne » de
conv f évoquée précédemment, il y a une construction « externe » qui s’avère
toute aussi parlante : La fonction conv f est le supremum de toutes les fonctions
affines minorant f sur R n .
275
– Soient des fonctions f 1 , . . . , f k ∈ Γ 0 (R n ) et x un point intérieur à tous les
dom f i , i = 1, . . . , k (par exemple x est quelconque si les f i sont partout finies
sur R n ). Alors :
∂( max
i=1,...,k
f i )(x) = conv
⎧
⎨
⎩
i∈I(x)
∂f i (x)
⎫
⎬
⎭
,
(7.8)
où I(x) := {i | f i (x) = f (x)} . En d’autres termes, un sous-gradient de
max i=1,...,k f i en x est une combinaison convexe de sous-gradients de f i en x, où
l’on ne retient que les indices i pour lesquels f i (x) = f (x) (« là où ça touche »). La
règle de calcul (7.8), sans équivalent dans le monde des fonctions différentiables,
est sans doute la plus importante du royaume des fonctions convexes.
VII.3. La convexification d’une fonction
Étant donnée une fonction f (toujours vérifiant (7.1)), on se pose la question de construire l’enveloppe convexe de f , c’est-à-dire la plus grande fonction
convexe minorant f sur R n ; laquelle fonction est notée conv f (ou co f plus traditionnellement). La construction analytique de conv f est comme suit :
(conv f )(x) = inf
n+1
i=1
α i f (x i ) | x =
n+1
i=1
α i x i , α i 0 pour tout i
et
n+1
i=1
α i = 1
;
parmi toutes les décompositions possibles de x comme combinaisons convexes
de points x i , on prend l’infimum des combinaisons convexes correspondantes des
valeurs f (x i ) de la fonction. (Mais attention ! l’épigraphe de conv f peut être
légèrement plus gros que l’enveloppe convexe de epi f.)
Plus utile que conv f est son enveloppe semi-continue inférieure, c’est-à-dire
la fonction obtenue en fermant l’épigraphe de conv f (ce qui revient in fine à
prendre l’enveloppe convexe fermée de epi f ) ; cette nouvelle fonction est notée
conv f (ou co f plus traditionnellement). Outre la construction « interne » de
conv f évoquée précédemment, il y a une construction « externe » qui s’avère
toute aussi parlante : La fonction conv f est le supremum de toutes les fonctions
affines minorant f sur R n .
275