m

3 Fonctions convexes

No
The fundamental idea to be understood is that the convex
functions on Rn can be identified with certain convex subsets of
Rn+1 (their epigraphs), while the convex sets in Rn can be
identified with certain convex functions on Rn (their
indicators). These identifications make it easy to pass back and
forth between a geometric approach and an analytic approach.
R.T. Rockafellar (1970). Convex Analysis [535].

Moreau and I independently in those days at first, but soon in

close exchanges with each other, made the crucial changes in
nom
outlook which, I believe, created convex analysis out of
convexity. For instance, he and I passed from the basic objects
in Fenchel’s work, which were pairs consisting of a convex set
and a finite convex function on that set, to extended-real-valued
functions implicitly having effective domains, for which we
moreover introduced set-valued subgradient mappings.
R.T. Rockafellar sur le site Wikimization.

3.1 Définition
Soit E un espace vectoriel sur R. On note R := R ∪ {−∞, +∞} la droite achevée.
En analyse convexe et en optimisation, il est parfois intéressant de pouvoir considérer
des fonctions pouvant prendre des valeurs infinies. En analyse convexe, plutôt que
Pre

de définir une fonction convexe comme un couple formé d’un ensemble convexe C et
d’une fonction f définie sur C ayant une propriété bien particulière (une approche
que l’on rencontre encore parfois), il est préférable de dire que cette fonction prend
des valeurs infinies en dehors de C. On évite ainsi de devoir décrire C avant de dé-
finir f , en particulier lorsque f est construite par une des opérations non triviales
que nous verrons dans lesquels il est compliqué de déterminer l’ensemble C. C’est ce
à quoi fait allusion la seconde épigraphe de ce chapitre. De même, il peut être utile
de représenter un problème d’optimisation avec contrainte min{f (x) : x ∈ X}, où X
est une partie de E, par le problème sans contrainte équivalent min{f˜(x) : x ∈ E},
où f˜ prend les mêmes valeurs que f sur X et vaut +∞ sur le complémentaire de X.

69
 m
70 3. Fonctions convexes

Cette astuce conduit à un cadre théorique permettant de traiter en même temps les
problèmes avec et sans contraintes ; nous l’utiliserons souvent.
On rappelle que le domaine effectif (ou simplement domaine) d’une fonction f :
E → R est l’ensemble des points où elle ne prend pas la valeur +∞. On le note

dom f := {x ∈ E : f (x) < +∞}.

No
On accepte que f prenne la valeur −∞ sur son domaine pour que celui-ci soit convexe
lorsque f est convexe (proposition 3.2, ci-dessous), mais nous considérerons le plus
souvent des fonctions ne prenant pas la valeur −∞. On rappelle que l’épigraphe de f
est la partie de l’espace produit E × R qui est au-dessus de son graphe :

epi f := {(x, α) ∈ E × R : f (x) 6 α}.

Quant à l’épigraphe stricte, il est obtenu en prenant l’inégalité stricte ci-dessus. On

le note
epis f := {(x, α) ∈ E × R : f (x) < α}. (3.1)
Comme le montre le point 3 de l’exercice 3.1, cet épigraphe stricte est généralement
différent de l’intérieur relatif de l’épigraphe.

Définitions 3.1 On dit qu’une fonction f : E → R est convexe si son épigraphe (ou
nom
son épigraphe stricte) est convexe dans E × R. On dit que f : E → R est concave si
−f est convexe. ✷
Le fait qu’il soit équivalent de prendre l’épigraphe ou l’épigraphe stricte dans cette
définition est le sujet du point 2 de l’exercice 3.1.

Proposition 3.2 (charactérisation de la convexité d’une fonction) Le do-

maine d’une fonction convexe est convexe. Une fonction f : E → R est convexe
si, et seulement si, pour tout x, y ∈ dom f et tout t ∈ ]0, 1[, on a
 
f (1−t)x + ty 6 (1−t)f (x) + tf (y). (3.2)

Avant de donner la démonstration de la proposition, observons que le membre de

droite de (3.2) n’est pas ambigu, car les coefficients (1 − t) et t sont strictement
positifs. Donc les produits ne sont pas indéterminés (comme le produit de −∞ par
Pre

zéro), même si f (x) ou f (y) valent −∞. Par ailleurs, f (x) ou f (y) ne peuvent pas
prendre la valeur +∞ (x et y ∈ dom f ) et donc on n’a jamais l’indétermination ∞−∞.
Démonstration. Supposons que f soit convexe. Soient x, y ∈ dom f , t ∈ ]0, 1[ et
α, β ∈ R tels que α > f (x) et β > f (y) (de tels α et β existent car x et y ∈
dom f ). Comme (x, α) et (y, β) sont dans l’épigraphe de f , qui est convexe, il en est
de même de (1−t)(x, α) + t(y, β) = ((1−t)x + ty, (1−t)α + tβ), ce qui se traduit par
f ((1−t)x + ty) 6 (1−t)α + tβ. Comme α > f (x) et β > f (y) sont arbitraires, on
obtient (3.2). En particulier, ((1−t)x + ty) ∈ dom f ; donc dom f est convexe.
Supposons à présent que f : E → R ∪ {+∞} vérifie (3.2) pour tout x, y ∈ dom f
et tout t ∈ ]0, 1[. Soient (x, α) et (y, β) ∈ epi f ; donc x et y ∈ dom f . D’après (3.2),
 m
3.1. Définition 71

on a pour t ∈ ]0, 1[ : f ((1−t)x + ty) 6 (1−t)α + tβ. Donc (1−t)(x, α) + t(y, β) =

((1−t)x + ty, (1−t)α + tβ) ∈ epi f , si bien que epi f est convexe. ✷

La signification géométrique de l’inégalité de convexité (3.2) est claire (voir la

figure 3.1) : pour être convexe, il faut que, sur tout segment [x, y] ⊆ dom f , f reste
en-dessous de la fonction affine valant f (x) en x et f (y) en y.

No
+∞
epi f epi f

y
x
y x
convexe non convexe

Fig. 3.1. Définition d’une fonction convexe

Définition 3.3 On dit que f : E → R ∪ {+∞} est strictement convexe si pour tout
nom
x, y ∈ dom f avec x 6= y et pour tout t ∈ ]0, 1[ on a
 
f (1−t)x + ty < (1−t)f (x) + tf (y).

Sur un espace normé E, on dit que f : E → R ∪ {+∞} est fortement convexe de

module α > 0, si pour tout x, y ∈ dom f et tout t ∈ [0, 1], on a
  α
f (1−t)x + ty 6 (1−t)f (x) + tf (y) − t(1−t)kx − yk2 .
2
Si la norme dérive d’un produit scalaire, cette propriété qui revient à affirmer que
f − (α/2)k · k2 est convexe. ✷
Une fonction fortement convexe est donc strictement convexe avec une inégalité de
convexité renforcée par un terme quadratique lui donnant une « courbure » au moins
égale à α.
Une fonction identiquement égale à +∞ est convexe (son épigraphe est vide), mais
présente peu d’intérêt. Par ailleurs, une fonction convexe prenant la valeur −∞ est
très particulière (exercice 3.3). Une fonction f : E → R ne prenant pas la valeur −∞
Pre

et n’étant pas identiquement égale à +∞ est dite propre, sinon elle est dite impropre.
On note
Conv(E)
l’ensemble des fonctions de E → R qui sont convexes et propres. Ce n’est pas un
espace vectoriel (la différence de deux fonctions convexes n’est généralement pas con-
vexe !), ni même un cône convexe (à moins que l’on ne suppose les fonctions à valeurs
réelles, car deux fonctions de Conv(E) peuvent avoir des domaines qui ne s’intersectent
pas, auquel cas leur somme est impropre). Si f ∈ Conv(E), son épigraphe n’est pas
vide ; donc l’intérieur relatif de celui-ci non plus (proposition 2.15). Le point 3 de
l’exercice 3.1 en donne une expression explicite :
 m
72 3. Fonctions convexes

(epi f )−
◦
= {(x, α) : x ∈ (dom f )−
◦
, f (x) < α}. (3.3)

Il s’agit donc d’une partie de l’épigraphe stricte de f .

On rappelle qu’une une fonction f : E → R est dite fermée si son épigraphe est
fermé (il revient au même de dire que f est s.c.i.). La figure 3.2 représente à gauche

No
epi f epi f f (x)
f (x)

x x

f ∈ Conv(R) f 6∈ Conv(R)

Fig. 3.2. Fonctions convexes fermée (à gauche) et non fermée (à droite)

une fonction convexe fermée et à droite une fonction convexe non fermée, ne différant
de la première que par sa valeur en x. On note
nom
Conv(E)

la partie de Conv(E) formée des fonctions fermées.

Considérons le problème d’optimisation suivant :

min f (x)
(PX )
x ∈ X,

dans lequel on cherche à minimiser une fonction f définie sur un espace topologique X
à valeurs dans R∪{+∞} (voir la section 1.1). Le résultat suivant donne des conditions
simples assurant l’unicité de la solution de (PX ).

Théorème 3.4 (unicité de solution) Si X est une partie convexe d’un espace
vectoriel E et si f est strictement convexe sur X, alors (PX ) a au plus une
solution.

Démonstration. On raisonne par l’absurde. Soient x1 ∈ X et x2 ∈ X deux solutions

Pre

distinctes, vérifiant donc

f (x1 ) = f (x2 ) = min f.
Comme X est convexe et f est strictement convexe sur X, on a
 
x1 + x2 1 1
f < f (x1 ) + f (x2 ) = min f.
2 2 2

On aurait donc un point x = x1 +x 2

2
appartenant à X (car cet ensemble est convexe)
et tel que f (x) < f (x1 ). Ceci contredirait l’optimalité de x1 et x2 . ✷
 m
3.2. Exemples 73

3.2 Exemples
3.2.1 Indicatrice

On appelle fonction indicatrice d’une partie P ⊆ E, ou simplement indicatrice

de P , la fonction IP : E → R définie par

No
(
0 si x ∈ P
IP (x) =
+∞ sinon.

La démonstration du résultat suivant est proposée au point 1 de l’exercice 3.27.

Proposition 3.5 (fonction indicatrice) Si P est une partie non vide de E,

alors IP ∈ Conv(E) (resp. IP ∈ Conv(E)) si, et seulement si, P est convexe
(resp. convexe fermé).

3.2.2 Fonction affine et minorante affine

nom
Une fonction a : E → R est dite affine si elle vérifie pour tout x, y ∈ E et tout
t ∈ R:
a((1−t)x + ty) = (1−t)a(x) + ta(y).
Ceci revient à dire que la fonction x ∈ E 7→ a(x)−a(0) est linéaire. Il s’agit évidemment
d’une fonction convexe, puisque (3.2) est vérifiée avec égalité sans condition sur t ∈ R.
En dimension finie, il n’y a pas de restriction à supposer que E est muni d’un
produit scalaire h·, ·i. Une fonction affine est alors donnée par un élément x∗ ∈ E et
une scalaire α ∈ R et s’écrit

a : x ∈ E 7→ a(x) = hx∗ , xi − α.

L’élément x∗ , qui représente l’application linéaire x 7→ a(x) − a(0) dans E, est appelé
la pente de a. On voit que, si l’on munit l’espace produit E × R du produit scalaire
h(x, α), (y, β)i = hx, yi + αβ, l’épigraphe de a s’écrit

epi a = {(x, t) ∈ E × R : hx∗ , xi − α 6 t}

= {(x, t) ∈ E × R : h(x∗ , −1), (x, t)i 6 α},
Pre

qui n’est autre que le demi-espace fermé H − ((x∗ , −1), α) de E × R (notation (2.33)).
On appelle minorante affine d’une fonction f : E → R ∪ {+∞}, une fonction
affine a qui minore f sur E : pour tout x ∈ E, f (x) > a(x). L’épigraphe d’une mi-
norante affine de f est donc un demi-espace fermé de E × R qui contient l’épigraphe
de f . Forcément, si f a une minorante affine, elle ne peut pas prendre la valeur −∞.
On dit qu’une minorante affine a de f est exacte en x0 si a(x0 ) = f (x0 ). Dans ce cas,
elle s’écrit
a(x) = f (x0 ) + hx∗ , x − x0 i.
Une fonction convexe et propre a une minorante affine et celle-ci peut être choisie
exacte en un point donné de (dom f )−
◦
, c’est ce qu’affirme la proposition suivante.
 m
74 3. Fonctions convexes

Proposition 3.6 (existence de minorante affine) Si f ∈ Conv(E) et x ∈

(dom f )−
◦
, alors il existe x∗ dans le sous-espace vectoriel parallèle à aff(dom f )
tel que
∀ y ∈ E : f (y) > f (x) + hx∗ , y − xi.

No
Démonstration. Observons d’abord que (x, f (x)) est sur la frontière relative de
l’ensemble convexe fermé C := adh(epi f ). En effet, (x, f (x)) est sur la fron-
tière relative de l’épigraphe de f (un convexe non nécessairement fermé), puisque
(x, f (x)) ∈ epi f et que (x, α) ∈ (aff(epi f )) \ (epi f ) pour tout α < f (x). Donc
/ (epi f )−
(x, f (x)) ∈ ◦
. Mais ce dernier ensemble est aussi C − ◦
(point 3 de la proposi-
tion 2.15). Comme (x, f (x)) appartient à C mais pas à C − ◦
, il est sur la frontière
relative de C.
La proposition 2.28 nous assure alors qu’il existe une
normale non nulle (x∗0 , ν) à C en (x, f (x)) qui est dans
l’espace vectoriel parallèle à aff(epi f ) = aff(dom f ) × R
epi f
(point 1 de l’exercice 3.1) qui est E0 ×R, où E0 est l’espace
vectoriel parallèle à aff(dom f ). Pour tout (y, α) ∈ epi f , (x, f (x))
nom
on a donc h(y, α) − (x, f (x)), (x∗0 , ν)i 6 0 ou, si l’on munit (x∗0 , ν)
E × R du produit scalaire naturel de l’espace produit :
minorante affine
∀ (y, α) ∈ epi f : hx∗0 , y − xi + ν(α − f (x)) 6 0. de f exacte en x

Exploitons cette inégalité :

on peut prendre α ↑ ∞ dans cette inégalité, car (α, f (x)) reste alors dans
l’épigraphe de f , ce qui montre que ν 6 0 ;
on ne peut avoir ν = 0 (normale horizontale), car y = x + tx∗0 ∈ dom f pour t > 0
petit (car x ∈ (dom f )−◦
et x∗0 ∈ E0 ), si bien que l’inégalité ci-dessus impliquerait
tkx0 k 6 0 et donc x0 serait aussi nul, contredisant le fait que (x∗0 , ν) 6= 0.
∗ 2 ∗

Alors, en définissant x∗ = −x∗0 /ν et en prenant α = f (y) dans l’inégalité exposée

ci-dessus, on obtient l’inégalité de l’énoncé. ✷

Comme souvent, on a obtenu des résultats confortables en des points qui ne sont
pas sur la frontière relative des ensembles convexes considérés. Dans le cas présent, si x
est sur la frontière relative du domaine de f , le résultat de la proposition précédente
ne tient plus nécessairement. Ceci est illustré par la fonction d’une variable x ∈ R
Pre

suivante, qui a un graphe en demi-cercle :

 √
1 − 1 − x2 si x ∈ [−1, 1]
f (x) =
+∞ sinon.
1

Cette fonction convexe a évidemment une minorante affine (par exemple la fonction
nulle), mais n’a pas de minorante affine exacte en x = 1 (la tangente y est verticale
et celle-ci n’est pas le graphe d’une fonction affine ; ν = 0 dans la démonstration
précédente).
 m
3.2. Exemples 75

3.2.3 Fonction convexe polyédrique

On dit qu’une fonction f : E → R est (convexe) polyédrique si son épigraphe est

un polyèdre convexe. Une fonction polyédrique est donc nécessairement convexe et
fermée (elle peut ne pas être propre cependant).

No
(ξ1 , τ1 )
(y1 , β1 ) (y2 , β2 )
(x2 , α2 ) (x5 , α5 ) (ξ4 , τ4 )

(x1 , α1 ) (ξ2 , τ2 )
(x4 , α4 ) (ξ3 , τ3 )
(x3 , α3 )

Fig. 3.3. Représentation primale (à gauche) et duale (à droite) d’une fonction polyédrique

Selon la représentation choisie du polyèdre convexe de E × R qu’est l’épigraphe

d’un fonction polyédrique f (voir la section 2.4), on obtient une représentation primale
nom
ou duale de f . Dans la représentation primale (figure 3.3, à gauche), epi f s’écrit

epi f = co{(x1 , α1 ), . . . , (xp , αp )} + cone{(y1 , βq ), . . . , (yq , βq )},

où les xi et les yj sont donnés dans E et les αi et βj sont donnés dans R. Alors

 X X X X
f (x) = inf ti αi + s j βj : ti xi + sj yj = x,

16i6p 16j6q 16i6p 16j6q

X 
ti = 1, ti > 0, sj > 0 . (3.4)

16i6p

Dans la représentation duale (figure 3.3, à droite), epi f est vu comme une in-
tersection d’un nombre fini de demi-espaces de E × R, qui sont des ensembles de la
forme
{(x, α) ∈ E × R : hξi , xi + τi α 6 ti },
Pre

où ξi ∈ E, τi ∈ R et ti ∈ R. Puisque le polyèdre convexe ainsi obtenu doit être

un épigraphe de fonction, α peut y être pris aussi grand que l’on veut, si bien que
les τi 6 0. Si τi < 0, le demi-espace est l’épigraphe de la fonction affine ai : x 7→
−hξi /τi , xi + ti /τi . Si τi = 0, le demi-espace est vertical et la condition hξi , xi 6 ti
impose à x d’appartenir à un demi-espace de E : le domaine de f est donc un polyèdre
convexe P de E. De ce point de vue, f s’écrit

f = max ai + IP . (3.5)
16i6k

Cette représentation permet de voir que la somme de deux fonctions convexes polyé-
driques est une fonction convexe polyédrique (exercice 3.15).
 m
76 3. Fonctions convexes

3.2.4 Fonction sous-linéaire

Définition 3.7 On dit qu’une fonction σ : E → R ∪ {+∞} est sous-linéaire si elle est
convexe et positivement homogène de degré 1 (c’est-à-dire : pour tout t > 0 et tout
x ∈ E, on a σ(tx) = tσ(x)). ✷

No
Un exemple de fonction sous-linéaire est l’application d 7→ f ′ (x; d), dérivée direc-
tionnelle d’une fonction convexe en un point x. Nous verrons cela plus loin.
L’appellation « sous-linéaire » vient de la propriété (iii) de la proposition ci-
dessous. Elle est semblable à la condition de convexité (3.2), mais doit avoir lieu
ici, même si t1 + t2 6= 1.

Proposition 3.8 (sous-linéarité) Soit σ : E → R ∪ {+∞} une fonction avec

domaine non vide. Les propriétés suivantes sont équivalentes :
(i) σ est sous-linéaire ;
(ii) epi σ est un cône convexe de E × R ;
(iii) ∀ (x1 , x2 ) ∈ (dom σ)2 et ∀ (t1 , t2 ) ∈ R2+ , on a σ(t1 x1 + t2 x2 ) 6 t1 σ(x1 ) +
t2 σ(x2 ).
nom
Démonstration. [(i) ⇐⇒ (ii)] Par définition même, la convexité de σ est équivalente
à la convexité de son épigraphe. Si σ est sous-linéaire et si (x, r) ∈ epi σ, on a σ(x) 6 r,
puis σ(tx) = tσ(x) 6 tr pour t > 0, donc (tx, tr) ∈ epi σ, qui montre que epi σ est un
cône. Inversement, si epi σ est un cône, (tx, tσ(x)) ∈ epi σ pour tout t > 0, c’est-à-dire
σ(tx) 6 tσ(x) pour tout t > 0, donc aussi σ(x) 6 1t σ(tx) ; on en déduit σ(tx) = tσ(x)
et l’homogénéité positive de σ.
[(i) ⇐⇒ (iii)] Supposons que σ soit sous-linéaire. Soient (x1 , x2 ) ∈ (dom σ)2 et
(t1 , t2 ) ∈ R2+ . Alors pour t = t1 + t2 6= 0, on a grâce à l’homogénéité positive et la
convexité de σ :

σ(t1 x1 + t2 x2 ) = tσ( tt1 x1 + t2

t x2 ) 6 t1 σ(x1 ) + t2 σ(x2 ).

Inversement la condition (iii) implique la convexité de σ (proposition 3.2) ainsi que,

pour tout t > 0, σ(tx) = σ( 2t x + 2t x) = tσ(x). ✷

En prenant x1 = −x2 = x et t1 = t2 = 1 dans le point (iii) de la proposition

précédente, on voit qu’une fonction sous-linéaire σ vérifie
Pre

∀ x ∈ dom σ : σ(x) + σ(−x) > 0.

Pour que σ devienne linéaire sur un sous-espace vectoriel, il suffit que l’on ait égalité
dans cette relation pour des vecteurs engendrant ce sous-espace.

Proposition 3.9 (sous-linéarité et linéarité) Soit σ : E → R ∪ {+∞} une

fonction sous-linéaire telle que, pour des points x1 , . . . , xm ∈ dom σ, on ait
 m
3.2. Exemples 77

σ(xi ) + σ(−xi ) = 0. (3.6)

Alors σ est linéaire sur le sous-espace vectoriel engendré par x1 , . . . , xm .

No
Pm
Démonstration. Par (3.6), les −xi ∈ dom σ. Par ailleurs si x = i=1 ti xi avec des
ti ∈ R, on a
m
X  
σ(x) = σ |ti | (sgn ti ) xi
i=1
m
X  
6 |ti | σ (sgn ti ) xi [sous-linéarité]
i=1
Xm
= ti σ(xi ) [(3.6)].
i=1

Donc aussi m m
X X
−σ(x) 6 σ(−x) 6 ti σ(−xi ) = − ti σ(xi ).
nom
i=1 i=1
Pm
On en déduit σ(x) = i=1 ti σ(xi ), c’est-à-dire la linéarité de σ. ✷

3.2.5 Fonction d’appui

Soit E un espace euclidien (produit scalaire h·, ·i). La fonction d’appui d’une partie
non vide P ⊆ E est la fonction σP : E → R ∪ {+∞} définie par

σP (d) := sup hd, xi.

x∈P

Elle donne donc la valeur optimale du problème de maximisation de la fonction linéaire

x ∈ E 7→ hd, xi sur P .

Proposition 3.10 Soient P , P1 et P2 des parties non vides de E. Alors

1) σP est sous-linéaire et fermée,
2) σP1 6 σP2 ⇐⇒ coP1 ⊆ coP2 ,
Pre

3) σP1 = σP2 ⇐⇒ coP1 = coP2 ,

4) σP = σco P = σP = σcoP ,
5) dom σP ⊆ ((coP )∞ )− , dom σP = (P ∞ )− si P est un polyèdre convexe.

Démonstration. 1) Il s’agit de l’enveloppe supérieure de fonctions linéaires ; celles-ci

étant convexes et fermées, la fonction d’appui est convexe et fermée (proposition 3.33).
L’homogénéité positive est immédiate.
2) ⇒ Il suffit de montrer que P1 ⊆ coP2 . Si ce n’est pas le cas, il existe un point
x̂ ∈ P1 \ coP2 . On sépare strictement le compact {x̂} du fermé coP2 : il existe d ∈ E
et α ∈ R tels que
 m
78 3. Fonctions convexes

∀ x ∈ coP2 , hd, xi 6 α < hd, x̂i.

On en déduirait que σP2 (d) < σP1 (d), une contradiction.
⇐ Réciproquement, supposons qu’il existe d ∈ E tel que σP2 (d) 6 α < σP1 (d).
Alors P2 est contenu dans le demi-espace fermé H − (d, α) := {x ∈ E : hd, xi 6 α},
mais celui-ci ne contient pas un point de x̂ ∈ P1 . Alors coP2 ⊆ H − (d, α) et on aurait

No
P1 6⊆ coP2 .
3) C’est une conséquence immédiate du point 2.
4) C’est une conséquence du point 3 puisque coP = co(co P ) = coP = co(coP ).
5) On note C := coP . Si d ∈/ (C ∞ )− , il existe une direction p ∈ C ∞ telle que 2α :=
∞
hd, pi > 0. Le fait que p ∈ C implique à son tour qu’il existe des suites {xk } ⊆ C et
{tk } → ∞ telles que xk /tk → p (point 1 de la proposition 2.7). Dès lors, pour k assez
grand, on a hd, xk i > tk α, ce qui implique que σC (d) > supk hd, xk i = +∞. Comme
σC = σP (point 4), l’inclusion dom σP ⊆ (C ∞ )− est démontrée.
Si P est un polyèdre convexe, il peut s’écrire P = {x ∈ E : Ax 6 b} pour une
application linéaire A : E → Rm et b ∈ Rm . On sait qu’alors P ∞ = {p ∈ E : Ap 6 0}
(point 4 de l’exercice 2.18). Soit d ∈ (P ∞ )− . Par le lemme de Farkas (proposition 2.40),
on peut écrire d = A∗ v avec v > 0 dans Rm . Alors pour tout x ∈ P , on a hd, xi =
v T (Ax) 6 v T b (var v > 0 et Ax 6 b), ce qui montre que σP (d) 6 v T b < +∞,
c’est-à-dire que d ∈ dom σP . ✷
nom
On remarquera que l’on peut avoir dom σC 6= (C ∞ )− , si C est un convexe fermé
non vide, non polyédrique. C’est le cas si C = {x ∈ R2 : x2 > x21 }, puisqu’alors
C ∞ = R+ e2 , e1 ∈ (C ∞ )− , mais que σC (e1 ) > supk (e1 )T (k 2 , k 2 ) = supk k = ∞.

Proposition 3.11 (calcul de fonctions d’appui) 1) Pour i ∈ {1, . . . , m}, on

suppose donnés des parties non vides Pi de E et des scalaires αi > 0. Alors
Pm
σ(Pm α P ) = i=1 αi σPi .
i=1 i i

2) Soient F un espace euclidien, A : E → F une fonction linéaire, A∗ son adjointe

et P une partie non vide de E. Alors, pour tout h ∈ F :

σA(P ) (h) = σP (A∗ h).

Pre

Démonstration. 1) Soit d ∈ E. On a
Pm P 
m
σ(Pm αi Pi )
(d) = sup hd, i=1 αi xi i = sup i=1 αi hd, xi i .
i=1 xi ∈Pi xi ∈Pi

Ci-dessus, le supremum est pris sur chaque terme séparément, si bien que l’on peut
sortir la somme du sup, ce qui conduit au résultat.
2) On a σP (A∗ h) = sup{hA∗ h, xi : x ∈ P } = sup{hh, Axi : x ∈ P } = σA(P ) (h).
✷
 m
3.3. Régularité 79

3.3 Régularité

3.3.1 Continuité lipschitzienne

Les fonctions convexes sont régulières sur leur domaine ; plus précisément elles
sont lipschitziennes sur tout convexe compact contenu dans l’intérieur relatif de leur

No
domaine. C’est ce que nous allons montrer à la proposition 3.13 ci-dessous. Dès
lors, les accidents ne peuvent arriver que sur la frontière (relative) du domaine. Ce
sont ces accidents-frontière qui peuvent rendre la fonction non fermée ou non sous-
différentiable. Il faudra donc à l’avenir se concentrer sur le comportement de f sur la
frontière relative de son domaine.

Lemme 3.12 Si f ∈ Conv(E) est bornée (supérieurement et inférieurement)

sur un voisinage de E, alors f est localement lipschitzienne sur l’intérieur de ce
voisinage (tout point de ce voisinage est contenu dans un voisinage sur lequel f
est lipschitzienne).

Démonstration. Par hypothèse, il existe un voisinage V et une constante C > 0

tels que |f (x)| 6 C lorsque x ∈ V . Fixons x ∈ int(V ) et δ > 0 tels que B̄(x, δ) ⊆ V
nom
et montrons que f est lipschitzienne de module 4C δ
δ sur U := B̄(x, 2 ).
′ ′ ′
Soient y, y ∈ U , y 6= y , et posons ∆ := ky − y k ∈ ]0, δ]. Avec

δ ′
y ′′ := y ′ + (y − y) ∈ B̄(x, δ)
2∆
on a
2∆ ′′ δ
y′ = y + y.
2∆ + δ 2∆ + δ
Par convexité de f et sa bornitude sur B̄(x, δ), on obtient alors

2∆ δ 2∆ 4C
f (y ′ ) 6 f (y ′′ ) + f (y) = f (y) + (f (y ′′ ) − f (y)) 6 f (y) + ky − y ′ k.
2∆+δ 2∆+δ 2∆+δ δ
On obtient le résultat en inversant le rôle de y et y ′ dans l’inégalité ci-dessus. ✷

Les voisinages U sur lesquels f est lipschitzienne sont éventuellement plus petits
que le voisinage V sur lequel elle est bornée et la constante de Lipschitz sur U pourra
Pre

être d’autant plus grande que U entoure un point proche du bord de V . C’est le cas
par exemple pour la fonction convexe définie par

− log x si x > 0
+∞ si x 6 0.

Cette fonction n’est pas lipschitzienne sur ]0, ∞[, mais l’est sur ]ε, ∞[, quel que soit
ε > 0 (le module de Lipschitz peut y être pris égal à 1/ε).
 m
80 3. Fonctions convexes

Proposition 3.13 (continuité lipschitzienne) Si f ∈ Conv(E), alors f est

lipschitzienne sur tout convexe compact inclus dans (dom f )−
◦
.

Démonstration. Sans perte de généralité, on peut supposer que le domaine de f est

No
d’intérieur non vide (dans le cas contraire, on travaille sur aff(dom f ), comme dans
la démonstration de la proposition 3.6). Soient n = dim E et K un convexe compact
non vide de (dom f )◦ .
Montrons, en utilisant le lemme 3.12, que pour tout x0 ∈ K, il existe un ε0 > 0 et
une constante L > 0 tels que B(x0 , ε0 ) ⊆ (dom f )◦ et f est lipschitzienne de module L
sur B(x0 , ε0 ). Soit x0 ∈ K. Comme dans la démonstration de la proposition 2.15, on
peut construire un simplexe

∆ = co{z0 , z1 , . . . , zn } ⊆ dom f, avec x0 ∈ ∆◦ .

Dès lors, il existe ε′0 > 0 tel que B(x0 , ε′0 ) ⊆ ∆. AlorsPf est majorée par une cons-
tante M sur cette boule, car tout x ∈ ∆ s’écrit x = ni=0 αi zi avec (α0 , . . . , αn ) ∈
∆n+1 , si bien que, par convexité de f , on a
nom
n
X
f (x) 6 αi f (zi ) =: M.
i=0

Par ailleurs, f est aussi minorée inférieurement sur B(x0 , ε′0 ), car elle a une minorante
affine (proposition 3.6). Par le lemme 3.12, il existe un ε0 ∈ ]0, ε′0 ] tel que f est
lipschitzienne sur B(x0 , ε0 ).
En utilisant la propriété de Heine-Borel pour le compact K, on peut déter-
miner des points x1 , . . . , xp ∈ K, tels qu’avec les εi déterminés comme ci-dessus,
les boules B(x0 , εi ) recouvrent K et f est Li -lipschitzienne sur B(x0 , εi ). En prenant
L = max(L1 , . . . , Lp ), on voit que f est L-lipschitzienne sur K. En effet, un segment
[x, y] ⊆ K sera divisé par ces boules en au plus p sous-segments ([x, y] intersecte
chaque boule en un unique sous-segment) sur chacun desquels f est L-lipschitzienne ;
en ordonnant ces sous-segments de [x, y], on trouve que |f (y) − f (x)| 6 Lky − xk. ✷

3.3.2 Différentiabilité
Pre

En tout point où elle prend une valeur finie, une fonction convexe admet des
dérivées directionnelles suivant toutes directions (on se rappelle que l’on n’a pas besoin
de topologie sur E pour que cette notion de différentiabilité ait un sens). C’est ce que
l’on montre avec la proposition suivante. Dans cette affirmation, la notion de dérivée
directionnelle est prise dans un sens élargi : on accepte les valeurs −∞ ou +∞. Ceci
revient à dire que la limite dans

f (x + td) − f (x)
f ′ (x; d) = lim ,
t↓0 t

qui est normalement prise dans R pour les fonctions réelles, est prise ici dans R.
 m
3.3. Régularité 81

Proposition 3.14 (différentiabilité directionnelle) Soient E un espace vec-

toriel, f : E → R une fonction convexe, x ∈ E un point tel que f (x) est fini et
d ∈ E. Alors
(i) la fonction

No
f (x + td) − f (x)
t ∈ R++ 7→ ∈R
t
est croissante ;
(ii) f ′ (x; d) existe dans R (elle vaut éventuellement −∞ ou +∞) ;
(iii) f ′ (x; d) vaut +∞ si, et seulement si, x + td ∈ / dom f pour tout t > 0 ;
(iv) on a
f ′ (x; d) > −f ′ (x; −d) ; (3.7)
en particulier, si l’une des deux dérivées directionnelles f ′ (x; d) ou f ′ (x; −d)
vaut −∞ l’autre vaut +∞.

Démonstration. [(i)] Soient 0 < t1 < t2 . Si x + t2 d ∈ / dom f , la croissance du

quotient dans (i) est claire. Si x + t2 d ∈ dom f , alors x + t1 d ∈ dom f (convexité
de dom f et x ∈ dom f ) et par la convexité de f , on a
nom
  
t1 t1
f (x + t1 d) = f 1− x + (x + t2 d)
t2 t2
 
t1 t1
6 1− f (x) + f (x + t2 d).
t2 t2
Comme f (x) ∈ R, on en déduit
f (x + t1 d) − f (x) f (x + t2 d) − f (x)
6 .
t1 t2
[(ii) et (iii)] Donc, lorsque t ↓ 0 de façon monotone, la fonction ξ définie en (i)
décroît. Si x + td ∈ / dom f pour tout t > 0, alors ξ(t) = +∞ et f ′ (x; d) = +∞. Dans
le cas contraire, la limite ξ(0+ ) existe comme limite d’une suite décroissante (et vaut
éventuellement −∞).
[(iv)] Si f ′ (x; d) ou f ′ (x; −d) = +∞, il n’y a rien à démontrer. Dans le cas
contraire, x − td et x + td ∈ dom f pour t > 0 assez petit. Pour ces t > 0, la convexité
de f implique que
Pre

 
x + td x − td 1 1
f (x) = f + 6 f (x + td) + f (x − td).
2 2 2 2
On en déduit (iv) par passage à la limite lorsque t ↓ 0, après avoir retranché f (x) aux
deux membres. ✷

Deux remarques sur ce résultat.

D’après le point (iii), on n’aura f ′ (x; d) = +∞ que si f (x + td) = +∞ pour tout
t > 0. Mais on peut très bien avoir f ′ (x; d) = −∞, alors que f (x + td) > −∞
pour tout t > 0. C’est le cas en x = 0 pour la fonction convexe définie par
 m
82 3. Fonctions convexes

0
 √
− x si x > 0 √
f (x) = − x (3.8)
+∞ sinon

et la direction d = 1.

No
Le point (iv) montre que l’on peut comparer f ′ (x; d) et f ′ (x; −d) lorsque la fonc-
tion f est convexe. Si f n’est pas dérivable en x, en général f ′ (x; d) 6= −f ′ (x; −d).
Par exemple, si f (x) = |x|, x ∈ R, on a f ′ (0; 1) = f ′ (0; −1) = 1.
Par ailleurs, la fonction (3.8) donne un exemple d’application de la formule (3.7)
avec des valeurs infinies : f ′ (0; 1) = −∞ implique que f ′ (0; −1) = +∞.
Pour x fixé tel que f (x) ∈ R, la proposition suivante étudie les propriétés de
l’application dérivée directionnelle
δx : d ∈ E 7→ δx (d) = f ′ (x; d) ∈ R. (3.9)

Proposition 3.15 (application dérivée directionnelle) Soient E un espace

normé, f : E → R une fonction convexe et x ∈ E un point tel que f (x) soit fini.
nom
Alors l’application dérivée directionnelle (3.9) vérifie les propriétés suivantes :
1) δx est sous-linéaire,
2) si x ∈ (dom f )−◦
, alors
a) dom δx est le sous-espace vectoriel E0 de E parallèle à aff(dom f ),
b) δx ∈ Conv(E),
c) δx est lipschitzienne sur E0 .

Démonstration. 1) Montrons d’abord la convexité de δx . Soient d1 , d2 ∈ dom δx et

α ∈ [0, 1]. Alors x + td1 et x + td2 ∈ dom f pour t > 0 assez petit (proposition 3.14,
point (iii)). Par convexité de f , on a
1n   o
δx ((1−α)d1 + αd2 ) = lim f x + t[(1−α)d1 + αd2 ] − f (x)
t↓0 t | {z }
=(1−α)[x+td1 ]+α[x+td2 ]
∈ dom f pour t > 0 petit
1n o
6 lim (1−α)f (x+td1 ) + αf (x+td2 ) − f (x)
t↓0 t
Pre

1n    o
= lim (1−α) f (x+td1 ) − f (x) + α f (x+td2 ) − f (x)
t↓0 t
= (1−α)δx (d1 ) + αδx (d2 ).
Montrons à présent l’homogénéité positive de degré 1 de δx . Soient d ∈ E et α > 0.
On a
f (x + tαd) − f (x) f (x + τ d) − f (x)
δx (αd) = lim α = α lim = αδx (d).
t↓0 αt τ ↓0 τ
2) On suppose à présent que x ∈ (dom f )− ◦
(donc f est propre, voir l’exercice 3.3)
et on note E0 le sous-espace vectoriel parallèle à aff(dom f ).
 m
3.3. Régularité 83

2.a) Si d ∈ / E0 , x + td ∈/ dom f pour tout t > 0, si bien que δx (d) = +∞ et

d ∈/ dom δx . Par ailleurs, si d ∈ E0 , x + td ∈ dom f pour tout t > 0 petit (car
x ∈ (dom f )−◦
, si bien que δx (d) < +∞ et d ∈ dom δx .
2.b) La fonction δx est convexe (point 1) et propre (car son domaine est un sous-
espace vectoriel et que δx (0) = 0, donc elle ne peut pas prendre la valeur −∞ sur
son domaine). Elle est donc localement lipschitzienne sur E0 (proposition 3.13), donc

No
certainement s.c.i. sur E0 .
2.c) D’après la proposition 3.13, f est localement lipschitzienne sur (dom f )−◦
.
−
◦
Comme x ∈ (dom f ) , il existe r > 0 tel que f soit lipschitzienne sur B(x, r) ∩
aff(dom f ), disons de module L > 0, Alors pour d ∈ E0 et t > 0 assez petit, |f (x +
td) − f (x)| 6 Ltkdk. En divisant par t > 0 en passant à la limite lorsque t ↓ 0, on
trouve
∀ d ∈ E0 , |δx (d)| 6 Lkdk. (3.10)
Soient d1 et d2 ∈ E0 . Dès que t > 1, la monotonie du quotient différentiel de la fonc-
tion convexe δx (proposition 3.14) et l’homogénéité positive de cette même fonction
assurent que
δx (d1 + t(d2 − d1 )) − δx (d1 )
δx (d2 ) − δx (d1 ) 6
 t   
1 1
nom
= δx d1 + d2 − d1 − δx d1 .
t t
Comme δx est continue sur E0 , lorsque t → ∞, le membre de droite converge vers
δx (d2 − d1 ) qui, par (3.10), est majoré par Lkd2 − d1 k. En inversant le rôle de d1 et
d2 , on obtient |δx (d2 ) − δx (d1 )| 6 Lkd2 − d1 k. ✷

Intéressons-nous à présent à des propriétés de différentiabilité plus forte que la

différentiabilité directionnelle, qui est toujours vérifiée par les fonctions convexes,
comme nous l’avons vu à la proposition 3.14. La proposition 3.17 ci-dessous montre
que les trois notions de différentiabilité suivantes coïncident pour une fonction convexe
f : E → R en un point x ∈ E où elle prend une valeur finie (la situation est plus
complexe en dimension infinie [498 ; 1993]).
On dit que f a une dérivée partielle en x suivant un vecteur d ∈ E si la fonction
t ∈ R 7→ f (x + td) est différentiable en t = 0.
On dit que f est Gâteaux-différentiable en x si la dérivée directionnelle f ′ (x; d)
existe et est finie pour tout d ∈ E et si d ∈ E 7→ f ′ (x; d) est linéaire.
On dit que f est Fréchet-différentiable en x s’il existe un vecteur D ∈ E tel que
Pre

f (x + d) − f (x) − hD, di
lim = 0. (3.11)
d→0 kdk
d6=0

Dans ce cas, le vecteur D est appelé le gradient de f en x et est noté ∇f (x).

D’après la définition, si f est Fréchet-différentiable en x, f prend des valeurs
finies dans un voisinage de x.
Commençons par un lemme qui montre que la dérivée directionnelle en un point
(non nécessairement linéaire par rapport à la direction de dérivation) est une appro-
ximation au premier ordre de f en ce point. On pourra rapprocher (3.12) de (3.11).
Cette propriété est essentiellement due à la lipschitzianité de f et de f ′ (x; ·).
 m
84 3. Fonctions convexes

Lemme 3.16 (développement au premier ordre) Soient E un espace vec-

toriel de dimension finie, f ∈ Conv(E) et x ∈ (dom f )◦ . Alors

f (x + d) − f (x) − f ′ (x; d)
lim = 0. (3.12)

No
d→0 kdk
d6=0

Démonstration. Si (3.12) n’a pas lieu, il existe un ε > 0 et une suite de directions
non nulles {dk } convergeant vers zéro, tels que
∀k > 1 : |f (x + dk ) − f (x) − f ′ (x; dk )| > εkdk k.
En extrayant une sous-suite au besoin, on peut supposer qu’avec tk := kdk k, la suite
bornée {dk /tk } converge vers un d ∈ E. Alors
1
ε 6 |f (x + dk ) − f (x + tk d)|
tk
1
+ |f (x + tk d) − f (x) − f ′ (x; tk d)|
tk
nom
1
+ |f ′ (x; tk d) − f ′ (x; dk )|.
tk
Comme x ∈ (dom f )◦ , f est lipschitzienne dans un voisinage de x (proposition 3.13)
et f ′ (x; ·) est lipschitzienne sur E (proposition 3.15), disons de même constante L > 0.
Dès lors, les premier et troisième termes du membre de droite ci-dessus sont majorés
par Lkdk /tk −dk → 0. Quant au second terme, il tend aussi vers zéro, par la définition
et la positive homogénéité de la dérivée directionnelle. On aboutit donc bien à une
contradiction puisque ε > 0. ✷

Proposition 3.17 (différentiabilité) Soient E un espace vectoriel de dimen-

sion n, f ∈ Conv(E) et x ∈ (domf )◦ . Alors les propriétés suivantes sont équiva-
lentes :
(i) f a des dérivées partielles en x suivant n directions linéairement indépen-
dantes,
(ii) f est Gâteaux-différentiable en x,
Pre

(iii) f est Fréchet-différentiable en x.

Démonstration. [(i) ⇒ (ii)] Comme f ′ (x; ·) est sous-linéaire (point 1 de la propo-

sition 3.15) et linéaire suivant n directions linéairement indépendantes (hypothèse),
elle est linéaire sur l’espace vectoriel engendré par ces directions (proposition 3.9),
c’est-à-dire sur E.
[(ii) ⇒ (iii)] La linéarité supposée de f ′ (x; ·) et (3.12) montrent que f est Fréchet
différentiable en x.
[(iii) ⇒ (i)] Vrai quelle que soit la fonction f . ✷
 m
3.3. Régularité 85

3.3.3 Reconnaître une fonction convexe par ses dérivées

Les résultats de cette section donnent des critères (souvent même des caractérisa-
tions, c’est-à-dire des conditions nécessaires et suffisantes) de convexité d’une fonction
au moyen de ses dérivées. Ces critères sont souvent le moyen le plus rapide de vérifier
qu’une fonction régulière est convexe.

No
Pour étudier la convexité d’une fonction on est amené à examiner ses valeurs le long
des segments [x, y], pour tout x, y ∈ E. C’est la définition qui l’impose. Chaque fois que
l’on se fixe les points x et y, on se ramène à l’étude d’une fonction réelle d’une variable
réelle. Les premières caractérisations (propositions 3.18, 3.20 et 3.23) n’utilisent que
ces fonctions « réduites » aux segments [x, y]. Au contraire, les corollaires 3.19 et 3.21
et la proposition 3.25 utilisent les valeurs de la fonction sur des voisinages. On a alors
besoin d’une topologie sur E et d’avoir une fonction f dont le domaine contienne un
ouvert. Si ce n’est pas le cas, le domaine de f est toutefois d’intérieur relatif non vide.
Lorsque l’on peut représenter ce sous-espace comme l’image d’une application linéaire
continue bijective L : E0 → aff(dom f ), il est possible d’étudier la convexité de f à
partir de celle de f ◦ L sur un ouvert de l’espace normé E0 .

Utilisation des dérivées premières

nom
Convexité

La proposition suivante montre que l’on peut caractériser la convexité d’une

fonction f par le fait que celle-ci est au-dessus des fonctions affines obtenues par
linéarisation de f (point (ii)) ou encore en exprimant que ses dérivées direction-
nelles sont monotones (point (iii)). Ceci est illustré à la figure 3.4. La fonction f

f
   
x−y
pente = −f ′ x; kx−yk
y−x
pente = f ′ y; ky−xk

 
y−x
pente = f ′ x; ky−xk f (y)
f (x)
x f (x) + f ′ (x; y − x)
y
Pre

Fig. 3.4. Caractérisations de la convexité

qui y est représentée est convexe.  On voit  qu’elle

 est au-dessus
 de la fonction affine
y−x y−x
y 7→ f (x) + f ′ (x; y−x) et que f ′ y; ky−xk > f ′ x; ky−xk . On rappelle qu’une fonc-
tion convexe admet des dérivées directionnelles (pouvant valoir −∞ ou +∞) en tout
point de son domaine (proposition 3.14).
 m
86 3. Fonctions convexes

Proposition 3.18 (convexité et dérivées premières) Soient E un espace

normé et f : E → R ∪ {+∞} une fonction non identiquement égale à +∞,
ayant un domaine convexe et admettant des dérivées directionnelles en tout point
de son domaine (celles-ci pouvant valoir −∞ ou +∞). Alors, les propriétés sui-

No
vantes sont équivalentes :
(i) f est convexe ;
(ii) ∀ x, y ∈ dom f , x 6= y : f est continue sur ]x, y[ et f (y) > f (x)+f ′ (x; y−x) ;
(iii) ∀ x, y ∈ dom f , x 6= y : f est continue sur ]x, y[ et f ′ (y; y −x) > f ′ (x; y −x).
Ces propriétés impliquent que
(iv) ∀ x, y ∈ dom f : f ′ (x; y − x) + f ′ (y; x − y) 6 0.

Démonstration. [(i) ⇒ (ii)] Soient x, y ∈ dom f , x 6= y. Si f ′ (x; y − x) = −∞,

l’inégalité dans (ii) est trivialement vérifiée. Sinon f ′ (x; y−x) a une valeur finie (par la
proposition 3.14 : f est convexe et x, y ∈ dom f , donc f ′ (x; y − x) < +∞) et l’inégalité
dans (ii) s’obtient grâce à la convexité de f par
1 
f ′ (x; y − x) = lim f (x + t(y − x)) − f (x)
nom
t↓0 t
1 
= lim f ((1−t)x + ty) − f (x)
t↓0 t
1 
6 lim (1−t)f (x) + tf (y) − f (x)
t↓0 t
= f (y) − f (x).

D’autre part, l’application ξ : [0, 1] → R : t 7→ f ((1−t)x + ty) est convexe et bornée

supérieurement par max(f (x), f (y)). Elle est aussi bornée inférieurement. Pour mon-
trer cela, prenons par exemple le point milieu z = x+y ′ ′
2 . Alors f (z; x−z) et f (z; y −z)
sont toutes les deux finies (elles ne valent pas +∞ car f est convexe et x, y, z ∈ dom f
et ne peuvent alors pas prendre la valeur −∞ par la proposition 3.14 (iv)). Alors ξ
est bornée inférieurement par inf(f (z), f (z) + f ′ (z; x − z), f (z) + f ′ (z; y − z)). On en
déduit que ξ est continue sur ]0, 1[ par le lemme 3.12.
[(ii) ⇒ (i)] Si f n’est pas convexe, il existe x, y ∈ dom f , x 6= y, et t̂ ∈ ]0, 1[ tel
que ẑ := (1−t̂)x + t̂y vérifie
Pre

f (ẑ) > (1−t̂)f (x) + t̂f (y).

Soit t1 := inf{t̄ ∈ [0, t̂] : f ((1−t)x+ty) > (1−t)f (x)+tf (y), ∀ t ∈ ]t̄, t̂]}. Par continuité
de f sur ]x, y[, un tel t1 existe. D’autre part, soit parce que t1 = 0, soit par continuité
de f sur ]x, y[, on a avec z1 := (1−t1 )x + t1 y

f (z1 ) = (1−t1 )f (x) + t1 f (y).

Remarquons que f est continue sur [z1 , ẑ]. En effet, f étant continue sur ]x, y[ par
hypothèse, il reste à montrer la continuité de f en z1 lorsque t1 = 0. Mais si t1 = 0,
lim inf t↓0 f ((1−t)x + ty) > f (x). Or lim supt→0+ f ((1−t)x + ty) ne peut être > f (x)
sinon f ′ (x; y − x), qui est supposé exister, vaudrait +∞, ce qui contredirait l’inégalité
 m
3.3. Régularité 87

de (ii) (f (x) et f (y) sont finis). Donc f est continue sur [z1 , ẑ] et on peut appliquer
la version généralisée du théorème de Rolle (corollaire C.11) : il existe t2 ∈ ]t1 , t̂[ tel
que z2 := (1−t2 )x + t2 y vérifie
 
′ y − z2 f (ẑ) − f (z1 )
f z2 ; > .
ky − z2 k kẑ − z1 k

No
On peut alors conclure comme suit :

f (z2 ) + f ′ (z2 ; y − z2 ) > (1−t2 )f (x) + t2 f (y)

1 − t2  
+ (1−t̂)f (x) + t̂f (y) − (1−t1 )f (x) − t1 f (y)
t̂ − t1
= (1−t2 )f (x) + t2 f (y) + (1 − t2 )(f (y) − f (x))
= f (y),

ce qui contredit l’inégalité de (ii).

[(ii) ⇒ (iv)] Soient x, y ∈ dom f . L’inégalité est triviale si x = y. Sinon, on utilise
l’inégalité de (ii) en intervertissant le rôle de x et de y

f (y) > f (x) + f ′ (x; y − x)

nom
f (x) > f (y) + f ′ (y; x − y).

En sommant, on obtient (iv).

[(i), (ii) ⇒ (iii)] Soient x, y ∈ dom f , x 6= y. Si f ′ (y; y − x) = +∞, (iii) est
trivialement vérifiée. Sinon, d’après la proposition 3.14 (iv), f ′ (y; y − x) est fini (dans
le cas contraire, on devrait avoir f ′ (y; x−y) = +∞, ce qui contredirait le fait que x, y ∈
dom f ) et f ′ (y; x − y) > −f ′ (y; y − x). En utilisant cette inégalité et en intervertissant
les rôles de x et y dans l’inégalité de (ii), on obtient

f (y) > f (x) + f ′ (x; y − x)

f (x) > f (y) − f ′ (y; y − x).

En sommant, on obtient (iii).

[(iii) ⇒ (i)] Si f n’est pas convexe, il existe x, y ∈ dom f , x 6= y, et t̂ ∈ ]0, 1[ tels
que ẑ := (1−t̂)x + t̂y vérifie

f (ẑ) > (1−t̂)f (x) + t̂f (y).

Pre

On peut trouver t̂1 ∈ [0, t̂] tel que ẑ1 := (1−t̂1 )x + t̂1 y vérifie

f (ẑ1 ) = (1−t̂1 )f (x) + t̂1 f (y)

et tel que f soit continue sur [ẑ1 , ẑ]. On peut s’y prendre, par exemple, comme dans
la détermination de t1 dans la démonstration de l’implication (ii) ⇒ (i) ; ici, si t̂1 =
0, on ne peut pas avoir lim supt↓0 f ((1−t)x + ty) > f (x) car cela impliquerait que
f ′ (x; y − x) = +∞, ce qui est en contradiction avec l’hypothèse de monotonie des
dérivées directionnelles et le fait qu’il y a des points z entre x et y où f ′ (z; y − x) est
finie. Pour les mêmes raisons, on peut trouver t̂2 ∈ [t̂, 1] tel que ẑ2 := (1−t̂2 )x + t̂2 y
vérifie
 m
88 3. Fonctions convexes

f (ẑ2 ) = (1−t̂2 )f (x) + t̂2 f (y)

et tel que f soit continue sur [ẑ, ẑ2 ]. On peut alors appliquer la variante du théorème
de Rolle donnée au corollaire C.11 : il existe t1 ∈ ]t̂1 , t̂[ et t2 ∈ ]t̂, t̂2 [ tels que z1 :=
(1−t1 )x + t1 y et z2 := (1−t2 )x + t2 y vérifient

No
f (ẑ) − f (ẑ1 ) f (ẑ2 ) − f (ẑ)
f ′ (z1 ; y − x) > et f ′ (z2 ; y − x) 6 .
t̂ − t̂1 t̂2 − t̂

On en déduit que f ′ (z2 ; y−x) < f (y)−f (x) < f ′ (z1 ; y−x), ce qui contredit l’hypothèse
de monotonie des dérivées directionnelles dans (iii). ✷

Sans la continuité de f sur les segments ]x, y[, l’inégalité de (ii) peut très bien être
vérifiée par une fonction non convexe. En voici un exemple sur R : f (x) = 0, si x 6= 0,
et f (0) = 1 (on a f ′ (x; ±1) = 0, si x 6= 0, et f ′ (0; ±1) = −∞).
La démonstration de la proposition précédente est longue parce que nous avons
fait des hypothèses minimales sur la régularité de f . Si l’on suppose que le domaine
de f est un ouvert convexe d’un espace normé E et que f est dérivable sur cet ouvert,
on a un résultat plus simple à mémoriser et à démontrer. Nous le donnons sous forme
de corollaire.
nom
Corollaire 3.19 Soient E un espace normé, Ω un ouvert convexe de E et f :
Ω → R une fonction dérivable. Alors, les propriétés suivantes sont équivalentes :
(i) f est convexe sur Ω ;
(ii) ∀ x, y ∈ Ω : f (y) > f (x) + f ′ (x) · (y − x) ;
(iii) ∀ x, y ∈ Ω : (f ′ (y) − f ′ (x)) · (y − x) > 0.

Convexité stricte

On a un résultat analogue à celui de la proposition 3.18 pour les fonctions stricte-

ment convexes.

Proposition 3.20 (stricte convexité et dérivées premières I) Soient E un

espace normé et f : E → R ∪ {+∞} une fonction non identiquement égale à
+∞, ayant un domaine convexe et admettant des dérivées directionnelles en tout
point de son domaine (celles-ci pouvant valoir −∞ ou +∞). Alors, les propriétés
Pre

suivantes sont équivalentes :

(i) f est strictement convexe ;
(ii) ∀ x, y ∈ dom f , x 6= y : f est continue sur ]x, y[ et f (y) > f (x)+f ′ (x; y −x) ;
(iii) ∀ x, y ∈ dom f , x 6= y : f est continue sur ]x, y[ et f ′ (y; y − x) > f ′ (x; y − x).

Démonstration. [(i) ⇒ (ii)] Supposons que f soit strictement convexe et soient

x, y ∈ dom f , x 6= y. La continuité de f sur ]x, y[ découle de la proposition 3.18. Pour
démontrer l’inégalité stricte de (ii), on ne peut plus utiliser le même raisonnement
que dans la démonstration de la proposition 3.18, car le passage à la limite détruirait
 m
3.3. Régularité 89

l’inégalité stricte que l’on a pour les fonctions strictement convexes. On s’y prend
alors comme suit. Pour t ∈ ]0, 1], on a
1 ′ 1 
f ′ (x; y − x) = f (x; t(y − x)) 6 f (x + t(y − x)) − f (x) < f (y) − f (x),
t t

No
où pour la première inégalité on a utilisé la proposition 3.18 (ii) et pour la seconde
on a utilisé la stricte convexité de f .
[(ii) ⇒ (iii)] Si (iii) n’a pas lieu, il existe x, y ∈ dom f , x 6= y, tels que f ′ (y; y −
x) 6 f ′ (x; y − x). Par la proposition 3.18, on a f ′ (z; y − x) = f ′ (x; y − x) pour tout
z ∈ [x, y] et cette valeur est finie. On en déduit (par exemple par le corollaire C.10,
en y prenant ϕ(t) = ±(f ((1−t)x + ty) − tf ′ (x; y − x)) pour t ∈ [0, 1]) que f (y) =
f (x) + f ′ (x; y − x), ce qui contredit (ii).
[(iii) ⇒ (i)] Si f n’est pas strictement convexe, il existe x, y ∈ dom f , x 6= y, et
t̂ ∈ ]0, 1[ tels que ẑ := (1−t̂)x + t̂y vérifie

f (ẑ) > (1−t̂)f (x) + t̂f (y).

Comme f est convexe (proposition 3.18) ceci ne peut avoir lieu que si f est affine
entre x et y. Mais alors, la stricte monotonie des dérivées directionnelles dans (iii) ne
serait pas vérifiée. ✷
nom
Énonçons également sous forme de corollaire, le résultat que donne la proposi-
tion 3.20 lorsque f est dérivable.

Corollaire 3.21 Soient E un espace normé, Ω un ouvert convexe de E et f :

Ω → R une fonction dérivable. Alors, les propriétés suivantes sont équivalentes :
(i) f est strictement convexe sur Ω ;
(ii) ∀ x, y ∈ Ω, x 6= y : f (y) > f (x) + f ′ (x) · (y − x) ;
(iii) ∀ x, y ∈ Ω, x 6= y : (f ′ (y) − f ′ (x)) · (y − x) > 0.

Pour une fonction strictement convexe, contnûment différentiable, définie sur un

espace de dimension finie, les inégalités de la proposition 3.20 et de son corollaire 3.21
peuvent être renforcées [262 ; lemmes 1.1 et 1.2, pages 61 et 63]. Les inégalités (3.13)
et (3.14) qui sont établies dans la proposition suivante seront à nouveau renforcées
pour les fonction fortement convexes (proposition 3.23).
Pre

Proposition 3.22 (stricte convexité et dérivées premières II) Soient E

un espace vectoriel de dimension finie, f : E → R une fonction de classe C 1 et
t ∈ ]0, 1[. Alors les propriétés suivantes sont équivalentes :
(i) f est strictement convexe,
(ii) pour tout β > 0, il existe une fonction gβ : [0, 2β] → R+ continue, stricte-
ment croissante, vérifiant gβ (0) = 0 et

∀ x, y ∈ β B̄ : f (y) − f (x) > f ′ (x) · (y − x) + (1 − t)gβ (tky − xk), (3.13)

 m
90 3. Fonctions convexes

(iii) pour tout β > 0, il existe une fonction gβ : [0, 2β] → R+ continue, stricte-
ment croissante, vérifiant gβ (0) = 0 et

∀ x, y ∈ β B̄ : (f ′ (y) − f ′ (x)) · (y − x) > gβ (ky − xk). (3.14)

No
Démonstration. [(i) ⇒ (iii)] Soit β > 0. Au vu de la propriété désirée (3.14), il est
naturel d’introduire la fonction gβ0 : [0, 2β] → R+ définie en α ∈ [0, 2β] par
 
gβ0 (α) := inf f ′ (y) − f ′ (x) · (y − x).
ky−xk=α
x,y∈β B̄

Cette fonction a toutes les propriétés requises par le point (ii), hormis la continuité.
Montrons cela.
1. gβ0 (0) = 0, clairement.
2. gβ0 > 0 sur ]0, 2β], grâce à la stricte convexité de f et au point (iii) de la propo-
sition 3.20.
nom
3. gβ0 est strictement croissante sur [0, 2β]. En effet, soient 0 < α1 < α2 6 2β.
Remarquons d’abord que l’infimum dans la définition de gβ0 est atteint, car
{(x, y) ∈ β B̄ × β B̄ : ky − xk = α} est compact (E est de dimension finie)
et (x, y) 7→ (f ′ (y) − f ′ (x)) · (y − x) est continue (f est continûment différen-
tiable), puis on utilise alors le théorème de Weierstrass. Il existe donc des points
(x2 , y2 ) ∈ β B̄ × β B̄ tels que ky2 − x2 k = α2 et
 
gβ0 (α2 ) = f ′ (y2 ) − f ′ (x2 ) · (y2 − x2 ).

En introduisant y := x2 + (α1 /α2 )(y2 − x2 ), on a grâce à la stricte convexité de f

et 0 < α1 < α2 :
   
f ′ (y2 ) − f ′ (x2 ) · (y2 − x2 ) > f ′ (y) − f ′ (x2 ) · (y2 − x2 ).

En combinant ces deux relations, on obtient

 
Pre

gβ0 (α2 ) > f ′ (y) − f ′ (x2 ) · (y2 − x2 )

α2  ′ 
= f (y) − f ′ (x2 ) · (y − x2 ) [définition de y]
α
1 
> f ′ (y) − f ′ (x2 ) · (y − x2 ) [α2 > α1 et y 6= x2 ]
> gβ0 (α1 ) [ky − x2 k = α1 ].

D’où la croissance stricte de gβ0 .

4. Par définition même de gβ0 , (3.14) a lieu avec gβ = gβ0 .
 m
3.3. Régularité 91

Pour ontenir une fonction continue gβ , on utilise une technique de dérivation

intégration. Soient x et y ∈ β B̄. Comme ci-dessus, en intégrant la dérivée de
s 7→ f (x + s(y − x)), on obtient
Z 1
f (y) − f (x) = f ′ (x + s(y − x)) · (y − x) ds.

No
0

Mais x + s(y − x) ∈ β B̄ (convexité de β B̄) et (3.14) a lieu avec gβ = gβ0 , si bien que
  1
f ′ (x + s(y − x)) − f ′ (x) · (y − x) > gβ0 (sky − xk).
s
qui, avec l’identité précédente donne
Z 1
′ 1 0
f (y) − f (x) > f (x) · (y − x) + g (sky − xk) ds.
0 s β

En échangeant x et y et en additionnant, on obtient

  Z 1 Z ky−xk
′ ′ 2 0 2 0
f (y) − f (x) · (y − x) > g (sky − xk) ds = g (r) dr.
s β r β
nom
0 0

On obtient alors (3.14) en définissant gβ : [0, 2β] → R+ en s ∈ [0, 2β] par

Z s
2 0
gβ (s) = gβ (r) dr.
0 r

Par ailleurs, il est clair que gβ est continue, strictement croissante et vérifie gβ (0) = 0.
[(iii) ⇒ (ii)] Il s’agit de montrer que (3.14) implique (3.13). Comme ci-dessus, en
intégrant la dérivée de s 7→ f (x + s(y − x)), on obtient
Z 1
f (y) − f (x) = f ′ (x + s(y − x)) · (y − x) ds
0
Z 1
1
> f ′ (x) · (y − x) + gβ (sky − xk) ds [(3.14)]
0 s
Z 1
1
> f ′ (x) · (y − x) + gβ (sky − xk) ds [gβ > 0]
t s
> f ′ (x) · (y − x) + (1 − t) gβ (tky − xk),
Pre

car pour s ∈ [t, 1], gβ (sky − xk) > gβ (tky − xk) (croissance de gβ ) et s 6 1, si bien
que gβ (sky − xk)/s > gβ (tky − xk).
[(ii) ⇒ (i)] Soient x et y deux points distincts de E. On prend β := ky − xk,
qui est strictement positif. Par (3.13) avec t = 21 , on a f (y) − f (x) > f ′ (x) · (y −
x) + 21 gβ ( 21 ky − xk) > f ′ (x) · (y − x), car gβ ( 12 ky − xk) > 0. Donc f est strictement
convexe. ✷
 m
92 3. Fonctions convexes

Convexité forte

On a aussi des caractérisations de la forte convexité au moyen d’inégalités renfor-

cées. La démonstration du résultat est proposée à l’exercice 3.11.

No
Proposition 3.23 (forte convexité et dérivées premières) Soient E un
espace vectoriel euclidien (produit scalaire h·, ·i et norme associée k · k), α > 0
et f : E → R ∪ {+∞} une fonction non identiquement égale à +∞, ayant un
domaine convexe et admettant des dérivées directionnelles en tout point de son
domaine (celles-ci pouvant valoir −∞ ou +∞). Alors, les propriétés suivantes
sont équivalentes :
(i) f est fortement convexe de module α ;
(ii) pour tout x, y ∈ dom f , x 6= y : f est continue sur ]x, y[ et
f (y) > f (x) + f ′ (x; y − x) + α2 ky − xk2 ;
(iii) pour tout x, y ∈ dom f , x 6= y : f est continue sur ]x, y[ et
f ′ (y; y − x) > f ′ (x; y − x) + αky − xk2 .

Ce résultat s’énonce plus simplement lorsque la fonction est différentiable.

nom
Corollaire 3.24 Soient E un espace euclidien, Ω un ouvert convexe de E et f :
Ω → R une fonction dérivable. Alors, les propriétés suivantes sont équivalentes :
(i) f est fortement convexe sur Ω ;
(ii) ∀ x, y ∈ Ω : f (y) > f (x) + f ′ (x) · (y − x) + α2 ky − xk2 ;
(iii) ∀ x, y ∈ Ω : (f ′ (y) − f ′ (x)) · (y − x) > αky − xk2 .

Utilisation des dérivées secondes

On peut également donner une caractérisation de convexité d’une fonction (mais
pas de sa stricte convexité) au moyen de ses dérivées secondes.

Proposition 3.25 (convexité et dérivées secondes) Soient E un espace nor-

mé, Ω un ouvert convexe de E et f : Ω → R une fonction deux fois dérivable.
Alors f est convexe sur Ω si, et seulement si,
Pre

∀ x ∈ Ω, ∀ d ∈ E : f ′′ (x) · d2 > 0. (3.15)

D’autre part, si

∀ x ∈ Ω, ∀ d ∈ E \ {0} : f ′′ (x) · d2 > 0, (3.16)

alors f est strictement convexe sur Ω.

Démonstration. Si f est convexe sur Ω, on a pour tout x ∈ Ω et tout d ∈ E (en

utilisant les propositions C.17 et 3.18) :
 m
3.3. Régularité 93
1
f ′′ (x) · d2 = lim (f ′ (x + td) · d − f ′ (x) · d) > 0.
t↓0 t

Inversement, supposons que (3.15) ait lieu. Si x, y ∈ Ω, le théorème C.19 donne

1
f (y) = f (x) + f ′ (x) · (y − x) + f ′′ (x + θ(y − x)) · (y − x)2 ,

No
2
où θ ∈ ]0, 1[. Comme le dernier terme est positif ou nul, on voit par la proposition
3.18 que f est convexe. Le cas où (3.16) a lieu se démontre de la même manière. ✷

Remarquons que la condition (3.16) n’est pas nécessairement vérifiée pour une
fonction strictement convexe comme le montre la fonction x ∈ R 7→ f (x) = x4 .
Bien que celle-ci soit strictement convexe, on a f ′′ (0) = 0. Par contre, pour une
fonction quadratique, (3.16) est une condition nécessaire et suffisante de convexité
stricte (point 2 de l’exercice 3.8).
Lorsque E est un espace de Hilbert, on peut traduire le résultat de la propo-
sition 3.25 en utilisant la hessienne de f : (i) f est convexe si, et seulement si, sa
hessienne ∇2 f (x) est semi-définie positive et (ii) si ∇2 f (x) est défini positif, alors f
est strictement convexe.
nom
3.3.4 Fonction asymptotique

L’épigraphe d’une fonction f ∈ Conv(E) est un convexe fermé non vide. On peut
donc considérer son cône asymptotique (epi f )∞ . Celui-ci a des propriétés intéres-
santes.

Proposition 3.26 (définition de f ∞ ) Soit f ∈ Conv(E). Alors

(i) (epi f )∞ est l’épigraphe d’une fonction f ∞ : E → R ∪ {+∞}: (epi f )∞ =
epi f ∞ ,
(ii) ∀ x ∈ dom f , ∀ d ∈ E:

f (x + td) − f (x)
f ∞ (d) = lim , (3.17)
t→+∞ t
(iii) dom f ∞ ⊆ (dom f )∞ ,
(iv) f ∞ ∈ Conv(E) et est sous-linéaire.
Pre

Démonstration. Commençons par une caractérisation de l’appartenance à (epi f )∞ .

Soit x ∈ dom f (qui est non vide) ; donc f (x) est fini et (x, f (x)) ∈ epi f . Alors

(d, δ) ∈ (epi f )∞ ⇐⇒ (x, f (x)) + t(d, δ) ∈ epi f, ∀ t > 0

⇐⇒ f (x + td) 6 f (x) + tδ, ∀ t > 0. (3.18)

[(i)] Si (d, δ) ∈ (epi f )∞ et δ ′ > δ, (d, δ ′ ) ∈ (epi f )∞ , grâce à (3.18). Fixons à

présent d ∈ E et posons

δ0 := inf{δ : (d, δ) ∈ (epi f )∞ }.

 m
94 3. Fonctions convexes

Il faut montrer que (d, δ0 ) ∈ (epi f )∞ . D’après (3.18)

f (x + td) − f (x)
δ0 = sup .
t>0 t

On en déduit que f (x + td) 6 f (x) + tδ0 , ∀ t > 0, et donc (d, δ0 ) ∈ (epi f )∞ (par

No
(3.18)).
[(ii)] Soit f ∞ la fonction dont (epi f )∞ est l’épigraphe. On a f ∞ (d) = δ0 , ou
encore (3.17), car le quotient ci-dessus est croissant avec t (de fait de la convexité
de f ).
[(iii)] D’après (3.18), si d ∈ dom f ∞ , (d, f ∞ (d)) ∈ (epi f )∞ et f (x + td) 6 α +
tf (d), qui est fini quel que soit t > 0. Donc d ∈ (dom f )∞ .
∞

[(iv)] D’une part, f ∞ est convexe fermée et non identiquement égale à +∞, parce
que son épigraphe est le convexe fermé non vide (epi f )∞ . D’autre part, f ∞ ne prend
pas la valeur −∞ car sa valeur est obtenue comme limite d’une suite croissante (voir
(3.17)). Enfin f est sous-linéaire, car son épigraphe est un cône convexe (proposi-
tion 3.8). ✷

Définition 3.27 On appelle fonction asymptotique (ou fonction de récession) de f ∈

nom
Conv(E) la fonction f ∞ ∈ Conv(E) introduite dans la proposition 3.26. ✷
Quelques remarques sur la proposition 3.26.
D’après la proposition 3.14, on sait que, lorsque x ∈ dom f , le quotient de la
formule (3.17) croît avec t ; il converge vers f ∞ (d) si t → +∞ et vers f ′ (x; d) si
t ↓ 0.
Comme f (x) ∈ R, la formule du point (3.17) s’écrit aussi

f (x + td)
f ∞ (d) = lim , (3.19)
t→+∞ t
avec un quotient f (x + td)/t qui, contrairement au quotient différentiel dans
(3.17), n’est pas nécessairement monotone en t.
L’utilisation de la formule (3.19) est souvent le moyen le plus rapide de calculer
la valeur de la fonction asymptotique en une direction d. Insistons sur le fait que
la limite dans (3.19) ne dépend pas du point x choisi dans le domaine de f .
La formule (3.19) montre que si la fonction t 7→ f (x + td) a une asymptote à
Pre

droite, f ∞ (d) en est sa pente ; sinon f ∞ (d) = +∞.

Si x ∈ dom f et f (x + td) = +∞ pour un t > 0, alors d ∈ / (dom f )∞ et donc
∞ ∞
d∈ / dom f par (iii), c’est-à-dire f (d) = +∞.
On n’a pas nécessairement égalité au point (iii). En effet, si f : R → R est
l’exponentielle, on a f ∞ (1) = +∞. Donc 1 ∈ / dom f ∞ , alors que 1 ∈ (dom f )∞ =
∞
(R) = R.
La notion de fonction asymptotique est illustrée à la figure 3.5.
On note l’ensemble de sous-niveau ν ∈ R d’une fonction f : E → R de la manière
suivante :
Nν (f ) := {x ∈ E : f (x) 6 ν}.
 m
3.3. Régularité 95

f3
f1
f2

No
f3∞
f1∞
f2∞

Fig. 3.5. Exemples de fonctions convexes (en haut) et de leur fonction asymptotique (en
bas) ; de gauche à droite : f1 (x) = (x2 + 10)1/2 , f2 (x) = − log x et f3 (x) = x + ex

C’est un ensemble convexe, lorsque f est convexe. La notion de fonction asympto-

nom
tique est très utile, du fait du résultat suivant, qui montre que pour les fonctions
de Conv(E) ces ensembles de sous-niveau ont tous le même cône asymptotique (s’ils
sont non vides). En particulier, si l’un d’eux est borné non vide, ils sont tous bornés
(éventuellement vides). Un de ces ensembles de sous-niveau est l’ensemble de ses min-
imiseurs :

arg min f := {x ∈ E : f (x) 6 f (x′ ), ∀ x′ ∈ E} = Ninf f (f ).

La fonction asymptotique permet alors de donner des conditions nécessaires et suffi-

santes pour que l’ensemble des minimiseurs soit non vide et compact. D’autres con-
ditions, ne faisant pas intervenir f ∞ et valables pour les fonctions de Conv(E), sont
données à l’exercice 3.36.

Proposition 3.28 (ensembles de sous-niveau d’une fonction conve-

xe) Soit f ∈ Conv(E). Alors, pour tout ν ∈ R tel que Nν (f ) 6= ∅, on a

(Nν (f ))∞ = {d ∈ E : f ∞ (d) 6 0}. (3.20)

Pre

En particulier, les propriétés suivantes sont équivalentes :

(i) ∃ ν ∈ R tel que Nν (f ) est non vide et compact,
(ii) ∀ ν ∈ R, Nν (f ) est compact,
(iii) arg min f est non vide et compact,
(iv) ∀ d ∈ E \ {0}, f ∞ (d) > 0.

Démonstration. Soient ν ∈ R et x ∈ Nν (f ) supposé non vide. Alors

d ∈ (Nν (f ))∞ ⇐⇒ f (x + td) 6 ν, ∀ t > 0.

 m
96 3. Fonctions convexes

Donc si d ∈ (Nν (f ))∞ , f ∞ (d) 6 0 par passage à la limite ci-dessus (après avoir divisé
par t > 0). Inversement, si f ∞ (d) 6 0, f (x + td) 6 f (x), pour tout t > 0 (le quotient
dans (3.17) est croissant et borné par 0). Alors x ∈ Nν (f ) implique que x+td ∈ Nν (f ),
pour tout t > 0 ; donc d ∈ (Nν (f ))∞ .
L’équivalence des propriétés (i)-(iv) se déduit facilement de (3.20). ✷

No
En pratique, pour montrer que f a un ensemble non vide et borné de minimiseurs
(point (iii)), on utilise le point (iv) : quelle que soit la direction non nulle d, f ∞ (d) > 0.
Comme souvent en analyse convexe, on obtient une propriété globale (la bornitude
de l’ensemble des minimiseurs) à partir de propriétés unidirectionnelles (la stricte
positivité de la fonction asymptotique dans toutes les directions non nulles).
Dans le reste de cette section, nous énonçons quelques règles de calcul de fonctions
asymptotiques. La démonstration de la première règle est proposée à l’exercice 3.5.

Proposition 3.29 (pré-composition par une fonction affine) Soient E et F

deux espaces vectoriels, A : E → F une fonction linéaire, b ∈ F et a : x ∈ E →
Ax + b ∈ F l’application affine associée et f ∈ Conv(E) telle que (dom f ) ∩
R(a) 6= ∅. Alors, pour tout d ∈ F,
nom
(f ◦ a)∞ (d) = f ∞ (Ad).

Voici maintenant un résultat permettant de calculer, dans certains cas, la fonction

asymptotique d’une post-composition d’une fonction convexe par une fonction convexe
croissante [30]. La formule (3.21) rappelle celle de la dérivation en chaîne.

Proposition 3.30 (post-composition par une fonction convexe croissan-

te) Supposons données deux fonctions f ∈ Conv(E) et g ∈ Conv(R) telles que
(dom g) ∩ f (E) 6= ∅. On suppose que g est croissante et vérifie g ∞ (1) > 0. Alors
(g ◦ f ) ∈ Conv(E) et pour tout d ∈ E, on a

(g ◦ f )∞ (d) = g ∞ (f ∞ (d)). (3.21)

Dans ce résultat, on a adopté les conventions suivantes : g(f (x)) = +∞ si x ∈

/
dom f et g ∞ (f ∞ (d)) = +∞ si d ∈
/ dom f ∞ .
Pre

Démonstration. D’après [332 ; proposition IV.2.1.8], (g ◦ f ) ∈ Conv(E). Montrons

que
δ < f ∞ (d) =⇒ g ∞ (δ) 6 (g ◦ f )∞ (d). (3.22)
Si δ < f ∞ (d), alors pour t assez grand et x ∈ dom f tel que f (x) ∈ dom g, on a
δ < (f (x + td) − f (x))/t ou encore f (x) + tδ < f (x + td). Comme g est croissante et
f (x) ∈ dom g, on en déduit

g(f (x) + tδ) − g(f (x)) (g ◦ f )(x + td) − (g ◦ f )(x)

6 , pour t grand.
t t
 m
3.4. Opérations 97

Comme f (x) ∈ dom g, la limite dans cette relation conduit à (3.22).

/ dom f ∞ , on peut prendre δ → ∞ dans (3.22), et comme limδ→∞ g ∞ (δ) = ∞
Si d ∈
(car g (1) > 0), on en déduit que (g ◦ f )∞ (d) = ∞.
∞

Si d ∈ dom f ∞ , on prend δ ↓ f ∞ (d) dans (3.22). Comme g ∞ est fermée, on obtient

g ∞ (f ∞ (d)) 6 lim∞inf g ∞ (δ) 6 (g ◦ f )∞ (d).

No
δ↓f (d)

Pour montrer l’inégalité inverse, on prend x ∈ dom f tel que f (x) ∈ dom g. Alors,
quel que soit t > 0, f (x + td) 6 f (x) + tf ∞ (d) et comme g est croissante :

(g ◦ f )(x + td) 6 g(f (x) + tf ∞ (d)).

On divise par t > 0 et on passe à la limite pour t → ∞. Ceci donne (g ◦ f )∞ (d) 6

g ∞ (f ∞ (d)). ✷

3.4 Opérations
J’ai seul la clef de cette parade sauvage.
nom
A. Rimbaud, Parade, Illuminations (1873-1875).

3.4.1 Composition

La fonction composée de deux fonctions f et g, dont l’ensemble d’arrivée de f est

l’ensemble de définition de g, est la fonction notée g ◦ f et définie en x par

(g ◦ f )(x) = g(f (x)).

Si f et g sont convexes, la fonction composée g ◦ f n’est généralement pas convexe.

Relevons toutefois deux exceptions heureuses que l’on rencontre fréquemment, celle
où f est affine et celle où g est convexe croissante. Nous les examinons l’une après
l’autre.

Proposition 3.31 (pré-composition par une fonction affine) Soient E

et F deux espaces vectoriels, a : E → F une application affine et g : F → R
une fonction telle que R(a) ∩ dom g 6= ∅.
Pre

1) Si g ∈ Conv(F), alors g ◦ a ∈ Conv(E).

2) Si g ∈ Conv(F), alors g ◦ a ∈ Conv(E).
3) Si g est convexe polyédrique, alors g ◦ a est convexe polyédrique.

Démonstration. 1) Clairement g ◦ a ∈ Conv(E) lorsque g ∈ Conv(F) et que R(a) ∩

dom g 6= ∅.
2) Introduisons l’application affine

ã : E × R → F × R : (x, α) 7→ (a(x), α).

Alors, (x, α) ∈ epi(g ◦ a) si, et seulement si, (a(x), α) ∈ epi g, ce qui s’écrit
 m
98 3. Fonctions convexes

epi(g ◦ a) = ã−1 (epi g).

Si g ∈ Conv(F), epi g est fermé, donc aussi ã−1 (epi g) = epi(g ◦ a), ce qui montre que
g ◦ a ∈ Conv(E).
3) Si g est convexe polyédrique, epi g est un polyèdre convexe, donc aussi ã−1 (epi g) =
epi(g ◦ a) (exercice 2.18), ce qui montre que g ◦ a est convexe polyédrique. ✷

No
Le second cas où la convexité est préservée par composition se situe dans le cadre
suivant. Soient E un espace vectoriel, F : E → (R ∪ {+∞})m une première fonction et
g : Rm → R une seconde fonction. Avec F pouvant prendre la valeur +∞, la fonction
composée (g ◦ F ) : E → R est définie en x ∈ E par

g(F (x)) si F (x) ∈ Rm
(g ◦ F )(x) =
+∞ sinon.

On munit Rm de l’ordre habituel (c.-à-d., [x 6 y] ⇔ [xi 6 yi pour tout i = 1, . . . , m])

et on dit que g est croissante si g(x) 6 g(y) chaque fois que x 6 y dans Rm .

Proposition 3.32 (post-composition par une fonction convexe croissan-

te) Dans le cadre défini ci-dessus, si F est convexe composante par composante
nom
et si g est convexe et croissante, alors g ◦ F est convexe.

Démonstration. Soient x, y ∈ dom(g ◦ F ) et t ∈ ]0, 1[. Alors F (x) et F (y) ∈ Rm et

la convexité composante par composante de F conduit à

F ((1 − t)x + ty) 6 (1 − t)F (x) + tF (y) (inégalité dans Rm ).

Ensuite



(g ◦ F ) (1 − t)x + ty 6 g (1 − t)F (x) + tF (y) [croissance de g]
6 (1 − t)(g ◦ F )(x) + t(g ◦ F )(y) [convexité de g].

C’est l’inégalité recherchée. ✷

3.4.2 Enveloppes supérieure et inférieure

Pre

L’enveloppe supérieure d’une famille de fonctions est la fonction dont la valeur en

un point est le supremum (ou borne supérieure) des valeurs prises par ces fonctions
en ce point. Soyons plus précis.
Soient E un premier ensemble utilisé comme espace de définition de fonctions et I
un second ensemble utilisé comme ensemble (quelconque) d’indices. Pour tout i ∈ I,
on suppose donnée une fonction fi : E → R. On peut alors introduire la fonction

f = sup fi : E → R,
i∈I

définie pour x ∈ E par

 m
3.4. Opérations 99
 
f (x) = sup fi (x) .
i∈I

Cette fonction est appelée l’enveloppe supérieure des fonctions fi . On définit de

manière similaire, l’enveloppe inférieure des fonctions fi :
   

No
inf fi : E → R : x 7→ inf fi (x) := inf fi (x) .
i∈I i∈I i∈I

De manière plus abstraite, on peut dire que l’enveloppe supérieure de la famille

{fi }i∈I n’est autre que le supremum (ou borne supérieure) de cette famille dans
l’ensemble ordonné réticulé des fonctions définies sur E à valeurs dans R (ou treilli,
c.-à-d., l’ordre [f 6 g] ⇔ [pour tout x ∈ E, f (x) 6 g(x)] est tel que tout couple de
fonctions a une borne supérieure et une borne inférieure). Ceci justifie la notation
supi∈I fi [86 ; 1971, p. IV.21].

Proposition 3.33 Soit {fi }i∈I une famille quelconque de fonctions. Alors
  \
epi sup fi = (epi fi ) .
i∈I i∈I
nom
On en déduit que :
1) supi∈I fi est convexe si E est un espace vectoriel et les fi sont convexes,
2) supi∈I fi est fermée si E est un espace topologique et les fi sont fermées.

Démonstration. En effet (x, α) ∈ epi(supi∈I fi ) ⇐⇒ α > fi (x), pour tout i ∈ I

⇐⇒ (x, α) ∈ epi fi , pour tout i ∈ I ⇐⇒ (x, α) ∈ ∩i∈I (epi fi ). On utilise ensuite le
fait qu’une intersection de convexes [resp. fermés] est convexe [resp. fermée]. ✷

Il se peut cependant que l’enveloppe supérieure de fonctions convexes soit identique-

ment égale à +∞, même si les fi ∈ Conv(E) (par exemple l’enveloppe supérieure des
fonctions constantes).
Le point 2 de la proposition précédente met en évidence l’importance du concept de
fonction fermée (ou s.c.i.) en optimisation : cette propriété est stable pour l’enveloppe
supérieure, une opération souvent rencontrée dans cette discipline. On notera qu’à
l’inverse la continuité des fonctions n’est pas conservée par l’enveloppe supérieure,
comme le montre l’exemple où les fonctions fi : R → R, pour i ∈ R+ , sont définies en
Pre

x ∈ R par

fi (x) = −eix .

L’enveloppe supérieure de ces fonctions continues est nulle sur R∗− et vaut −1 sur R+ ;
elle n’est donc pas continue. Bien sûr, une fonction continue étant s.c.i., l’enveloppe
supérieure de fonctions continues est s.c.i.. Dans l’exemple ci-dessus, la valeur de
l’enveloppe supérieure en zéro est −1, pas zéro ou tout autre valeur > −1.
Le fait que l’enveloppe supérieure de fonctions convexes soit convexe se montre
aussi aisément en utilisant l’inégalité de convexité (3.2), grâce au fait que l’enveloppe
 m
100 3. Fonctions convexes

supérieure d’une somme est inférieure à la somme des enveloppes supérieures. Seule
la convexité des fonctions x 7→ fi (x), à i ∈ I fixé, joue dans l’obtention de ce résultat
(il n’y a d’ailleurs pas de structure sur l’ensemble I). La situation est bien différente
pour l’enveloppe inférieure, qui ne bénéficie pas des deux propriétés numérotées de la
proposition précédente. On peut toutefois avoir la convexité de l’enveloppe inférieure
si l’on a une structure vectorielle sur I et si (x, i) ∈ E × I 7→ fi (x) est convexe. Cela

No
conduit à la notion de fonction marginale de la section suivante.

3.4.3 Fonction marginale

Soient E et F deux espaces vectoriels et ϕ : E × F → R une fonction. On associe à

cette dernière la fonction marginale f : E → R définie par :

f (x) = inf ϕ(x, y). (3.23)

y∈F

Proposition 3.34 1) f est convexe, si ϕ est convexe.

2) f ∈ Conv(E), si ϕ ∈ Conv(E × F) et si f ne prend pas la valeur −∞.
nom
Démonstration. 1) L’épigraphe stricte epis f est la projection sur E×R de epis ϕ ⊆
(E×F)×R. Comme epis est convexe (convexité de ϕ) et que l’image par une application
linéaire d’un convexe est convexe (section 2.1), on en déduit que epis f est convexe ;
donc f est convexe.
2) Il reste à montrer que f 6≡ +∞. Mais si ϕ est propre, il existe un (x, y) tel que
ϕ(x, y) < ∞, donc f (x) < ∞. ✷

La fonction marginale est une enveloppe inférieure de fonctions convexes x 7→

ϕ(x, y), paramétrées par y ∈ F. On pourrait donc, à juste titre, s’étonner de sa
convexité. C’est évidemment la convexité conjointe sur E × F qui permet d’avoir cette
propriété. En comparaison, dans la proposition 3.33, on ne fait aucune hypothèse sur
la structure de l’ensemble I, ni sur la manière dont fi (x) dépend de i.

3.4.4 Inf-convolution

Soient f et g deux fonctions E → R ∪ {+∞}, définies sur un espace vectoriel E.

Leur inf-convolution est la fonction (f ⊎ g) : E → R définie par1
Pre

 
(f ⊎ g)(x) = inf f (y) + g(x−y) = inf{f (y) + g(z) : y + z = x}. (3.24)
y∈E

Voilà une opération bien singulière ! Observons d’abord qu’il s’agit de la fonction
marginale associée à la fonction définie sur E2 par ϕ(x, y) = f (y) + g(x−y), si bien
1
La notation f ⊎ g nous est propre, mais les autres notations ne sont guère stabilisées : on
trouve f ✷ g chez Rockafellar [535], f +
∨ g chez Hiriart-Urruty et Lemaréchal [332] et f ⊙ g
chez Borwein et Lewis [81]. Avec un peu de bonne volonté, le lecteur verra dans le symbole
⊎ le fait que l’épigraphe (symbole ∪) stricte de f ⊎ g est obtenu en sommant (symbole +)
ceux de f et g (proposition 3.35).
 m
3.4. Opérations 101

qu’elle hérite des propriétés des fonctions marginales. D’autre part, si la définition
de l’inf-convolution donnée ci-dessus peut paraître obscure, son expression en termes
d’épigraphe est particulièrement simple (la démonstration de la proposition ci-dessous
est proposée à l’exercice 3.6).

No
Proposition 3.35 Soient f et g deux fonctions E → R ∪ {+∞}. Alors

epis (f ⊎ g) = epis f + epis g. (3.25)

En particulier :
1) dom(f ⊎ g) = dom f + dom g,
2) commutativité : f ⊎ g = g ⊎ f ,
3) associativité : (f ⊎ g) ⊎ h = f ⊎ (g ⊎ h),
4) f ⊎ g est convexe si f et g sont convexes,
5) f ⊎ g ∈ Conv(E) si f et g ∈ Conv(E) et ont une minorante affine commune.

L’identité (3.25) portant sur les épigraphes strictes n’a pas lieu si l’on utilise les
épigraphes, bien que l’on ait toujours
nom
epi(f ⊎ g) ⊇ epi f + epi g.

Le problème vient du fait que la somme de deux fermés n’est pas nécessairement
un fermé, si bien que epi f + epi g n’est pas nécessairement un épigraphe ; il peut ne
pas contenir sa « frontière inférieure », comme dans l’exemple suivant : si f = I[0,1[ et
g = Id+I[0,+∞[ , alors (x, α) ∈ epi f +epi g si, et seulement si, x > 0, α > 0 et α > x−1,
si bien que epi f + epi g n’est pas l’épigraphe d’une fonction. Cependant, en prenant
α := f (y) + g(z) dans la définition (3.24) de f ⊎ g, on a (x, α) = (y, f (y)) + (z.g(z)),
si bien que
(f ⊎ g)(x) = inf{α : (x, α) ∈ epi f + epi g}. (3.26)
L’inf-convolution d’une fonction f (éventuellement
non convexe) avec la fonction quadratique q = 12 k · k2
a un effet régularisant sur certains points de non-diffé- r=2
r=1

rentiabilité de f . La figure ci-joint considère le cas de la

r = 0.5

fonction non convexe et non différentiable r = 0.2

r = 0.1

3
f : x ∈ R 7→ |x + 1| − x+ + (x − 1)+ ∈ R,
Pre

2
qui y est représentée par la courbe en trait plein. Les courbes en tirets sont les inf-
convolutions  r  r
x 7→ f ⊎ q (x) = inf f (y) + ky − xk2
2 y∈R 2
pour les valeurs de r = 0.1, r = 0.2, r = 0.5, r = 1 et r = 2. On voit en prenant
y = x dans l’infimum ci-dessus, que (f ⊎ 2r q)(x) ∈ [inf f, f (x)], lorsque r > 0 ; on
verra aussi au point 3 de la proposition 13.2 que (f ⊎ r2 q)(x) croît avec r > 0 ; ces
propriétés peuvent s’observer dans la figure. Cet effet régularisant sera examiné dans
le cas d’une fonction convexe f à la section 3.7.2.
 m
102 3. Fonctions convexes

3.4.5 Inf-image sous une application linéaire

Soient f : E → R une fonction et A : E → F une application linéaire. L’inf-image

de f sous A est la fonction (f ⊻ A) : F → R définie par2

(f ⊻ A)(y) = inf{f (x) : x ∈ E, Ax = y}. (3.27)

No
Il s’agit donc de la valeur minimale de f sur les sous-espaces affines {x ∈ E : Ax = y}
paramétrés par y. On appellera aussi cette fonction la fonction valeur associée au
problème d’optimisation inf{f (x) : Ax = b}, où b est donné dans F. C’est un des
intérêts de cette opération.
En fait, la fonction marginale et l’inf-convolution peuvent être vues comme des
l’inf-images :
la fonction marginale de ϕ : E × F → R n’est autre que ϕ ⊻ A, où A est la
projection de E × F sur E,
si f1 et f2 : E → R, alors
f1 ⊎ f2 = f ⊻ A, (3.28)
avec f : E × E → R : et A : E × E → E définies par
nom
f (x1 , x2 ) = f1 (x1 ) + f2 (x2 ) et A(x1 , x2 ) = x1 + x2 . (3.29)

Par ailleurs, l’inf-image apparaît dans la conjuguée de la pré-composition d’une fonc-

tion convexe avec une application linéaire (proposition 3.52).
Des conditions assurant la convexité de f ⊻ A sont données dans la proposition
suivante. La polyédricité de f ⊻ A est étudiée à la proposition 3.37. Des conditions
pour que f ⊻ A soit propre et fermée seront données à la proposition 3.50.

Proposition 3.36 Soient f : E → R une fonction convexe et A : E → F une

application linéaire. Alors f ⊻ A est convexe.

Démonstration. Soit B : E × R → F × R l’application linéaire définie par B(x, α) =

(Ax, α). Montrons que
B(epis f ) = epis (f ⊻ A).
En effet, (y, α) ∈ B(epis f ) si, et seulement si, il existe un x ∈ E tel que y = Ax et
Pre

f (x) < α, ce qui revient à dire que (f ⊻ A)(y) < α ou encore que (y, α) ∈ epis (f ⊻ A).
Alors la convexité de epis f entraîne celle de epis (f ⊻ A) et donc la convexité de
f ⊻ A. ✷
2
L’appellation « inf-image de f sous A » et la notation f ⊻ A nous sont propres. Rockafel-
lar [535] et Hiriart-Urruty et Lemaréchal [332] appellent simplement cette fonction l’image
de f sous A, donc sans faire mention de l’opération de minimalité qui intervient dans la
définition, ce qui nous a paru dommage. D’autre part, leur notation « Af » nous semble
être trop proche d’une composition (chez Rockafellar [535], « f A » est la composition f ◦A,
alors que « Af » désigne l’inf-image de f sous A). La singularité de cette opération nous
a semblé mériter une notation particulière suggérant l’opération de minimalité (symbole
∨) sur des sous-espaces affines (symbole ).
 m
3.4. Opérations 103

Proposition 3.37 (inf-image d’une fonction convexe polyédrique sous

une application linéaire) Soient f : E → R une fonction convexe polyédrique
et A : E → F une application linéaire. Alors f ⊻ A est convexe polyédrique et
l’infimum dans (3.27) est atteint lorsqu’il est fini.

No
Démonstration. On utilise l’application linéaire B : E × R → F × R de la démon-
stration de la proposition 3.36, définie par B(x, α) = (Ax, α). Montrons que

B(epi f ) = epi(f ⊻ A).

En effet,
(y, α) ∈ B(epi f )
⇐⇒ il existe un x ∈ E tel que y = Ax et f (x) 6 α,
⇐⇒ (f ⊻ A)(y) 6 α,
⇒ clair,
⇐ le problème inf{f (x) : Ax = y} définissant (f ⊻ A)(y) s’écrit aussi
inf{t : Ax = y, f (x) 6 t} ; ce dernier consiste à minimiser une fonc-
nom
tion linéaire sur un polyèdre convexe non vide (polyédricité de f et
(f ⊻ A)(y) < +∞) ; soit il est non borné, soit il a une solution (propo-
sition 2.19) ; dans chaque cas l’implication est claire ; le même raison-
nement montre que l’infimum dans la définition de l’inf-image est atteint
lorsqu’il est fini,
⇐⇒ (y, α) ∈ epi(f ⊻ A).
La polyédricité de f ⊻ A résulte maintenant du fait que epi f est convexe polyédrique,
donc aussi B(epi f ) = epi(f ⊻ A) (proposition 2.17). ✷

3.4.6 Enveloppe convexe N

Soit f : E → R une fonction, non nécessairement convexe. La plus grande fonction

convexe minorant f , si elle existe, a un épigraphe convexe qui contient celui de f . Il est
donc très tentant de définir cette minorante convexe maximale de f comme la fonction
dont l’épigraphe serait co epi f , l’enveloppe convexe de l’épigraphe de f . Cependant,
Pre

cet ensemble n’est pas nécessairement un épigraphe. Par exemple, si f : R → R est

définie par

 f
1 − x2 si −1 < x < 1
f (x) =
+∞ sinon,
co epi f

0
co epi f = {(x, α) ∈ R2 : −1 < x < 1, α > 0}, auquel il manque le segment du fond
]0, 1[ × {0} pour que ce soit un épigraphe. On s’y prend alors comme suit.
 m
104 3. Fonctions convexes

L’enveloppe convexe de f : E → R est la fonction notée co f , définie en x ∈ E par

(co f )(x) := inf{α ∈ R : (x, α) ∈ co epi f }.

Des conditions pour qu’il s’agisse de la plus grande minorante convexe de f sont
données dans le résultat qui suit.

No
Proposition 3.38

Démonstration. ✷

3.4.7 Adhérence

On peut construire d’autres fonctions à partir de l’épigraphe d’une fonction f :

E → R non nécessairement convexe, par exemple en prenant son adhérence. Comme
le montre la proposition suivante, par cette opération on obtient l’épigraphe d’une
fonction notée
f¯ : E → R.
nom
Cette fonction est appelée l’adhérence de f .

Proposition 3.39 (définition de l’adhérence) Soit f : E → R une fonction

(non nécessairement convexe). Alors adh(epi f ) est l’épigraphe d’une fonction
f¯ : E → R :
epi f¯ = epi f .

Démonstration. Il faut d’abord montrer que si (x, α) ∈ adh(epi f ) et β > α, alors

(x, β) ∈ adh(epi f ). Si (x, α) ∈ adh(epi f ), il existe une suite de couples (xk , αk ) ∈
epi f convergeant vers (x, α). Alors, pour k assez grand, αk 6 β et donc (xk , β) ∈ epi f .
En passant à la limite, on trouve que (x, β) ∈ adh(epi f ).
Il faut ensuite montrer que si (x, αk ) ∈ adh(epi f ) et αk ↓ α, on a (x, α) ∈
adh(epi f ). Ceci se déduit directement du fait que adh(epi f ) est fermé. ✷
Pre

Proposition 3.40 (propriétés de l’adhérence) Soit f : E → R une fonction

(non nécessairement convexe) et f¯ son adhérence. Alors
(i) f¯ est fermée et f¯ 6 f ,
(ii) pour tout x ∈ dom f¯,

f¯(x) = lim inf f (y) := lim inf f (y), (3.30)

y→x ε↓0 y∈B(x,ε)

(iii) en x ∈ dom f , f (x) = f¯(x) si, et seulement si, f est s.c.i. en x.

 m
3.4. Opérations 105

Démonstration. [(i)] L’épigraphe de f¯ étant fermé, f¯ est fermée. Par ailleurs f¯ 6 f

car epi f¯ ⊇ epi f .
[(ii)] Comme f¯ est fermée et f¯ 6 f , f¯(x) = lim inf y→x f¯(y) 6 lim inf y→x f (y).
Inversement, il existe une suite de couples (xk , αk ) ∈ epi f convergeant vers (x, f¯(x)).
Comme f (xk ) 6 αk , f¯(x) = limk αk > lim inf k f (xk ) > lim inf y→x f (y).
[(iii)] Si f (x) = f¯(x), on voit par (3.30) que f est s.c.i. en x. Inversement, si f

No
est s.c.i. en x, f (x) 6 lim inf y→x f (y) = f¯(x) [par (3.30)] 6 f (x) [car f¯ 6 f ], donc
f (x) = f¯(x). ✷

Proposition 3.41 (enveloppe supérieure de minorantes affines) Soit f ∈

Conv(E). Alors f¯ est l’enveloppe supérieure des minorantes affines de f .

Démonstration. Soit {ai }i∈I la famille des minorantes affines de f . On cherche à

montrer que f¯ = supi∈I ai ou en termes d’épigraphe :
\
epi f¯ = epi ai .
i∈I
nom
L’épigraphe de f étant un convexe, le corollaire 2.36 nous apprend que epi f¯ =
adh(epi f ) est l’intersection de tous les demi-espaces fermés de E × R contenant
epi f . Comme l’épigraphe d’un ai est un demi-espace fermé contenant epi f , on a
déjà l’inclusion epi f¯ ⊆ ∩i∈I epi ai . Pour montrer l’inclusion inverse, il s’agit d’écrire
les demi-espaces fermés contenant epi f au moyen des épigraphes des ai .
Un demi-espace fermé de E × R est défini par un triplet (ξ, τ, t) ∈ E × R × R ; on
le note H − (ξ, τ, t) := {(x, α) : hξ, xi + τ α 6 t}. S’il contient epi f il faut que l’on ait

∀ (x, α) ∈ epi f : hξ, xi + τ α 6 t.

On a nécessairement τ 6 0 (on peut prendre α aussi grand que l’on veut dans
l’inégalité ci-dessus). Si τ < 0, H − (ξ, τ, t) est l’épigraphe de la minorante affine de f
suivante x 7→ h−ξ/τ, xi + t/τ (prendre α = f (x) ci-dessus).
Que faire des demi-espaces fermés de la forme H − (ξ, 0, t) ? Par hypothèse, f ∈
Conv(E) ; elle a donc une minorante affine (proposition 3.6), dont l’épigraphe est un
certain H − (ξ0 , τ0 , t0 ), avec τ0 < 0. Si l’on établit que
\
Pre

H − (ξ, 0, t) ∩ H − (ξ0 , τ0 , t0 ) = H − (ξ0 + ρξ, τ0 , t0 + ρt),

ρ>0

on aura terminé la démonstration, puisque l’on aura exprimé l’intersection des demi-
espaces fermés contenant epi f comme l’intersection des epi ai . Cette identité résulte
en fait de l’équivalence triviale

hξ, xi 6 t et hξ0 , xi + τ0 α 6 t0
⇐⇒ ∀ρ > 0 : hξ0 + ρξ, xi + τ0 α 6 t0 + ρt. ✷
 m
106 3. Fonctions convexes

3.5 Conjugaison

Soit f : E → R une fonction, non nécessairement convexe. Nous allons dans cette
section lui associer une autre fonction f ∗ : E → R, appelée conjuguée de Fenchel
de f . Elle est construite explicitement à partir de f . Cette construction peut paraître
abstraite et arbitraire au premier abord, mais elle est utile à plus d’un titre :

No
nous verrons à la section 3.5.2 qu’en réitérant le processus de conjugaison, on
dispose d’un moyen analytique de convexifier f ,
la conjuguée de Fenchel peut aussi être utilisée comme outil intermédiaire dans
le calcul de sous-gradient, un concept généralisant la notion de gradient pour les
fonctions convexes non différentiables, que nous verrons à la section 3.6,
enfin la conjuguée de Fenchel permet aussi d’introduire un problème d’optimisa-
tion dual d’un autre problème d’optimisation (section 14.2).
On supposera dans cette section que E est un espace euclidien, dont le produit scalaire
est noté h·, ·i.

3.5.1 Conjuguée
nom
Comme nous le signalions ci-dessus, la notion de fonction conjuguée intervient dans
la définition du sous-différentiel d’une fonction convexe f et c’est par cette notion de
sous-différentiel que nous allons motiver l’introduction de la fonction conjuguée.
On verra que le sous-différentiel ∂f (x) de f en x est l’ensemble des pentes x∗ des
minorantes affines de f exactes en x. Il définit une multifonction

∂f : x ∈ E 7→ ∂f (x) ⊆ E.

Il n’est pas toujours aisé d’expliciter cette application car, pour x ∈ E, il n’est pas
nécessairement simple de déterminer toutes les minorantes affines de f exactes en x.
Que l’on songe par exemple à la fonction valeur-propre-maximale λmax qui à une
matrice A ∈ S n fait correspondre sa valeur propre maximale λmax (A). Cette fonction
est convexe (exercice 3.32), mais quelles sont les minorantes affines de λmax qui sont
exactes en une matrice A ∈ S n donnée ? Il est parfois plus facile de déterminer la
multifonction réciproque de ∂f , à savoir

∂f −1 : x∗ ∈ E 7→ {x ∈ E : x∗ ∈ ∂f (x)}.
Pre

De ce point de vue, pour une pente x∗ ∈ E donnée, on cherche les points x ∈ E

tels que f a une minorante affine de pente x∗ qui est exacte en x. Pour déterminer
ces points x, on s’y prend de la manière suivante ; c’est dans ce calcul qu’apparaît la
fonction conjuguée.
Une fonction affine de pente x∗ est une application de la forme

ax∗ ,α : E → R : x 7→ ax∗ ,α (x) = hx∗ , xi − α,

où α ∈ R est l’opposé de sa valeur en zéro. Pour que cette fonction affine minore f et
soit exacte en certains points, on cherche à prendre α le plus petit possible (donc −α
le plus grand possible) tout en conservant l’inégalité de minoration ax∗ ,α 6 f . Les
 m
3.5. Conjugaison 107
R

f
minorante affine maximale
de pente x∗ , exacte en x

No
−f ∗ (x∗ ) pente x∗

0 x E

Fig. 3.6. Interprétation de f ∗ (x∗ )

points où f et cette minorante affine maximale ax∗ ,α prennent les mêmes valeurs
sont les points x ∈ ∂f −1 (x∗ ) recherchés. La démarche est illustrée à la figure 3.6. De
manière plus explicite, on cherche le plus petit α ∈ R tel que
 
ax∗ ,α 6 f ou ∀ x ∈ E : hx∗ , xi − α 6 f (x) (3.31)
nom
 
ou ∀ x ∈ E : hx∗ , xi − f (x) 6 α .

On voit clairement que la plus petite valeur de α est donnée par

 
f ∗ (x∗ ) := sup hx∗ , xi − f (x) . (3.32)
x∈E

C’est la valeur de la conjuguée de f en x∗ .

Définition 3.42 Soit f : E → R une fonction (non nécessairement convexe). Sa

fonction conjuguée f ∗ : E → R est la fonction prenant en x∗ ∈ E la valeur donnée par
(3.32). L’application f 7→ f ∗ est appelée transformation de Legendre-Fenchel. ✷
Revenons au problème que nous nous posions au début de ce paragraphe : si x est
solution du problème en (3.32), alors

∀y ∈ E : hx∗ , xi − f (x) > hx∗ , yi − f (y) (3.33)

Pre

ou encore (on vérifiera l’équivalence même lorsque f peut prendre des valeurs infinies)

∀y ∈ E : f (y) > f (x) + hx∗ , y − xi, (3.34)

ce qui montre que y 7→ f (x) + hx∗ , y − xi est une minorante affine de f , exacte
en x. Dès lors, les sous-différentiels de f aux points-solutions du problème en (3.32)
contiennent x∗ .
L’expression (3.32) de la conjuguée et (3.31) montrent que l’on a une relation très
simple entre les minorantes affines de f et les éléments de l’épigraphe de f ∗ :

ax∗ ,α est une minorante affine de f ⇐⇒ (x∗ , α) ∈ epi f ∗ . (3.35)

 m
108 3. Fonctions convexes

Comme une fonction est entièrement spécifiée par son épigraphe, on peut dire que la
conjuguée f ∗ de f est la fonction qui décrit toutes les minorantes affines de f .
La convexité de f ∗ mise en évidence par la proposition ci-dessous est remarquable ;
on se rappelle en effet que f n’est, elle, pas nécessairement convexe. On note f 6≡ −∞
(resp. f 6≡ +∞) pour signifier que f n’est pas identiquement égale à −∞ (resp. +∞)
et on note f > −∞ (resp. f < +∞) pour exprimer le fait que f ne prend pas la

No
valeur −∞ (resp. +∞).

Proposition 3.43 (conjuguée convexe fermée) La fonction conjuguée f ∗

d’une fonction f : E → R est convexe et fermée. Par ailleurs, on a les équivalences
suivantes

f 6≡ +∞ ⇐⇒ f ∗ > −∞ ⇐⇒ f ∗ 6≡ −∞, (3.36)

f a une minorante affine ⇐⇒ f ∗ 6≡ +∞, (3.37)
f propre avec minorante affine ⇐⇒ f ∗ propre ⇐⇒ f ∗ ∈ Conv(E). (3.38)

Démonstration. Certains arguments seront donnés plusieurs fois, de manière à

nom
garder une démonstrstion structurée.
[f ∗ est convexe fermée] Il y a trois cas possibles.
Si f prend la valeur −∞, alors f ∗ ≡ +∞ (par la définition de f ∗ ), une fonction
convexe et fermée (l’épigraphe de f ∗ est vide, donc convexe et fermé).
Si f ≡ +∞, alors f ∗ ≡ −∞ (par la définition de f ∗ ), une fonction convexe et
fermée (l’épigraphe de f ∗ est égal à E × R, donc convexe et fermé).
Si f est propre, f ∗ s’écrit comme le supremum de la famille indicée par x ∈ dom f
(non vide) des fonctions affines (donc convexes et fermées) x∗ 7→ hx∗ , xi − f (x).
On en déduit que f ∗ est elle-même convexe et fermée (proposition 3.33).
[(3.36)] Si f 6≡ +∞, il existe un x0 ∈ E tel que f (x0 ) < +∞ ; dans ce cas, quel
que soit x∗ ∈ E, f ∗ (x∗ ) > hx∗ , x0 i − f (x0 ) > −∞, si bien que f ∗ > −∞. Évidemment,
f ∗ > −∞ implique que f ∗ 6≡ −∞. Enfin, si f ≡ +∞, alors f ∗ ≡ −∞.
[(3.37)] Soit x 7→ hx∗0 , xi + α0 une minorante affine de f , avec x∗0 ∈ E et α0 ∈ R ;
alors, pour tout x ∈ E, f (x) > hx∗0 , xi + α0 ; on en déduit que −α0 > sup{hx∗0 , xi −
f (x) : x ∈ E} = f ∗ (x∗0 ) et donc que f ∗ 6≡ +∞. La réciproque est obtenue par le
raisonnement inverse : si f ∗ 6≡ +∞, il existe x∗0 ∈ E et α0 ∈ R tels que f ∗ (x∗0 ) 6 −α0 ;
alors, pour tout x ∈ E, hx∗0 , xi − f (x) 6 −α0 , si bien que x 7→ hx∗0 , xi + α0 est une
Pre

minorante affine de f .
[(3.38)] Par (3.36) et (3.37), f est propre et a une minorante affine si, et seulement
si, f ∗ est propre. Enfin, il revient au même de dire que f ∗ est propre et que f ∗ ∈
Conv(E), parce que f ∗ est toujours convexe et fermée. ✷

3.5.2 Biconjuguée

On peut bien sûr appliquer la transformation de Legendre-Fenchel à la fonction

conjuguée f ∗ : E → R ; on obtient ainsi la biconjuguée de f , notée f ∗∗ .
 m
3.5. Conjugaison 109

Définition 3.44 Soit f : E → R une fonction (non nécessairement convexe) et f ∗ :

E → R sa conjuguée. La fonction biconjuguée de f est la fonction f ∗∗ : E → R définie
en x ∈ E par
 
f ∗∗ (x) = sup hx∗ , xi − f ∗ (x∗ ) .
x∗ ∈E

No
✷

Proposition 3.45 (biconjuguée convexe fermée) La fonction biconjuguée

f ∗∗ d’une fonction f : E → R est convexe et fermée. De plus

f est propre et a une minorante affine ⇐⇒ f ∗∗ ∈ Conv(E). (3.39)

Démonstration. La biconjuguée est convexe et fermée en tant que conjuguée (propo-

sition 3.43).
Si f est propre et a une minorante affine, alors f ∗ est propre par (3.38). Mais f ∗
a aussi une minorante affine puisque, avec x0 ∈ dom f 6= ∅, on a
nom
∀ x∗ ∈ E : f ∗ (x∗ ) > hx∗ , x0 i − f (x0 ).

Dès lors, f ∗∗ ∈ Conv(E) par (3.38) appliqué à f ∗ au lieu de f .

Réciproquement, si f ∗∗ ∈ Conv(E), alors f ∗ est propre par (3.38) appliqué à f ∗ .
On en déduit que f est propre et a une minorante affine, à nouveau par (3.38). ✷

Si l’argument x∗ de f ∗ est une forme linéaire (identifiée à un élément de E au

moyen du produit scalaire h·, ·i), l’argument x de f ∗∗ est dans l’espace de départ E.
On peut alors se demander s’il y a un lien entre f et f ∗∗ . La proposition suivante
examine cette question.

Proposition 3.46 (enveloppe convexe fermée) Soit f : E → R une fonction

propre ayant une minorante affine. Alors
1) f ∗∗ est l’enveloppe supérieure des minorantes affines de f ,
2) f ∈ Conv(E) =⇒ f ∗∗ = f¯ (l’adhérence de f ),
3) f ∈ Conv(E) ⇐⇒ f ∗∗ = f ,
4) la transformation de Legendre-Fenchel f 7→ f ∗ est une bijection sur l’ensem-
Pre

ble Conv(E).

Démonstration. 1) Soit x ∈ E. La valeur en x de l’enveloppe supérieure des mino-

rantes affines de f s’écrit
 m
110 3. Fonctions convexes
   
sup hx∗ , xi − α = sup sup hx∗ , xi − α
x∗ ∈E, α∈R x∗ ∈E α∈R
hx∗ ,yi−α6f (y), ∀ y∈E hx∗ ,yi−α6f (y), ∀ y∈E
 
= sup sup hx∗ , xi − α
x∗ ∈E α=f ∗ (x∗ )
 

No
= sup hx∗ , xi − f ∗ (x∗ )
x∗ ∈E
= f ∗∗ (x).

2) Si f ∈ Conv(E), f¯ est l’enveloppe supérieure des minorante affines de f (propo-

sition 3.41), c’est-à-dire f ∗∗ d’après le point 1.
3) Si f ∈ Conv(E), epi f = adh(epi f ) [car epi f est fermé] = epi f¯ [par définition
de f¯] = epi f ∗∗ [par le point 2, donc f = f ∗∗ . Inversement, l’égalité f ∗∗ = f implique
que f est convexe et fermée (car f ∗∗ ∈ Conv(E)).
4) D’après la proposition 3.43, la transformation de conjugaison C : f 7→ f ∗ est bien
définie sur Conv(E) et est de toute façon à valeurs dans Conv(E). Elle est injective,
car si f1 et f2 ∈ Conv(E) sont telles que f1∗ = f2∗ , on a f1∗∗ = f2∗∗ et donc f1 = f2
d’après le point 3. Elle est surjective, car si g ∈ Conv(E), on a C(g ∗ ) = g ∗∗ = g d’après
le point 3 ; donc g est l’image de g ∗ par C. ✷
nom
Ce résultat permet de comparer les valeurs de f ∗∗ et de f .

Corollaire 3.47 (comparaison de f ∗∗ et f ) Quelle que soit f : E → R, on a

f ∗∗ 6 f.

Si f ∈ Conv(E) et x ∈ dom f , alors

f ∗∗ (x) = f (x) ⇐⇒ f est s.c.i. en x.

Démonstration. Si f ≡ +∞, on a certainement f ∗∗ 6 f . Si f n’a pas de minorante

affine, f ∗ ≡ +∞ par (3.37), puis f ∗∗ ≡ −∞ 6 f . Dans les autres cas, f ∗∗ est
l’enveloppe supérieure des minorantes affines de f (point 1 de la proposition 3.46), si
bien que f ∗∗ 6 f (quel que soit x ∈ E, f ∗∗ (x) est le supremum de valeurs plus petites
que f (x)).
Pre

D’après la proposition 3.40, lorsque x ∈ dom f , on a f (x) = f¯(x) si, et seulement

si, f est s.c.i. en x. Le résultat est alors une conséquence du fait que f¯ = f ∗∗ lorsque
f ∈ Conv(E) (point 2 de la proposition 3.46). ✷

D’après la proposition 3.46, il est naturel d’appeler aussi la biconjuguée f ∗∗ ,

l’enveloppe convexe fermée de f . La figure 3.7 donne la biconjuguée de la fonction
représentée à la figure 3.6.
La proposition suivante montre qu’il ne sert à rien de réitérer le processus de
conjugaison au-delà du second ordre : la tri-conjuguée se confond avec la conjuguée.
 m
3.5. Conjugaison 111
R

No
f ∗∗

0 E

Fig. 3.7. Fonction biconjuguée f ∗∗ (en trait plein) de la fonction f de la figure 3.6 (en tirets)

Proposition 3.48 (triconjuguée) Soit f : E → R ∪ {+∞} une fonction propre

ayant une minorante affine. Alors (f ∗∗ )∗ = f ∗ .
nom
Démonstration. D’après le corollaire 3.47, f ∗∗ 6 f et donc (f ∗∗ )∗ > f ∗ (exer-
cice 3.16-(3)). Inversement, pour x∗ fixé, f ∗∗ (x) > hx∗ , xi − f ∗ (x∗ ) pour tout x ∈ E,
et donc  
(f ∗∗ )∗ (x∗ ) = sup hx∗ , xi − f ∗∗ (x) 6 f ∗ (x∗ ).
x∈E ✷

3.5.3 Règles de calcul

Inf-image sous une application linéaire

Rappelons la définition de l’inf-image f ⊻ A d’une fonction f sous une application
linéaire A, introduite à la section 3.2. On se donne deux espaces euclidiens E et F (on
aura besoin ici d’un produit scalaire sur E et F, alors que cette structure n’est pas
nécessaire dans la définition de f ⊻ A), une fonction f : E → R et une application
linéaire A : E → F. Alors f ⊻ A : F → R est définie en y ∈ F par

(f ⊻ A)(y) = inf f (x). (3.40)

Pre

x∈E
Ax=y

Nous donnons à la proposition 3.49 l’expression de la conjuguée de f ⊻ A. La propo-

sition 3.50 énonce des conditions assurant que f ⊻ A est dans Conv(F) ou Conv(F).

Proposition 3.49 (conjuguée de f ⊻ A) Dans les conditions définies ci-des-

sus, on a
(f ⊻ A)∗ = f ∗ ◦ A∗ . (3.41)
 m
112 3. Fonctions convexes

De plus, si f est propre et a une minorante affine et si l’application linéaire A

vérifie
R(A∗ ) ∩ dom f ∗ 6= ∅,
alors f ⊻ A est propre et a une minorante affine.

No
Démonstration. Pour y ∗ ∈ F, on trouve
 

(f ⊻ A)∗ (y ∗ ) = sup hy ∗ , yi − inf f (x)

y∈F x∈E
Ax=y
 
= sup hy ∗ , yi − f (x)
(x,y)∈E×F
Ax=y
 
= sup hy ∗ , Axi − f (x)
x∈E
 
= sup hA∗ y ∗ , xi − f (x)
x∈E
nom
= f ∗ (A∗ y ∗ ).

Supposons à présent que f est propre et a une minorante affine et que R(A∗ ) ∩
dom f ∗ 6= ∅. Alors, clairement, f ⊻A 6≡ +∞ (elle prend une valeur finie sur A(dom f ),
qui n’est pas vide). D’autre part, par hypothèse, il existe un x∗0 := A∗ y0∗ ∈ dom f ∗ .
Alors l’inégalité +∞ > f ∗ (x∗0 ) > hx∗0 , xi − f (x) valable pour tout x ∈ E conduit à

+∞ > f (x) > hy0∗ , Axi − (f ∗ ◦ A∗ )(y0∗ ), pour tout x ∈ dom f .

Évidemment (f ⊻ A)(y) = +∞ si y ∈ / A(dom f ). Soit à présent y ∈ A(dom f ). En

prenant l’infimum ci-dessus pour les x ∈ dom f vérifiant Ax = y, on trouve

(f ⊻ A)(y) > hy0∗ , yi − (f ∗ ◦ A∗ )(y0∗ ), pour tout y ∈ F.

Dès lors f ⊻ A a une minorante affine.

Proposition 3.50 (régularité de f ⊻A) Soient E et F deux espaces euclidiens,

f : E → R une fonction et A : E → F une application linéaire.
Pre

1) Si f ∈ Conv(E) et si A vérifie R(A∗ ) ∩ dom f ∗ 6= ∅, alors f ⊻ A ∈ Conv(F).

2) Si f ∈ Conv(E) et si A vérifie R(A∗ )∩(dom f ∗ )−◦
6= ∅, alors f ⊻A ∈ Conv(F).
De plus, l’infimum dans (3.40) est atteint lorsqu’il est fini.

Démonstration. 1) Comme f ∈ Conv(E), f ⊻ A est convexe (proposition 3.36).

D’autre part, comme f : E → R ∪ {+∞} est propre avec une minorante affine (propo-
sition 3.6) et que R(A∗ )∩dom f ∗ 6= ∅, f ⊻A est également propre avec une minorante
affine (proposition 3.49). Donc f ⊻ A ∈ Conv(F).
2) Pour montrer que f ⊻ A est fermée, on suppose que l’on a des suites {yk } ⊆ F
et {αk } ⊆ R telles que
 m
3.5. Conjugaison 113

(f ⊻ A)(yk ) 6 αk , yk → y et αk → α.
Il suffit de montrer que (f ⊻ A)(y) 6 α. D’après la définition de f ⊻ A, on peut trouver
une suite {εk } ↓ 0 et une suite {xk } ⊆ E telles que
f (xk ) 6 αk + εk , Axk = yk , yk → y et αk → α.

No
Il s’agit de passer à la limite dans ces relations.
La suite {xk } n’étant pas nécessairement bornée, on cherche à construire une
autre suite {x̄k } ⊆ E, bornée elle, qui laisse inchangés f et A. Si l’on se donne
x∗1 ∈ R(A∗ ) ∩ dom f ∗ , qui est non vide par hypothèse, il revient au même d’imposer
f (x̄k ) − hx∗1 , x̄k i = f (xk ) − hx∗1 , xk i et Ax̄k = Axk ,
puisqu’alors f (x̄k ) = f (xk ) (en effet x∗1 ∈ R(A∗ ) et Ax̄k = Axk impliquent que
hx∗1 , x̄k i = hx∗1 , xk i). Remarquons que f (·) − hx∗1 , ·i = f ∗∗ (·) − hx∗1 , ·i n’est autre
que la conjuguée ϕ∗ de la fonction ϕ ∈ Conv(E) définie par ϕ(x∗ ) := f ∗ (x∗ + x∗1 ).
Comme 0 ∈ dom ϕ, E0 := aff dom ϕ est un sous-espace vectoriel. Soit x̄k la projection
orthogonale de xk sur E0 − R(A∗ ). D’une part, xk − x̄k ∈ R(A∗ )⊥ = N (A), si bien
que A(xk ) = A(x̄k ). D’autre part, xk − x̄k ∈ E⊥ 0 , si bien que

ϕ∗ (xk ) = sup hx∗ , xk i − ϕ(x∗ ) = sup hx∗ , x̄k i − ϕ(x∗ ) = ϕ∗ (x̄k ).

x∗ ∈E0 x∗ ∈E0
nom
On a donc
f (x̄k ) 6 αk + εk , Ax̄k = yk , yk → y et αk → α.
Si {x̄k } est bornée, on peut en extraire une sous-suite convergente, disons vers x̄.
Par semi-continuité inférieure de f , on a f (x̄) 6 lim inf f (x̄k ). En passant à la limite
ci-dessus, on a
f (x̄) 6 α et Ax̄ = y.
Donc (f ⊻ A)(y) 6 α et (f ⊻ A) est fermée.
Remarquons que si l’on prend ci-dessus yk = y et αk = (f ⊻ A)(y), pour tout k, la
suite {xk } devient une suite minimisante du problème de minimisation dans (3.40).
Le raisonnement ci-dessus montre alors que ce problème a une solution.
Il reste donc à montrer que {x̄k } est bornée. Observons que x̄k ∈ E1 := E0 −
R(A∗ ) = vect(dom ϕ − R(A∗ )). Dès lors, pour montrer que {x̄k } est bornée, il suffit
de monter que, quel que soit z ∈ E1 , {hz, x̄k i} est bornée (par l’absurde : on prend
pour z, un point d’adhérence de {x̄k /kx̄k k}). Soit donc z ∈ E1 . Par hypothèse, 0 ∈
(dom f ∗ )−
◦
− R(A∗ ) = (dom f ∗ − R(A∗ ))−
◦
= (dom ϕ − R(A∗ ))− ◦
, puisque dom f ∗ =
∗ ∗ ∗ ∗
dom ϕ − x1 et que x1 ∈ R(A ). Donc tz ∈ dom ϕ − R(A ) pour t > 0 assez petit :
Pre

il existe x∗ ∈ dom ϕ et y ∗ ∈ F tels que tz = x∗ − A∗ y ∗ . En introduisant v ∗ tel que

x∗1 = A∗ v ∗ , on trouve
thz, x̄k i = hx∗ , x̄k i − hA∗ y ∗ , x̄k i
6 ϕ(x∗ ) + ϕ∗ (x̄k ) − hy ∗ , Ax̄k i
= ϕ(x∗ ) + ϕ∗ (xk ) − hy ∗ , Axk i
= ϕ(x∗ ) + f (xk ) − hy ∗ + v ∗ , Axk i
6 ϕ(x∗ ) + αk + εk − hy ∗ + v ∗ , yk i,
dont le membre de droite est borné (il converge vers ϕ(x∗ ) + α − hy ∗ + v ∗ , yi ∈ R). ✷
 m
114 3. Fonctions convexes

Pré-composition avec une application linéaire

D’après la proposition 3.31, si A : E → F est une application linéaire et si g ∈
Conv(F) vérifie R(A)∩dom g 6= ∅, alors g ◦A ∈ Conv(E), si bien que (g ◦A)∗∗ = g ◦A.
On s’intéresse ci-dessous au calcul de la biconjuguée (g ◦ A)∗∗ lorsque la fonction
g ∈ Conv(F) n’est pas nécessairement fermée, mais vérifie une condition plus forte

No
que la condition minimale R(A) ∩ dom g 6= ∅ assurant la propreté de g ◦ A.

Proposition 3.51 (biconjuguée de g ◦ A) Soient E et F deux espaces vecto-

riels, A : E → F une application linéaire et g ∈ Conv(F) une fonction vérifiant
R(A) ∩ (dom g)−◦
6= ∅. Alors g ◦ A ∈ Conv(E) et

(g ◦ A)∗∗ = g ∗∗ ◦ A.

Démonstration. On a déjà vu que g ◦ A ∈ Conv(E). Comme dans la démonstration

de la proposition 3.31, on introduit l’application linéaire

B : E × R → F × R : (x, α) 7→ (Ax, α)
nom
qui permet d’écrire epi(h ◦ A) = B −1 (epi h), quelle que soit la fonction h : F → R.
D’après (3.3) et grâce à la condition de propreté renforcée R(A) ∩ (dom g)− ◦
6= ∅ :
 
B −1 ((epi g)−
◦
) = B −1 {(y, α) : y ∈ (dom g)− ◦
, g(y) < α}
= {(x, α) : Ax ∈ (dom g)−
◦
, g(Ax) < α}
6 = ∅.

Ensuite

epi((g ◦ A)∗∗ ) = epi(g ◦ A), [proposition 3.46, point 2]

= B −1 (epi g)
= B −1 (epi g), [proposition 2.16 et B −1 ((epi g)−
◦
) 6= ∅]
= B −1 (epi g ∗∗ )
= epi(g ∗∗ ◦ A).
Pre

On a donc bien établi que (g ◦ A)∗∗ = g ∗∗ ◦ A. ✷

Proposition 3.52 (conjuguée de g ◦A) Soient E et F deux espaces euclidiens,

A : E → F une application linéaire et g ∈ Conv(F).
1) Si g ∈ Conv(F) et si R(A) ∩ dom g 6= ∅, alors g ◦ A ∈ Conv(E) et

(g ◦ A)∗ = (g ∗ ⊻ A∗ )∗∗ . (3.42)

 m
3.5. Conjugaison 115

2) Si g est convexe polyédrique et si R(A) ∩ dom g 6= ∅, alors

(g ◦ A)∗ = g ∗ ⊻ A∗ . (3.43)

De plus, l’infimum dans la définition de (g ∗ ⊻ A∗ )(x∗ ) est atteint s’il est fini.

No
3) Si g ∈ Conv(F) et si R(A) ∩ (dom g)− ◦
6= ∅, alors g ◦ A ∈ Conv(E) et (3.43)
a lieu. De plus, l’infimum dans la définition de (g ∗ ⊻ A∗ )(x∗ ) est atteint s’il
est fini.

Démonstration. 1) D’après la proposition 3.31, g ◦ A ∈ Conv(E). On applique

alors la proposition 3.49 avec f := g ∗ et A := A∗ (ses hypothèses sont vérifiées, car
g ∗∗ = g) : (3.41) donne (g ∗ ⊻ A∗ )∗ = g ◦ A, qui par conjugaison conduit à (3.42).
2) Si g est convexe polyédrique et si R(A) ∩ dom g 6= ∅, alors, d’après le point 1,
on a (3.42). Mais g ∗ est convexe polyédrique (exercice 3.15) et donc aussi g ∗ ⊻ A∗
(proposition 3.37), qui est donc fermée. Alors (3.42) donne (3.43). La proposition 3.37
nous apprend aussi que l’infimum dans la définition de (g ∗ ⊻ A∗ )(x∗ ) est atteint s’il
est fini.
3) D’après la proposition 3.31, g ◦ A ∈ Conv(E). On peut appliquer le point 1 avec
nom
g := g ∗∗ ∈ Conv(F), car R(A) ∩ dom g ∗∗ ⊇ R(A) ∩ (dom g ∗∗ )− ◦
= R(A) ∩ (dom g)− ◦

[selon l’exercice 3.18 (2)] 6= ∅ [par hypothèse]. Ceci donne

(g ∗∗ ◦ A)∗ = (g ∗ ⊻ A∗ )∗∗ .

D’après la proposition 3.51 et grâce à l’hypothèse R(A) ∩ (dom g)− ◦

6= ∅, g ∗∗ ◦ A =
∗∗ ∗∗ ∗ ∗
(g ◦A) , si bien que (g ◦A) = (g ◦A) . D’autre part, d’après la proposition 3.50 (2)
avec f := g ∗ et A := A∗ et grâce au fait vu ci-dessus que R(A) ∩ dom g ∗∗ 6= ∅, on
voit que g ∗ ⊻ A∗ est fermée (donc (g ∗ ⊻ A∗ )∗∗ = g ∗ ⊻ A∗ ) et que l’infimum définissant
g ∗ ⊻ A∗ est atteint lorsqu’il est fini. ✷

Inf-convolution
Une inf-convolution peut se voir comme une inf-image sous une application linéaire,
voir (3.28)–(3.29). En appliquant la proposition 3.49 à cette inf-image, on obtient le
résultat suivant.
Pre

Proposition 3.53 (conjuguée de l’inf-convolution) Soient f1 , . . . , fp : E →

R ∪ {+∞} des fonctions propres telles que
\
dom fi∗ 6= ∅.
16i6p

Alors f1 ⊎ · · · ⊎ fp est propre avec une minorante affine et

(f1 ⊎ · · · ⊎ fp )∗ = f1∗ + · · · + fp∗ .

 m
116 3. Fonctions convexes

Démonstration. On applique donc la proposition 3.49. On sait que f1 ⊎ · · · ⊎ fp =

f ⊻ A, avec f : Ep → R ∪ {+∞} et A : Ep → E définies par

f (x1 , . . . , xp ) = f1 (x1 ) + · · · + fp (xp ) et A(x1 , . . . , xp ) = x1 + · · · + xp .

Exiger la propreté de f revient à demander celle des fi . D’autre part, f a une mino-

No
rante affine si, et seulement si, les fi ont une minorante affine. On peut alors calculer
f ∗ et A∗ (la somme des fi∗ (x∗i ) ci-dessous peut valoir +∞, mais on est sûr de ne pas
additionner +∞ et −∞) :

f ∗ (x∗1 , . . . , x∗p ) = f1∗ (x∗1 ) + · · · + fp∗ (x∗p ) et A∗ (x∗ ) = (x∗ , . . . , x∗ ).

Enfin la condition R(A∗ ) ∩ dom f ∗ 6= ∅ s’écrit ∩i dom fi∗ 6= ∅. En conclusion, f1 ⊎

· · · ⊎ fp est propre avec une minorante affine et (f1 ⊎ · · · ⊎ fp )∗ = (f ⊻ A)∗ = f ∗ ◦ A∗ =
f1∗ + · · · + fp∗ . ✷

Somme
nom
Proposition 3.54 (conjuguée d’une somme) Soient f1 , . . . , fp : E → R ∪
{+∞} des fonctions.
1) Si les fi ∈ Conv(E) et ∩i dom fi 6= ∅, alors f1 + · · · + fp ∈ Conv(E),
f1∗ ⊎ · · · ⊎ fp∗ ∈ Conv(E) et

(f1 + · · · + fp )∗ = (f1∗ ⊎ · · · ⊎ fp∗ )∗∗ . (3.44)

2) Si les fi ∈ Conv(E) et ∩i (dom fi )− ◦

6= ∅ (on peut remplacer (dom fi )−
◦
par
dom fi dans cette condition si fi est polyédrique), alors f1 + · · · + fp ∈
Conv(E), f1∗ ⊎ · · · ⊎ fp∗ ∈ Conv(E) et

(f1 + · · · + fp )∗ = f1∗ ⊎ · · · ⊎ fp∗ . (3.45)

De plus, l’infimum dans la définition de (f1∗ ⊎· · ·⊎fp∗ )(x∗ ) est atteint lorsqu’il
est fini.

Démonstration. 1) Supposons que les fi ∈ Conv(E) et que ∩i dom fi 6= ∅. Les

Pre

fonctions fi∗ vérifient bien les hypothèses demandées sur les fi dans la proposition 3.53.
On en déduit que f1∗ ⊎ · · · ⊎ fp∗ est propre avec une minorante affine et que (f1∗ ⊎
· · · ⊎ fp∗ )∗ = f1 + · · · + fp . Donc f1 + · · · + fp ∈ Conv(E) (proposition 3.43) et
f1∗ ⊎ · · · ⊎ fp∗ ∈ Conv(E) (f1∗ ⊎ · · · ⊎ fp∗ est aussi convexe par la proposition 3.35). En
prenant la conjuguée de la dernière identité, on obtient (3.44).
2a) Si toutes les fonctions fi sont convexes polyédriques et que l’on a seulement
∩i dom fi 6= ∅, le point 1 et l’exercice 3.15 donnent le résultat énoncé au point 2.
En effet, dans ce cas, les fi ∈ Conv(E) comme fonctions convexes polyédriques, les
fi∗ ∈ Conv(E) comme conjuguées de fonctions convexes polyédriques et f1∗ ⊎ · · · ⊎ fp∗ ∈
Conv(E) comme inf-convolution de fonctions convexes polyédriques. De plus l’infimum
dans la définition de (f1∗ ⊎ · · · ⊎ fp∗ )(x∗ ) est atteint lorsqu’il est fini.
 m
3.5. Conjugaison 117

2b) Supposons à présent que les fi ∈ Conv(E) et que ∩i (dom fi )− ◦

6= ∅. On
se ramène à la proposition 3.52 (point 2) en écrivant f1 + · · · + fp = g ◦ A, avec
g ∈ Conv(Ep ) et A : E → Ep linéaire, définies par
g(x1 , . . . , xp ) = f1 (x1 ) + · · · + fp (xp ) et A(x) = (x, . . . , x).

No
Il faut vérifier que R(A) ∩ (dom g)−◦
6= ∅. On a R(A) = {(x, . . . , x) : x ∈ E} et
(dom g) = (dom f1 ×· · ·×dom fp ) = (dom f1 )−
−◦ −
◦ ◦
×· · ·×(dom fp )−◦
(proposition 2.16),
si bien que R(A) ∩ (dom g) = {(x, . . . , x) : x ∈ (dom f1 ) ∩ · · · ∩ (dom fp )−
−
◦ −
◦ ◦
}, qui est
non vide par hypothèse. Dès lors f1 + · · · + fp ∈ Conv(E) et
(f1 + · · · + fp )∗ (x∗ ) = (g ◦ A)∗ (x∗ ) = (g ∗ ⊻ A∗ )(x∗ ) = inf g ∗ (x∗1 , . . . , x∗p ).
x∗ ∗
1 ,...,xp ∈E
A∗ (x∗
1 ,...,x ∗ )=x∗
p

De plus, l’infimum ci-dessus est atteint lorsqu’il est fini. On vérifie aisément que
g ∗ (x∗1 , . . . , x∗p ) = f1∗ (x∗1 ) + · · · + fp∗ (x∗p ) et que A∗ (x∗1 , . . . , x∗p ) = x∗1 + · · · + x∗p , ce qui
permet de conclure.
2c) Considérons à présent le cas mixte où les fi ∈ Conv(E), où f1 , . . . , fk sont
polyédriques (0 < k < p) et où (∩16i6k dom fi ) ∩ (∩k+16i6p (dom fi )− ◦
) 6= ∅. On note
g1 = f1 + · · · + fk et g2 = fk+1 + · · · + fp .
nom
D’après les points 2a et 2b, on a
g1∗ (y1∗ ) = inf {f1∗ (x∗1 ) + · · · + fk∗ (x∗k ) : x∗1 + · · · + x∗k = y1∗ }
g2∗ (y2∗ ) ∗
= inf {fk+1 (x∗k+1 ) + · · · + fp∗ (x∗p ) : x∗k+1 + · · · + x∗p = y2∗ },
avec des bornes inférieures atteintes lorsqu’elles sont finies. Il suffit donc de montrer
que
(g1 + g2 )∗ (x∗ ) = inf {g1∗ (y1∗ ) + g2∗ (y2∗ ) : y1∗ + y2∗ = x∗ } (3.46)
et que la borne inférieure est atteinte si elle est finie, car alors
(f1 + · · · + fp )∗ (x∗ ) = (g1 + g1 )∗ (x∗ )
 
∗ ∗ ∗ ∗
= inf g (y
1 1 ) + g (y
2 2 ) (3.47)
y1∗ +y2∗ =x∗
  
∗ ∗ ∗ ∗
= ∗
inf
∗ ∗ ∗
inf ∗ ∗
f 1 (x1 ) + · · · + f k (xk )
y1 +y2 =x x1 +···+xk =y1
 
∗
+ inf fk+1 (x∗k+1 ) + · · · + fp∗ (x∗p )
Pre

x∗ ∗ ∗
k+1 +···+xp =y2
 
= inf ∗ f1∗ (x∗1 ) + · · · + fp∗ (x∗p ) .
x∗
1 +···+xp =x
∗

De plus, si (f1 + · · · + fp )∗ (x∗ ) est fini, l’infimum en (3.47) est atteint par des yi∗ (c’est
ce que l’on démontrera), si bien que les gi (yi∗ ) sont finis et les autres bornes inférieures
sont également atteintes. Montrons donc (3.46) et l’affirmation qui suit.
On note A2 := aff dom g2 . Clairement, dom g1 = ∩16i6k dom fi et (dom g2 )− ◦
=
(∩k+16i6p dom fi )− ◦
= ∩k+16i6p (dom fi )− ◦
, car cette dernière intersection est sup-
posée non vide (proposition 2.16). Alors (dom g1 ) ∩ (dom g2 )− ◦
6= ∅, par hypothèse. Il
en découle (voir l’exercice 2.10)
 m
118 3. Fonctions convexes

(A2 ∩ dom g1 )−
◦
∩ (dom g2 )−
◦
6= ∅.

On voit que l’on peut appliquer le point 2b aux fonctions

h1 = g1 + IA2 ∈ Conv(E)

No
et g2 , qui ont un point commun dans l’intérieur relatif de leur domaine. Comme
g1 + g2 = h1 + g2 , on trouve
 
(g1 + g2 )∗ (x∗ ) = (h1 + g2 )∗ (x∗ ) = ∗ inf
∗ ∗
h ∗ ∗
(z
1 1 ) + g ∗ ∗
(z
2 2 ) ,
z1 +z2 =x

avec un infimum atteint s’il est fini. On peut aussi calculer h∗1 par le point 2a, car g1
et IA2 sont polyédriques (exercice 3.15) et ont des domaines qui s’intersectent :
 
h∗1 (z1∗ ) = ∗ inf
∗ ∗
g ∗ ∗
1 (y 1 ) + IA
∗
2
(z ∗
) ,
y1 +z =z1

avec un infimum atteint s’il est fini. En injectant ci-dessus, on trouve

 
(g1 + g2 )∗ (x∗ ) = ∗ ∗inf ∗ ∗ g1∗ (y1∗ ) + IA
∗
2
(z ∗
) + g ∗ ∗
(z
2 2 ) ,
y1 +z +z2 =x
nom
avec un infimum atteint s’il est fini. On peut maintenant regrouper les deux derniers
termes, car IA2 ∈ Conv(E) et g2 ∈ Conv(E) ont un point commun dans l’intérieur
relatif de leur domaine ((dom IA2 )− ◦
= A2 ⊇ (dom g2 )− ◦
):
 
g2∗ (y2∗ ) = (IA2 + g2 )∗ (y2∗ ) = ∗ inf
∗ ∗
IA
∗
2
(z ∗
) + g ∗ ∗
2 (z 2 ) ,
z +z2 =y2

avec un infimum atteint s’il est fini. On conclut

  
∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗
(g1 + g2 ) (x ) = ∗ inf g1 (y1 ) + ∗ inf IA2 (z ) + g2 (z2 )
y1 +y2∗ =x∗ z +z2∗ =y2∗
 
= ∗ inf ∗ ∗
g1∗ (y1∗ ) + g2∗ (y2∗ ) ,
y1 +y2 =x

avec un infimum atteint s’il est fini. ✷

Pre

3.6 Sous-différentiabilité
La notion de dérivée est fondamentale en analyse car elle permet d’approcher
localement des fonctions par des modèles linéaires, plus simples à étudier. Ces modèles
fournissent des renseignements sur les fonctions qu’ils approchent, si bien que de
nombreuses questions d’analyse passent par l’étude des fonctions linéarisées (stabilité,
inversibilité locale, optimalité, etc). On rencontre beaucoup de fonctions convexes qui
ne sont pas différentiables au sens classique (voir l’annexe C pour un rappel sur le
calcul différentiel), en particulier lorsque celles-ci résultent de constructions qui n’ont
rien pour assurer la différentiabilité des fonctions qu’elles produisent. Il en est ainsi
de la fonction duale associée à un problème d’optimisation sous contraintes, pour en
 m
3.6. Sous-différentiabilité 119

citer un exemple emblématique. Pour ces fonctions, on dispose toutefois de la notion

de sous-différentiel qui peut jouer un rôle similaire à celui de la dérivée des fonctions
plus régulières, plus lisses. Nous la développons dans cette section.
Le sous-différentiel est un substitut de la notion de gradient pour les fonctions
convexes non différentiables (section 3.6.1). Ce n’est plus un vecteur de E comme le
gradient, mais un sous-ensemble de E qui n’est réduit à un point qu’en cas de différen-

No
tiabilité (proposition 3.68). Nous l’introduirons de trois manières différentes : à partir
des dérivées directionnelles, dont on sait qu’elles existent toujours pour les fonctions
convexes (proposition 3.14), en utilisant les minorantes affines de f (section 3.2.2) et
en faisant usage de la conjuguée f ∗ (section 3.5).
Une fonction convexe est sous-différentiable si son sous-différentiel est non vide
(définition 3.56). La propriété de sous-différentiabilité s’exprime donc sous la forme
de résultat d’existence. Appliqué à la fonction valeur d’un problème d’optimisation
cela impliquera l’existence de multiplicateurs optimaux (section 4.6.1) et donc de
solutions d’un autre problème d’optimisation, le problème dual (chapitre 14). On
dispose donc là d’une méthode originale pour montrer qu’un problème d’optimisation
a une solution : il suffit de montrer qu’il est le dual d’un problème dont la fonction
valeur est sous-différentiable en zéro (cette technique sera par exemple utilisée pour
établir le théorème 14.17).
Dans cette section, on suppose que l’on travaille sur un espace euclidien E, dont
nom
le produit scalaire est noté h·, ·i.

3.6.1 Définitions

Dans cette section, on se donne une fonction f : E → R ∪ {+∞} convexe avec

domaine non vide, c’est-à-dire
f ∈ Conv(E).
On rappelle que ces fonctions ont aussi une minorante affine et donc f ∗ ∈ Conv(E)
(proposition 3.43). On rappelle également, qu’en tout point de son domaine, une
fonction convexe admet une dérivée directionnelle suivant toute direction, celle-ci
pouvant éventuellement prendre les valeurs −∞ ou +∞ (proposition 3.14).
La notion de sous-différentiabilité est fondée sur la proposition suivante, dont la
longueur de démonstration est inversement proportionnelle à l’importance, qui est
grande.

Proposition 3.55 (définitions du sous-différentiel) Soient f ∈ Conv(E),

Pre

x ∈ dom f et x∗ ∈ E. Alors les propriétés suivantes sont équivalentes :

(i) ∀ d ∈ E : f ′ (x; d) > hx∗ , di,
(ii) ∀ y ∈ E : f (y) > f (x) + hx∗ , y −

xi,

(iii) x ∈ arg miny∈E f (y) − hx∗ , yi = arg maxy∈E hx∗ , yi − f (y) ,
(iv) f (x) + f ∗ (x∗ ) 6 hx∗ , xi,
(v) f (x) + f ∗ (x∗ ) = hx∗ , xi.

Démonstration. [(i) ⇒ (ii)] Par convexité de f et (i) avec d = y−x, on obtient (ii) :

∀y ∈ E : f (y) > f (x) + f ′ (x; y − x) > f (x) + hx∗ , y − xi.

 m
120 3. Fonctions convexes

[(ii) ⇒ (iii)] On récrit (ii) comme suit :

∀y ∈ E : f (y) − hx∗ , yi > f (x) − hx∗ , xi. (3.48)

C’est (iii).
[(iii) ⇒ (iv)] On récrit (3.48) comme suit :

No
∀y ∈ E : hx∗ , xi − f (x) > hx∗ , yi − f (y). (3.49)

En prenant le supremum en y ∈ E à droite, on obtient (iv).

[(iv) ⇒ (v)] Par définition de la conjuguée, on a toujours f (x) + f ∗ (x∗ ) > hx∗ , xi.
[(v) ⇒ (i)] Par (v), on a certainement (3.49), qui avec y = x + td devient

f (x + td) − f (x) > hx∗ , tdi.

Après division par t > 0 et passage à la limite lorsque t ↓ 0, on obtient (i). ✷

Définitions 3.56 On dit qu’une fonction f ∈ Conv(E) est sous-différentiable en un

point x ∈ dom f s’il existe x∗ ∈ E vérifiant les propriétés équivalentes (i)-(v) de la
proposition 3.55. Ces éléments x∗ sont appelés les sous-gradients de f en x. L’ensemble
nom
des sous-gradients de f en x est appelé le sous-différentiel de f en x. Cet ensemble
est noté ∂f (x). Par convention, ∂f (x) = ∅ si x ∈/ dom f . ✷
Chacune des cinq conditions équivalentes (i)-(v) de la proposition 3.55 reflète un
aspect particulier des sous-gradients, permettant en particulier de les calculer.
1) La condition (i) nous apprend qu’un sous-gradient est la pente d’une minorante
linéaire de δx (·) = f ′ (x; ·), forcément exacte en 0 (les deux fonctions s’annulent
en zéro). Ce point de vue conduit à la méthode de calcul de ∂f (x) suivante.
On calcule d’abord la dérivée directionnelle en x et on en détermine toutes les
minorantes linéaires exactes en 0, pour former ∂f (x).
2) Selon la condition (ii), dont l’inégalité porte le nom d’inégalité du sous-gradient,
un sous-gradient est la pente d’une minorante affine de f , exacte en x. On utilise
parfois cette approche pour montrer qu’une pente particulière s ∈ E est un
sous-gradient. Elle est par exemple utilisée dans la démonstration de la proposi-
tion 14.37.
3) La condition (iii) nous informe aussi que x∗ est un sous-gradient de f en x si
Pre

f (·) − hx∗ , ·i atteint son minimum en x. Ce point de vue conduit à la méthode de

calcul de ∂f (x) suivante. On se donne d’abord x∗ et on calcule les minimiseurs
de x 7→ f (x) − hx∗ , xi ; un tel minimiseur x est tel que x∗ ∈ ∂f (x).
4) Les conditions (iv)-(v) nous disent que x∗ est un sous-gradient de f en x si
la plus haute minorante affine de f de pente x∗ , qui est l’application y ∈ E 7→
hx∗ , yi−f ∗ (x∗ ) (voir la discussion au début de la section 3.5.1), est exacte en x. Ce
point de vue conduit à la méthode de calcul de ∂f (x) suivante. On commence par
calculer la fonction conjuguée f ∗ puis on utilise la relation (v). Cette approche est
souvent la plus aisée lorsque f ∗ ne prend que les valeurs 0 ou +∞ ; des exemples
sont donnés aux exercices 3.28, 3.29, 3.32 et 3.34.
 m
3.6. Sous-différentiabilité 121

Nous donnerons à la section 3.6.3 des règles de calcul du sous-différentiel qui per-
mettent souvent de ne pas devoir recourir aux méthodes de calcul de base décrites
ci-dessus.
La figure 3.8 illustre la définition du sous-différentiel.

No
f
x1 + ∂f (x1 )

1
x1

x3
x3 + ∂f (x3 )
x2
∂f
2
1 x2 + ∂f (x2 )

1
nom
Fig. 3.8. Représentations du sous-différentiel. À gauche : la fonction x ∈ R 7→ f (x) =
max(x, x2 ) et la multifonction ∂f . À droite : quelques sous-différentiels dans R2 de x ∈ R2 7→
max(q1 (x), q2 (x), q3 (x)), où les qi sont quadratiques convexes.

À gauche, on a représenté la fonction f : R → R définie par f (x) = max(x, x2 )

(en haut) et l’application multivoque x ∈ R 7→ ∂f (x) ∈ P(R) (en bas). Comme
on le verra à la proposition 3.68, ∂f (x) ne se distingue de ∇f (x), le gradient de f
en x, qu’en des points de non-différentiabilité, c’est-à-dire ici aux points x = 0 et
x = 1. D’après le point (ii) de la proposition 3.55, en un tel point x, ∂f (x) est
l’ensemble des pentes x∗ telles que y 7→ f (x) + hx∗ , y−xi minore f sur R. Ainsi
∂f (0) = [0, 1] et ∂f (1) = [1, 2]. On observe le caractère monotone maximal de la
multifonction x 7→ ∂f (x) (proposition 3.67).
À droite sont représentées les courbes de niveau d’une fonction f : R2 → R, qui
est le maximum de trois fonctions quadratiques convexes. Les courbes en tirets
sont les lieux de non différentiabilité, que l’on repère par les coins qu’y font les
Pre

courbes de niveau. On les appelle les plis de f . Au point x1 , la fonction est

différentiable et le sous-différentiel ∂f (x1 ) se confond avec le vecteur gradient
∇f (x1 ) (proposition 3.68), que l’on a représenté ici après avoir translaté l’origine
en x1 . En x2 et x3 la fonction n’est pas différentiable. Les sous-différentiels en
ces points sont alors les enveloppes convexes des vecteurs gradients des fonctions
quadratiques « actives » en ces points (proposition 3.78) : ∂f (x2 ) est un segment
et ∂f (x3 ) est un triangle. Les sous-différentiels représentés à la figure 3.8 sont
polyédriques, mais ceci est dû à la nature de la fonction considérée (une enveloppe
supérieure d’un nombre fini de fonctions convexes différentiables). Il n’en est pas
toujours ainsi ; par exemple, le sous-différentiel en zéro de la norme ℓ2 dans Rn
est la boule unité associée à cette norme (point 3 de l’exercice 3.28).
 m
122 3. Fonctions convexes

Voici quelques corollaires de la proposition 3.55.

Corollaire 3.57 (sous-différentiel de la dérivée directionnelle) Soit x ∈

dom f et δx l’application dérivée directionnelle définie en (3.9). Alors

No
∂f (x) = ∂δx (0).

Démonstration. Comme δx (0) = 0, cette relation se déduit de l’équivalence entre

les points (i) et (ii) de la proposition 3.55. ✷

Les sous-différentiels de f et de sa conjuguée f ∗ jouissent d’une belle règle de

réciprocité, parfois appelée règle de bascule [331].

Corollaire 3.58 (règle de bascule)

1) Si f ∈ Conv(E), alors x∗ ∈ ∂f (x) =⇒ x ∈ ∂f ∗ (x∗ ).
2) Si f ∈ Conv(E), alors x∗ ∈ ∂f (x) ⇐⇒ x ∈ ∂f ∗ (x∗ ).
nom
Démonstration. 1) Si x∗ ∈ ∂f (x), on a f (x) + f ∗ (x∗ ) = hx∗ , xi (point (v) de la
proposition 3.55). Comme f ∗∗ 6 f (corollaire 3.47), on a aussi, f ∗∗ (x) + f ∗ (x∗ ) 6
hx∗ , xi, ce qui exprime le fait que x ∈ ∂f ∗ (x∗ ) (point (iv) de la proposition 3.55).
2) On a cette fois

x∗ ∈ ∂f (x) ⇐⇒ f (x) + f ∗ (x∗ ) = hx∗ , xi [proposition 3.55 (v)]

∗∗ ∗ ∗ ∗
⇐⇒ f (x) + f (x ) = hx , xi [proposition 3.46]
⇐⇒ x ∈ ∂f ∗ (x∗ ) [proposition 3.55 (v) appliquée à f ∗ ],

ce qui montre l’équivalence. ✷

La réciproque n’a pas lieu au point 1, pour la fonction f ∈ Conv(R) ci-dessous


0 si x < 0 
+∞ si x∗ < 0
f (x) = 1 si x = 0 donc f ∗ (x∗ ) =
 0 si x∗ > 0,
+∞ si x > 0
Pre

/ ∂f (0) = ∅, alors que 0 ∈ ∂f ∗ (0) = ] − ∞, 0].

puisque l’on a 0 ∈

Corollaire 3.59 (sous-différentiel et f ∗ ) Si f ∈ Conv(E), alors

∂f (x) = arg max hx∗ , xi − f ∗ (x∗ ) . (3.50)
x∗ ∈E

Démonstration. On a
 m
3.6. Sous-différentiabilité 123

x∗ ∈ ∂f (x) ⇐⇒ x ∈ ∂f ∗ (x∗ ) [règle de bascule]

⇐⇒ x ∈ arg max h·, xi − f ∗ (·) ,
∗

par le point (iii) de la proposition 3.55, appliqué à f ∗ ∈ Conv(E) au lieu de f . ✷

No
Corollaire 3.60 (sous-différentiels de f et f ∗∗ ) Soient f ∈ Conv(E) et x ∈
dom f . Alors
1) ∂f (x) ⊆ ∂f ∗∗ (x),
2) ∂f (x) 6= ∅ =⇒ f (x) = f ∗∗ (x),
3) f (x) = f ∗∗ (x) =⇒ ∂f (x) = ∂f ∗∗ (x).

Démonstration. 1) Si x∗ ∈ ∂f (x), alors f (x) + f ∗ (x∗ ) = hx∗ , xi (point (v) de la

proposition 3.55), donc f ∗∗ (x) + (f ∗∗ )∗ (x∗ ) 6 hx∗ , xi car f ∗∗ 6 f (corollaire 3.47) et
(f ∗∗ )∗ = f ∗ (proposition 3.48), si bien que x∗ ∈ ∂f ∗∗ (x) (point (iv) de la proposi-
tion 3.55).
2) On a toujours f ∗∗ (x) 6 f (x) (corollaire 3.47). D’autre part, si x∗ ∈ ∂f (x), on
a par définition de f ∗∗ et par le point (v) de la proposition 3.55 :
nom
f ∗∗ (x) > hx∗ , xi − f ∗ (x∗ ) = f (x).

3) D’après le point 1, il reste à montrer l’inclusion ∂f ∗∗ (x) ⊆ ∂f (x). Si x∗ ∈

∂f (x), on a f ∗∗ (x) + (f ∗∗ )∗ (x∗ ) = hx∗ , xi. En utilisant l’hypothèse f (x) = f ∗∗ (x)
∗∗

et la propriété (f ∗∗ )∗ (x∗ ) = f ∗ (x∗ ), on obtient f (x) + f ∗ (x∗ ) = hx∗ , xi, c’est-à-dire

x∗ ∈ ∂f (x). ✷

Corollaire 3.61 (optimalité I)

1) inf f = −f ∗ (0).
2) Si f ∈ Conv(E), alors x̄ ∈ arg min f si, et seulement si, 0 ∈ ∂f (x̄).
3) Si f ∈ Conv(E), alors arg min f = ∂f ∗ (0).

Démonstration. 1) f ∗ (0) = supx h0, xi − f (x) = − inf x f (x).

2) C’est une conséquence immédiate du point (ii) de la proposition 3.55 : si x
minimise f , on peut prendre x∗ = 0 dans (ii), donc 0 ∈ ∂f (x) ; inversement, si
Pre

0 ∈ ∂f (x), x∗ = 0 dans (ii) montre que x minimise f .

3) On a x̄ ∈ arg min f si, et seulement si, 0 ∈ ∂f (x̄) (point 2) si, et seulement si,
x̄ ∈ ∂f ∗ (0) (règle de bascule). ✷

D’après le point 1 du corollaire, trouver un minimiseur de f sur E revient à trouver

les « zéros » de la fonction multivoque ∂f (·). On rapprochera ce fait du résultat selon
lequel, lorsque f est convexe différentiable, les minimiseurs de f sont les zéros de son
application gradient ∇f (·).
 m
124 3. Fonctions convexes

3.6.2 Quelques propriétés

Une fonction f ∈ Conv(E) n’est pas nécessairement sous-différentiable en tout

point de son domaine. Comme nous allons le montrer, la difficulté vient essentiellement
du fait que la fonction dérivée directionnelle en x peut prendre la valeur −∞. Le fait
que f ′ (x; d) = −∞ empêche que f soit sous-différentiable en x se voit clairement par

No
le point (i) de la proposition 3.55. La réciproque est le sujet de la proposition 3.62
ci-dessous. Une telle situation se présente pour la fonction convexe f définie par (3.8),
l’opposée de la racine carrée. Cette fonction n’est pas sous-différentiable en 0, parce
que f ′ (0; 1) = −∞. Évidemment, si f ′ (x; d) = −∞, alors f ′ (x; −d) = +∞ par (3.7),
mais ce n’est pas la valeur +∞ de la dérivée directionnelle qui empêche f d’être sous-
différentiable en x. C’est ce que montre l’exemple suivant de fonction convexe f , dont
le sous-différentiel en 0 vaut [1, +∞[ :


ex si x 6 0 ex
f (x) =
+∞ sinon. 0

Comme nous l’avons mentionné au début de cette section, la mise en évidence de

nom
conditions suffisantes de sous-différentiabilité est importante, car ces conditions de-
viennent alors un moyen de montrer que certains problèmes d’optimisation ont des
solutions. C’est le but de la proposition suivante.

Proposition 3.62 (sous-différentiabilité) Si f ∈ Conv(E) et x ∈ dom f , les

propriétés suivantes sont équivalentes :
(i) ∂f (x) 6= ∅,
(ii) il existe y ∈ (dom f )−
◦
tel que f ′ (x; y − x) > −∞,
′
(iii) f (x; ·) est propre (ou ne prend pas la valeur −∞).
Ces propriétés sont vérifiées si x ∈ (dom f )− ◦
.

Démonstration. [(i) ⇒ (ii)] Soit y un point quelconque de (dom f )− ◦

, qui est
′
non vide. Alors f (x; y − x) > −∞ sinon ∂f (x) serait vide (par le point (i) de la
proposition 3.55).
[(ii) ⇒ (iii)] Comme f ′ (x; 0) = 0, il suffit de montrer que f ′ (x; ·) ne prend pas
la valeur −∞. On raisonne par l’absurde. Soit d1 := y − x (qui peut être nul, si
Pre

x ∈ (dom f )− ◦
) et supposons qu’il existe d0 ∈ E tel que f ′ (x; d0 ) = −∞. On pose
dt := (1−t)d0 + td1 . Par convexité de f ′ (x; ·) (point 1 de la proposition 3.15), f ′ (x; dt )
vaut −∞ pour t ∈ [0, 1[ et vaut +∞ pour t > 1. Mais, pour α ∈ ]0, 1] suffisamment
petit, x + αd0 ∈ dom f (sinon la dérivée directionnelle suivant d0 ne vaudrait pas
−∞). Alors, par convexité de dom f ,
x + αdt = (1−t)[x + αd0 ] + t[x + αd1 ] ∈ dom f
pour t ∈ [0, 1] et même pour t > 1 proche de 1 (car x + αd1 ∈ (dom f )− ◦
par le
lemme 2.13). Mais alors, on ne peut avoir f ′ (x; dt ) = +∞ pour ces t > 1 (le quotient
différentiel est monotone), comme affirmé précédemment.
 m
3.6. Sous-différentiabilité 125

[(iii) ⇒ (i)] Si f ′ (x; ·) est propre, cette fonction convexe a une minorante affine
(proposition 3.6) : ∃x∗ ∈ E et α ∈ R tels que pour tout d ∈ E on a

f ′ (x; d) > hx∗ , di + α.

En remplaçant d par td avec t ↑ ∞, on voit que l’on peut prendre α = 0. Par le

No
point (i) de la proposition 3.55, ce x∗ ∈ ∂f (x) qui est donc non vide.
Finalement, si x ∈ (dom f )− ◦
, la propriété (ii) est vérifiée en prenant y = x. ✷

On trouvera une autre condition nécessaire et suffisante de sous-différentiabilité à

l’exercice 3.25, qui est dans le même esprit que la proposition précédente : il faut et il
suffit que f soit « sous-lipschitzienne ».

Corollaire 3.63 (optimalité II) Si f ∈ Conv(E) et 0 ∈ (dom f ∗ )−

◦
, alors
arg min f est non vide.

Démonstration. Lorsque f ∈ Conv(E), arg min f = ∂f ∗ (0) (corollaire 3.61).

D’après la proposition, lorsque 0 ∈ (dom f ∗ )−
◦
, f ∗ est sous-différentiable en zéro,
donc arg min f 6= ∅. ✷
nom
Proposition 3.64 (propriétés géométrique et topologique du sous-diffé-
rentiel) Soient f ∈ Conv(E), E0 le sous-espace vectoriel parallèle à aff(dom f ),
PE0 le projecteur orthogonal sur E0 et x ∈ dom f . On note f |x+E0 la restriction
de f à x + E0 = aff(dom f ). Alors
1) ∂f (x) = ∂f |x+E0 (x) + E⊥
0 , en particulier PE0 ∂f (x) = ∂f |x+E0 (x),
2) ∂f (x) est convexe et fermé (éventuellement vide),
3) x ∈ (dom f )−◦
⇐⇒ PE0 ∂f (x) est non vide et borné,
◦
4) x ∈ (dom f ) ⇐⇒ ∂f (x) est non vide et borné.

Démonstration. 1) On note f0 : y ∈ E0 7→ f (x + y) la restriction de f à x + E0 .

Soit x∗ ∈ ∂f (x). On peut écrire x∗ = x∗0 + h, avec x∗0 = PE0 x∗ et h = x∗ − x∗0 ∈ E⊥ 0.
Il reste à montrer que x∗0 ∈ ∂f0 (0). Par définition de x∗ , f ′ (x; d) > hx∗ , di, pour tout
d ∈ E. Mais, pour tout d ∈ E0 : f ′ (x; d) = f0′ (0; d) et hx∗ , di = hx∗0 , di, si bien que
f0′ (0; d) > hx∗0 , di. On a montré que x∗0 ∈ ∂f0 (0). Réciproquement, soient x∗0 ∈ ∂f0 (0)
Pre

et h ∈ E⊥ ′ ∗ ′ ′
0 . Alors, pour tout d ∈ E0 : f0 (0; d) > hx0 , di, f0 (0; d) = f (x; d) et hh, di = 0,
′ ∗ ′
si bien que f (x; d) > hx0 + h, di. Comme f (x; d) = +∞ si d ∈ / E0 , on a certainement
aussi f ′ (x; d) > hx∗0 + h, di, pour tout d ∈ E. Donc x∗0 + h ∈ ∂f (x).
2) Comme on a toujours f (x) + f ∗ (x∗ ) > hx∗ , xi, le sous-différentiel est donné par

∂f (x) = {x∗ : f ∗ (x∗ ) − hx∗ , xi 6 −f (x)}.

Mais x∗ 7→ f ∗ (x∗ ) − hx∗ , xi est dans Conv(E) (proposition 3.43). Comme ensemble
de sous-niveau de cette fonction, ∂f (x) est donc convexe et fermé.
3) Notons d’abord que ∂f (x) est non vide lorsque x ∈ (dom f )−◦
(proposition 3.62),
donc PE0 ∂f (x) 6= ∅. Montrons à présent que cet ensemble est borné. Pour un ε > 0
 m
126 3. Fonctions convexes

assez petit, on note L > 0 le module de Lipschitz de f sur B(x, 2ε) ∩ (dom f )− ◦
∗
(proposition 3.13). Soit x un élément non nul de ∂f (x) (si le sous-différentiel est
réduit à {0}, il n’y a plus rien à démontrer). En prenant y = x + εx∗ /kx∗ k au
point (ii) de la proposition 3.55, on obtient εkx∗ k 6 f (x + εx∗ /kx∗ k) − f (x) 6 Lε.
Donc kx∗ k 6 L.
On démontre l’implication inverse par l’absurde. Supposons que x ∈ (dom f ) \

No
(dom f )−◦
et que x∗ ∈ ∂f (x) qui est supposé non vide (si le sous-différentiel est vide,
il n’y a plus rien à démontrer). Il faut montrer que PE0 ∂f (x) est non borné. Par
définition de x∗ , on a f (y) > f (x) + hx∗ , y − xi pour tout y ∈ E. Soit ν ∈ E0 une
normale non nulle à dom f en x (elle existe par la proposition 2.28), qui vérifie donc
hν, y − xi 6 0 pour tout y ∈ dom f . Alors, on a f (y) > f (x) + hx∗ + tν, y − xi, pour
tout y ∈ E et pour tout t > 0. Dès lors x∗ + tν ∈ E0 ∩ ∂f (x) pour tout t > 0, ce qui
démontre que cet ensemble est non borné.
4) Si x ∈ (dom f )◦ , E0 = E et le point 3 montre que ∂f (x) est non vide et borné.
Réciproquement, si ∂f (x) est non vide et borné, E0 = E par le point 1. Alors
(dom f )−◦
= (dom f )◦ et on voit que x ∈ (dom f )◦ par le point 3. ✷

Corollaire 3.65 (optimalité III) Si f ∈ Conv(E) et 0 ∈ (dom f ∗ )◦ , alors

nom
arg min f est non vide et compact.

Démonstration. Lorsque f ∈ Conv(E), arg min f = ∂f ∗ (0) (corollaire 3.61).

D’après les points 2 et 4 de la proposition, lorsque 0 ∈ (dom f ∗ )◦ , ∂f ∗ (0) est non
vide et compact. ✷

Nous avons défini le sous-différentiel à partir de la dérivée directionnelle. La propo-

sition suivante montre que l’on peut retrouver les dérivées directionnelles à partir du
sous-différentiel : f ′ (x; ·) est la fonction d’appui de ∂f (x).

Proposition 3.66 (formule du max) Si f ∈ Conv(E) et x ∈ (dom f )−

◦
, alors,
pour tout d ∈ E, on a
f ′ (x; d) = sup hx∗ , di. (3.51)
x∗ ∈∂f (x)

Le supremum est atteint si f ′ (x; d) < +∞.

Pre

Démonstration. En tant qu’élément de Conv(E) (proposition 3.15), f ′ (x; ·) est l’en-

veloppe supérieure de ses minorantes affines (point 1 de la proposition 3.46). Comme
f ′ (x; ·) est positivement homogène de degré 1 (proposition 3.15), toute minorante
affine est majorée par une minorante linéaire, si bien que f ′ (x; ·) est aussi l’enveloppe
supérieure de ses minorantes linéaires : pour tout d ∈ E,

f ′ (x; d) = sup hx∗ , di = sup hx∗ , di.

∗
x ∈E x∗ ∈∂f (x)
hx∗ ,hi6f ′ (x;h), ∀ h∈E
 m
3.6. Sous-différentiabilité 127

Montrons que l’on peut remplacer le supremum par un maximum, lorsque d ∈ E0 :=

dom f ′ (x; ·), qui est un sous-espace vectoriel lorsque x ∈ (dom f )−◦
(proposition 3.15).
On a en effet
f ′ (x; d) = sup hPE0 x∗ , di = sup hx∗ , di,
x∗ ∈∂f (x) x∗ ∈PE0 ∂f (x)

No
parce que PE0 ∂f (x) ⊆ ∂f (x) (point 1 de la proposition 3.64). On utilise alors le fait
que PE0 ∂f (x) est compact lorsque x ∈ (dom f )−
◦
(points 2 et 3 de la proposition 3.64).
✷

Le résultat précédent ne tient plus si x est sur la frontière relative du domaine

de f . Voici un contre-exemple : f est l’indicatrice de la boule-unité fermée de R2 , pour
la norme euclidienne, et x = (−1, 0). Alors f ′ (x; 0) = 0 et si d 6= 0 :
(
′ 0 si d1 > 0
f (x; d) =
+∞ si d1 6 0.

Comme la fonction δx : d 7→ f ′ (x; d) n’est pas fermée, elle ne peut être la fonction
d’appui d’un ensemble (point 1 de la proposition 3.10) et donc certainement pas du
sous-différentiel. D’ailleurs, ce dernier s’écrit ∂f (x) = {x∗ ∈ R2 : x∗1 6 0, x∗2 = 0} et
nom
(
0 si d1 > 0
σ∂f (x) (d) =
+∞ si d1 < 0

est l’enveloppe convexe fermée de δx . Cette propriété est tout à fait générale pour les
fonctions de Conv(E) (voir l’exercice 3.19).
On peut voir ∂f : E ⊸ E : x 7→ ∂f (x) comme la multifonction qui à un élément
de E fait correspondre le sous-différentiel ∂f (x), qui est une partie de E. En voici
quelques propriétés.

Proposition 3.67 (la multifonction ∂f ) Si f ∈ Conv(E), alors

(i) (dom f )−◦
⊆ dom ∂f ⊆ dom f ,
(ii) R(∂f ) ⊆ dom f ∗ ,
(iii) G(∂f ) est fermé,
(iv) la multifonction ∂f est monotone.
Si f ∈ Conv(E), alors
Pre

(v) (dom f ∗ )−
◦
⊆ R(∂f ),
(vi) (∂f ) = ∂f ∗ ,
−1

(vii) la multifonction ∂f est monotone maximale.

Démonstration. [(i)] C’est une conséquence de la proposition 3.62 et de la défini-

tion 3.56 du sous-différentiel.
[(ii)] Si x∗ ∈ ∂f (x), alors x ∈ dom f (par convention) et f ∗ (x∗ ) = hx∗ , xi− f (x) ∈
R (par le point (v) de la proposition 3.55).
[(iii)] Soit {xk , x∗k } ⊆ G(∂f ), avec xk → x et x∗k → x∗ . Il faut montrer que
(x, x∗ ) ∈ G(∂f ). Il suffit en fait de passer à la limite dans
 m
128 3. Fonctions convexes

∀y ∈ E : f (y) > f (xk ) + hx∗k , y − xk i.

[(iv)] Soient x∗1 ∈ ∂f (x1 ) et x∗2 ∈ ∂f (x2 ). En additionnant les deux inégalités
f (x2 ) > f (x1 ) + hx∗1 , x2 − x1 i et f (x1 ) > f (x2 ) + hx∗2 , x1 − x2 i, on obtient hx∗2 −
x∗1 , x2 − x1 i > 0, ce qui montre la monotonie de ∂f .
[(v)] Si x∗ ∈ (dom f ∗ )− ◦
, alors x∗ ∈ dom ∂f ∗ (par le point (i)), si bien qu’il existe

No
∗ ∗
un x ∈ ∂f (x ) et par le point 2 du corollaire 3.58 (c’est ici que l’on a besoin d’avoir
f ∈ Conv(E)), x∗ ∈ ∂f (x).
[(vi)] C’est le point 2 de la proposition 3.58.
[(vii)] Soit (y, y ∗ ) ∈ E2 tel que

hy ∗ − x∗ , y − xi > 0, ∀ (x, x∗ ) ∈ G(∂f ). (3.52)

Il suffit de montrer que (y, y ∗ ) ∈ G(∂f ). Le problème

 
1 ∗ 2
min f (x) + kx − (y + y)k
x∈E 2

a une unique solution x̄ (en effet, le critère tend vers l’infini à l’infini car f a une
minorante affine ; il est aussi s.c.i. et strictement convexe). Celle-ci vérifie y ∗ + y − x̄ ∈
∂f (x̄). En prenant (x, x∗ ) = (x̄, y ∗ + y − x̄) dans (3.52), on trouve que y = x̄ et donc
nom
que y ∗ ∈ ∂f (x̄) = ∂f (y). ✷

On note que l’on peut très bien avoir R(∂f ) 6= dom f ∗ : pour la fonction x 7→
f (x) = ex , R(∂f ) = ]0, +∞[, alors que dom f ∗ = [0, +∞[.
C’est le caractère fermé de f qui rend ∂f monotone maximale. La théorie des
inéquations variationnelles étudie les opérateurs (éventuellement multivoques) qui
ne « dérivent pas d’un potentiel » (T n’est pas de la forme ∂f , pour une fonc-
tion f ∈ Conv(E)). Cette théorie englobe donc l’optimisation. Lorsque les opéra-
teurs considérés sont monotones, c’est leur caractère maximal qui leur donne une
chance d’être surjectif, comme le caractère fermé de f donne une chance au problème
inf x (f (x) − hu, xi), équivalent à u ∈ ∂f (x), d’avoir une solution. On voit que cela
ne suffit pas et qu’une hypothèse de coercivité (équivalente à la croissance de f vers
l’infini à l’infini) peut être bien utile.
La proposition suivante établit un lien entre la sous-différentiabilité et la diffé-
rentiabilité. Par différentiabilité, on entend soit la Gâteaux-différentiabilité, soit la
Fréchet-différentiabilité, deux notions identiques pour une fonction convexe (propo-
sition 3.17). Ce résultat peut être utilisé pour montrer qu’un fonction convexe est
Pre

différentiable ; il suffit de montrer que son sous-différentiel est un singleton.

Proposition 3.68 (lien avec la différentiabilité) Soient f ∈ Conv(E) et

x ∈ (dom f )◦ . Si f est différentiable en x, alors f est sous-différentiable en x
et ∂f (x) = {∇f (x)}. Inversement, si ∂f (x) est le singleton {x∗ }, alors f est
différentiable en x et ∇f (x) = x∗ .

Démonstration. Si f est différentiable en x, le point (ii) de la proposition 3.55 est

vérifiée avec x∗ = ∇f (x) ; donc ∇f (x) ∈ ∂f (x) et f est sous-différentiable. D’autre
 m
3.6. Sous-différentiabilité 129

part, si x∗0 ∈ ∂f (x), le point (i) de la proposition 3.55 montre que f ′ (x) · d > hx∗0 , di,
∀ d ∈ E. La linéarité de f ′ (x) implique que f ′ (x) · d = hx∗0 , di, ∀ d ∈ E et donc que
x∗0 = ∇f (x). On en déduit que ∂f (x) = {∇f (x)}.
Si ∂f (x) est le singleton {x∗ }, la formule du max (3.51) donne pour tout d ∈ E :
f (x; d) = hx∗ , di. Donc f est (Gâteaux-)différentiable en x et ∇f (x) = x∗ .
′
✷

No
Soit f une fonction convexe différentiable. Alors f ′ est lipschitzienne si, et seule-
ment si, f ∗ est fortement convexe. C’est ce que montre la proposition suivante [332],
qui nous sera utile dans l’analyse des algorithmes quasi-newtoniens (chapitre 11).

Proposition 3.69 (fonction convexe avec gradient lipschitzien) Soit f :

E → R une fonction convexe et C 1,1 . On note ∇f le gradient de f pour le produit
scalaire h·, ·i et L > 0 la constante de Lipschitz de ∇f pour la norme k · k associée
à ce produit scalaire. Alors, pour tout x, y ∈ E, on a
1
h∇f (y) − ∇f (x), y − xi > k∇f (y) − ∇f (x)k2 .
L
nom
Démonstration. Soient x, y ∈ E. On note x∗ = ∇f (x) et y ∗ = ∇f (y). Alors x ∈
∂f ∗ (x∗ ) et y ∈ ∂f ∗ (y ∗ ). Il suffit de montrer la forte convexité de f ∗ (proposition 3.23),
c’est-à-dire
1 ∗
f ∗ (y ∗ ) > f ∗ (x∗ ) + hy ∗ − x∗ , xi + ky − x∗ k2 .
2L
Par définition de f ∗ , on a
 
f ∗ (y ∗ ) = sup hy ∗ , yi − f (y) ,
y∈E

si bien que pour obtenir l’inégalité ci-dessus, il est utile de trouver une majoration
de f (y). En utilisant le développement de Taylor avec reste intégral, la constante de
Lipschitz de ∇f et le point (v) de la proposition 3.55, on obtient
Z 1
f (y) = f (x) + h∇f (x), y − xi + h∇f (x + t(y − x)) − ∇f (x), y − xi dt
0
L
6 f (x) + hx∗ , y − xi + ky − xk2
2
Pre

L
= − f ∗ (x∗ ) + hx∗ , yi + ky − xk2 .
2
Alors  
L
f ∗ (y ∗ ) > f ∗ (x∗ ) + sup hy ∗ − x∗ , yi − ky − xk2 .
y∈E 2
La borne supérieure du membre de droite est atteinte pour y = x + L1 (y ∗ − x∗ ). Après
substitution, on obtient l’inégalité recherchée. ✷
 m
130 3. Fonctions convexes

3.6.3 Règles de calcul

Quelques règles du calcul sous-différentiel sont données dans les propositions sui-
vantes (on en trouvera d’autres dans [332 ; 1993 ; section VI.4]). Les fonctions consid-
érées sont parfois supposées ne prendre que des valeurs finies, mais on trouvera au
corollaire 14.18 une extension de certaines règles de calcul au cas de fonctions pouvant

No
prendre la valeur +∞.

Combinaison conique

Proposition 3.70 (multiplication par un scalaire positif ) Soit α > 0,

f ∈ Conv(E) et x ∈ E. Alors

∂(αf )(x) = α ∂f (x). (3.53)

Démonstration. C’est une conséquence immédiate de la définition du sous-différen-

tiel. ✷
nom
Proposition 3.71 (somme) Soient f1 , . . . , fp ∈ Conv(E) et x ∈ E. Alors

∂(f1 + · · · + fp )(x) ⊇ ∂f1 (x) + · · · + ∂fp (x). (3.54)

L’égalité a lieu ci-dessus si

\
(dom fi )−
◦
6= ∅. (3.55)
16i6p

Dans la condition (3.55), on peut remplacer (dom fi )−

◦
par dom fi si fi est poly-
édrique.

Démonstration. On note f = f1 + · · · + fp .
L’inclusion (3.54) se déduit directement de la définition du sous-différentiel: si
x∗i ∈ ∂fi (x) pour i = 1, . . . , p, alors x ∈ ∩i (dom fi ) = dom f et, pour tout h ∈ E,
Pre

f ′ (x; h) = f1′ (x; h)+· · ·+fp′ (x; h) > hx∗1 +· · ·+x∗p , hi, si bien que x∗1 +· · ·+x∗p ∈ ∂f (x).
Supposons maintenant que (3.55) a lieu et que x∗ ∈ ∂f (x) ; donc x ∈ dom f . Il
s’agit de décomposer x∗ en des sous-gradients des fi . On passe par la conjuguée de f
donnée par la proposition 3.54, point 2 : puisque f ∗ (x∗ ) est fini, on peut écrire

f ∗ (x∗ ) = (f1∗ ⊎ · · · ⊎ fp∗ )(x∗ ) = f1∗ (x∗1 ) + · · · + fp∗ (x∗p ), avec x∗ = x∗1 + · · · + x∗p .

Alors, d’après la définition du sous-différentiel (point (v) de la proposition 3.55):

hx∗1 + · · · + x∗2 , xi = f1 (x) + · · · + fp (x) + f1∗ (x∗1 ) + · · · + fp∗ (x∗p ).

 m
3.6. Sous-différentiabilité 131

Mais on a toujours f2 (x) + · · · + fp (x) + f2∗ (x∗2 ) + · · · + fp∗ (x∗p ) > hx∗2 + · · · + x∗p , xi, si
bien que l’identité ci-dessus donne hx∗1 , xi > f1 (x) + f1∗ (x∗1 ). Comme l’inégalité inverse
a toujours lieu, on obtient hx∗1 , xi = f1 (x) + f1∗ (x∗1 ), c’est-à-dire que x∗1 ∈ ∂f1 (x1 ). De
même pour les autres indices : x∗i ∈ ∂fi (xi ), pour tout i. Donc x∗ ∈ ∂f1 (x) + · · · +
∂fp (x). ✷

No
On ne peut pas se passer de √ la condition (3.55) pour avoir égalité en (3.54). Par
exemple, si f1 est la fonction − x définie en (3.8) et f2 = I]−∞,0] , la somme f = f1 +f2
a son domaine réduit à {0} et ∂f (0) = R, alors que ∂f1 (0) + ∂f2 (0) = ∅, parce que
∂f1 (0) = ∅.

Composition
Le cadre est le suivant. On dispose d’une fonction affine a : E → F entre deux
espaces euclidiens E et F. Celle-ci est supposée être définie en x ∈ E par

a(x) = Ax + b,

où A : E → F est linéaire et b ∈ F. On note A∗ l’application linéaire adjointe de A

pour les produits scalaires que l’on s’est donné sur E et F. L’application affine a est
composée avec une application g : F → R.
nom
Proposition 3.72 (pré-composition par une fonction affine) Dans le cadre
défini ci-dessus, si g ∈ Conv(F), alors pour tout x ∈ E :
 
∂(g ◦ a)(x) ⊇ A∗ ∂g(a(x)) , (3.56)

avec égalité si l’une des conditions suivantes est vérifiée :

R(a) ∩ (dom g)− ◦
6= ∅,
R(a) ∩ dom g 6= ∅ et g est aussi polyédrique.

Démonstration. Démontrons (3.56). Soit y ∗ ∈ ∂g(a(x)), supposé non vide. Alors,

pour tout x′ ∈ E, on a (g ◦ a)(x′ ) = g(a(x′ )) > g(a(x)) + hy ∗ , A(x′ − x)i = (g ◦ a)(x) +
hA∗ y ∗ , x′ − xi, ce qui montre que A∗ y ∗ ∈ ∂(g ◦ a)(x).
Démontrons l’égalité en (3.56) lorsque R(A) ∩ (dom g)− ◦
6= ∅ [resp. lorsque g est
convexe polyédrique et R(A) ∩ (dom g) 6= ∅]. Dans ce cas, g ◦ a ∈ Conv(E) (proposi-
Pre

tion 3.31). Soit x∗ ∈ ∂(g ◦ a)(x) avec x ∈ dom(g ◦ a), ce qui s’écrit (proposition 3.55)

(g ◦ a)∗ (x∗ ) + (g ◦ a)(x) = hx∗ , xi.

En introduisant g0 ∈ Conv(F) par g0 (y) = g(y + b), on peut écrire g ◦ a = g0 ◦ A. La

relation ci-dessus implique que (g0 ◦A)∗ (x∗ ) est fini. D’autre part, R(A)∩(dom g0 )− ◦
=
−◦ −
◦
(R(a) − b) ∩ (dom g − b) = (R(a) ∩ (dom g) ) − b, qui est donc non vide [on trouve
que R(A) ∩ dom g0 est non vide dans le cas polyédrique]. D’après la proposition 3.52,
il existe alors un y ∗ ∈ F tel que A∗ y ∗ = x∗ et (g0 ◦ A)∗ (x∗ ) = g0∗ (y ∗ ). On en déduit
que (g ◦ a)∗ (x∗ ) = g0∗ (y ∗ ) = g ∗ (y ∗ ) − hy ∗ , bi. La relation ci-dessus devient

g ∗ (y ∗ ) + g(a(x)) = hA∗ y ∗ , xi + hy ∗ , bi = hy ∗ , a(x)i.

 m
132 3. Fonctions convexes

Elle exprime que y ∗ ∈ ∂g(a(x)) (proposition 3.55) ; donc x∗ ∈ A∗ (∂g(a(x))). ✷

La démonstration du corollaire suivant est proposée à l’exercice 3.26. Le résultat

doit être différencié du point 1 du théorème 3.64.

No
Corollaire 3.73 (restriction à un sous-espace affine) Soient E0 un sous-
espace vectoriel de E, PE0 le projecteur orthogonal de E sur E0 , x0 ∈ E et f ∈
Conv(E). On note f |x0 +E0 : x ∈ E0 7→ f (x0 + x) la restriction de f à x0 + E0 .
Alors en x ∈ E0 , on a
 
∂(f |x0 +E0 )(x) ⊇ PE0 ∂f (x0 + x) , (3.57)

avec égalité si l’une des conditions suivantes est vérifiée :

(x0 + E0 ) ∩ (dom f )−◦
6= ∅,
(x0 + E0 ) ∩ (dom f ) 6= ∅ et f est aussi polyédrique.

Replaçons-nous dans le cadre défini à la section 3.4.1. Soient E un espace vectoriel,

F : E → (R ∪ {+∞})m une fonction convexe (composante par composante) et g :
Rm → R une fonction convexe croissante (pour l’ordre habituel de Rm ). On sait
nom
qu’alors la fonction composée (g ◦ F ) définie en x ∈ E par

g(F (x)) si F (x) ∈ Rm
(g ◦ F )(x) =
+∞ sinon.

est convexe (proposition 3.32). On s’intéresse ici à sa sous-différentiabilité. Pour rendre

les notations plus compactes, on écrira

∂F (x) := ∂F1 (x) × · · · × ∂Fm (x) ⊆ Em .

Rappelons que si F et g sont à valeurs finies et différentiables, on a

(g ◦ F )′ (x) = g ′ (x) ◦ F ′ (x).

Le résultat suivant généralise cette identité.

Proposition 3.74 (post-composition par une fonction convexe croissan-

te) Dans le cadre défini ci-dessus, le sous-différentiel de g ◦F en x ∈ E est donné
Pre

par
(m )
X
∗ ∗
∂(g ◦ F )(x) = γi xi : γ ∈ ∂g(F (x)), xi ∈ ∂Fi (x), for i ∈ [1 : n] .
i=1

Démonstration. ✷

Ce résultat a de nombreuses conséquences pratiques. On en déduit par exemple

que le carré (ou la puissance p > 2) d’une fonction convexe positive est convexe.
 m
3.6. Sous-différentiabilité 133

Fonction marginale
Rappelons le cadre introduit à la section 3.4.3. On dispose de deux espaces eu-
clidiens E et F et d’une fonction ϕ : E × F → R. La fonction marginale f : E → R
associée à ϕ est définie en x ∈ E par

No
f (x) = inf ϕ(x, y). (3.58)
y∈F

Le sous-différentiel de f dépend de celui de ϕ qui est supposé calculé pour le produit

scalaire de E × F suivant : h(x, y), (x′ , y ′ )i = hx, x′ i + hy, y ′ i.

Proposition 3.75 (fonction marginale) Dans le cadre défini ci-dessus, sup-

posons que ϕ ∈ Conv(E×F) et que f ∈ Conv(E). Si x ∈ dom f et f (x) = ϕ(x, yx )
pour un certain yx ∈ F (i.e., l’infimum en (3.58) est atteint en yx ), alors

∂f (x) = {x∗ : (x∗ , 0) ∈ ∂ϕ(x, yx )}.

Démonstration. On a les équivalences suivantes :

nom
x∗ ∈ ∂f (x)
⇐⇒ f (x′ ) > f (x) + hx∗ , x′ − xi, ∀ x′ ∈ E [proposition 3.55 (ii)]
⇐⇒ ϕ(x , y ) > ϕ(x, yx ) + h(x , 0), (x , y ) − (x, yx )i, ∀ (x′ , y ′ ) ∈ E × F
′ ′ ∗ ′ ′
(3.59)
⇐⇒ (x∗ , 0) ∈ ∂ϕ(x, yx ) [proposition 3.55 (ii)].
L’implication directe ⇒ dans (3.59) vient de l’inégalité f (x′ ) 6 ϕ(x′ , y ′ ) qui est
vérifiée pour tout y ′ ∈ F et de l’égalité f (x) = ϕ(x, yx ). L’implication réciproque ⇐
dans (3.59) vient de ce que le membre de droite est indépendant de y ′ , si bien que l’on
peut donc prendre la borne inférieure en y ′ dans le membre de gauche sans modifier
l’inégalité. ✷

Remarques 3.76 1. Il faut bien noter que, si la borne inférieure inf y ϕ(x, y) est
atteinte en plusieurs yx , {x∗ : (x∗ , 0) ∈ ∂ϕ(x, yx )} ne dépend pas du minimiseur yx
choisi. C’est une conséquence de la démonstration.
On a un autre éclairage sur cette indépendance par rapport à yx en observant que ϕ
est constante sur l’ensemble M (x) := {(x, yx ) : yx minimise ϕ(x, ·)}, si bien que
Pre

∂ϕ est aussi constant sur l’intérieur relatif de M (x) (exercice 3.35). Cependant
∂ϕ(x, yx ) peut varier lorsque (x, yx ) passe de l’intérieur relatif de M (x) à son bord.
C’est le cas de la fonction définie par ϕ(x, y) = max(0, |y| − 1), dont la fonction
marginale est nulle :

 {0} × [−1, 0] si y = −1
M (x) = {x} × [−1, 1] et ∂ϕ(x, yx ) = {(0, 0)} si −1 < y < 1

{0} × [0, 1] si y = 1.

Malgré cela, quel que soit le yx choisi dans [−1, 1], le sous différentiel de f en x est
toujours réduit à {0}.
 m
134 3. Fonctions convexes

2. D’autre part, si ϕ est différentiable en (x, yx ), où yx est un minimiseur quelconque

de ϕ(x, ·), alors f est également différentiable en x (car son sous-différentiel est un
singleton) et on a
∇f (x) = ∇x ϕ(x, yx ).
C’est comme s’il y avait un minimiseur unique yx := η(x), fonction différentiable

No
de x, que l’on écrivait f (x) = ϕ(x, η(x)) et que l’on calculait ∇f (x) par une déri-
vation en chaîne :

∇f (x) = ∇x ϕ(x, η(x)) + η ′ (x)∗ ∇y ϕ(x, η(x)).

On retrouverait le résultat ci-dessus en observant que ∇y ϕ(x, η(x)) = 0 car η(x)

minimise ϕ(x, ·).
3. Le fait que ϕ(x, ·) ait un minimum unique n’implique nullement la différentiabilité
de la fonction marginale en x. Par exemple, f est la fonction marginale de ϕ définie
par ϕ(x, yx ) = f (x) + yx2 . Cette dernière a un minimum yx = 0 unique en y quel
que soit x, alors que f peut ne pas être différentiable.

Enveloppe supérieure
nom
Considérons à présent le cas de l’enveloppe supérieure

f := sup fi
i∈I

de fonctions convexes fi : E → R, pour i dans un ensemble quelconque I, dont les

éléments sont appelés indices ci-dessous. Rappelons de la section 3.4.2, qu’elle est
définie en x ∈ E par  
f (x) = sup fi (x) .
i∈I

On aura besoin de désigner l’ensemble des indices des fonctions fi valant f (x) en
x ∈ E:
I 0 (x) := {i ∈ I : f (x) = fi (x)}.

Proposition 3.77 (enveloppe supérieure I) Dans le cadre défini ci-dessus,

si les fi sont convexes et f ∈ Conv(E), alors pour tout x ∈ dom f , on a
 
Pre

[
∂f (x) ⊇ co  ∂fi (x) . (3.60)
i∈I 0 (x)

Démonstration. Soient x ∈ dom f , i ∈ I 0 (x) et x∗i ∈ ∂fi (x). Comme un sous-

différentiel est un ensemble convexe fermé (proposition 3.64), il suffit de montrer que
x∗i ∈ ∂f (x). Quel que soit y ∈ E, on a
 m
3.7. Proximalité 135

f (y) > fi (y) [par définition de f ]

> fi (x) + hx∗i , y − xi [car x∗i ∈ ∂fi (x)]
= f (x) + hx∗i , y − xi [car i ∈ I 0 (x)].

Ceci montre que x∗i ∈ ∂f (x) (point (ii) de la proposition 3.55). ✷

No
La proposition 3.77 montre en particulier, que ∂f (x) 6= ∅, si l’un des ∂fi (x) 6= ∅,
avec i ∈ I 0 (x). Il se pourrait cependant que I 0 (x) = ∅ ou que ∂fi (x) = ∅ pour tout
i ∈ I 0 (x), auxquels cas cette proposition ne donne pas d’information. Ce dernier cas
se présente, par exemple, lorsque les fonctions fi sont obtenues en divisant par i ∈ N∗
(ou en mulitpliant par i ∈ ]0, 1]) la fonction définie en (3.8) (l’opposée de la racine
carrée) : I 0 (0) = N∗ , mais tous les ∂fi (0) = ∅, alors que f est l’indicatrice de R+ et
a donc un sous-différentiel ∂f (0) = ] − ∞, 0[ non vide.
L’identification de conditions pour avoir l’égalité en (3.60) est un problème délicat.
Un des résultats les plus simples est le suivant. Pour des résultats plus fins, on pourra
consulter la section VI.4.4 dans [332 ; 1993].

Proposition 3.78 (enveloppe supérieure II) Dans le cadre défini ci-dessus,

supposons que
nom
les fi sont convexes,
I est compact,
∀ x ∈ dom f , i 7→ fi (x) est semi-continue supérieurement,
alors pour tout x ∈ (dom f )◦ :
 
[
∂f (x) = co  ∂fi (x) . (3.61)
i∈I 0 (x)

Démonstration. ✷

3.7 Proximalité
Pre

3.7.1 Opérateur proximal

Soient E un espace euclidien (produit scalaire h·, ·i et norme associée k · k) et

f ∈ Conv(E). Pour x donné dans E, on considère le problème
 
1
inf f (y) + ky − xk2 . (3.62)
y∈E 2

Il s’agit donc de l’inf-convolution de f et 21 k · k2 , mais il n’est pas très important de

le savoir. Il sera utile d’introduire une notation pour le critère de ce problème, qui
dépend de x ∈ E :
 m
136 3. Fonctions convexes

1
ϕx (y) := f (y) + ky − xk2 .
2
D’après la proposition 3.6, f a une minorante affine, si bien que ϕx (y) → ∞ lorsque
kyk → ∞ ; de plus ϕx est s.c.i. et strictement convexe. Dès lors le problème ci-dessus
a une solution unique. On la note

No
xp solution unique de (3.79)

et on l’appelle le point proximal de x (celui-ci dépend de f et du produit scalaire

utilisé). Il est clair que le point proximal xp ∈ dom f . On appelle opérateur proximal,
l’application
Pf : E → E : x 7→ xp .
Le point proximal est caractérisé par la condition d’optimalité de (3.79) : 0 ∈
∂ϕx (xp ) = ∂f (xp ) + xp − x. Dès lors

x̃ = Pf (x) ⇐⇒ ∃ g̃ ∈ ∂f (x̃) : x̃ = x − g̃. (3.63)

On note que l’unicité de xp implique celle de

gp := x − xp . (3.64)
nom
On verra à la proposition 3.79 que ce sous-gradient n’est autre que Pf ∗ (x). L’algo-
rithme qui, en x considéré comme l’itéré courant, choisit xp comme itéré suivant est
appelé l’algorithme proximal. Nous l’étudierons à la section 7.2.
On trouvera à la figure 3.9 une illustration du concept de point proximal dans

ϕx
f f

f (x) = |x| f (x) = |x|

xp x xp x
Pre

Fig. 3.9. Deux points de vue sur le point proximal associé à la fonction f = | · |

le cas où E = R et f est la valeur absolue. Le graphique de gauche représente une

première manière de trouver le point proximal xp , vu comme solution de (3.79). On
y voit la fonction f et la fonction ϕx (en tirets) obtenue en ajoutant à f une fonc-
tion quadratique. Le point xp minimise ϕx . La seconde manière de trouver le point
proximal de x utilise l’équation d’optimalité (3.63) : la fonction quadratique concave
y 7→ f (xp ) + 12 kxp − xk2 − 21 ky − xk2 , représentée en tirets, minore f et a en y = xp
la même valeur que f et un gradient valant x − xp , qui est donc égal au sous-gradient
 m
3.7. Proximalité 137

gp de f en xp . Les deux graphes sont donc tangents et xp est l’abscisse de l’unique

point de contact entre ces deux graphes [56].
On vérifie facilement que si f est l’indicatrice IX d’une partie convexe fermée non
vide X de E, Pf est la projection sur X. On peut donc voir l’opérateur proximal
comme une généralisation de ce concept. Comme le montre la proposition suivante,
il a d’ailleurs des propriétés analogues à celle d’une projection (comparez avec la

No
proposition 2.25) : Pf est monotone et contractante. La proposition affirme aussi la
contractilité de l’opérateur
Rf = Pf − Pf ∗ .

Proposition 3.79 (opérateur proximal) Pour une fonction f ∈ Conv(E),

les propriétés suivantes ont lieu :
(i) I − Pf = Pf ∗ ,
(ii) pour tout x et y ∈ E,

hPf (y)−Pf (x), y−xi > kPf (y)−Pf (x)k2 , (3.65)

2 2 2
kPf (y) − Pf (x)k + kPf ∗ (y) − Pf ∗ (x)k 6 ky − xk , (3.66)
kRf (y) − Rf (x)k 6 ky − xk. (3.67)
nom
Démonstration. [(i)] On a (I − Pf )(x) = x − xp = gp , avec gp ∈ ∂f (xp ). D’après
le corollaire 3.58 et f ∈ Conv(E), on a xp ∈ ∂f ∗ (gp ). Alors, l’égalité gp = x − xp et la
caractérisation (3.63) montrent que gp = Pf ∗ (x).
[(ii)-(3.65)] On a xp = x − gpx , avec gpx ∈ ∂f (xp ), et yp = y − gpy , avec gpy ∈ ∂f (yp ).
En retranchant
y − x = yp − xp + (gpy − gpx ). (3.68)
En multipliant scalairement cette identité par (yp − xp ) et en utilisant la monotonie
du sous-différentiel (proposition 3.67), on trouve

hyp − xp , y − xi = kyp − xp k2 + hgpy − gpx , yp − xp i > kyp − xp k2 .

| {z }
>0

[(ii)-(3.66)] L’inégalité s’obtient en élevant (3.68) au carré et en tenant compte

de la monotonie du sous-différentiel.
Pre

[(ii)-(3.67)] En utilisant à nouveau la monotonie du sous-différentiel, on a

kRf (y) − Rf (x)k2 = k(yp − gpy ) − (xp − gpx )k2

= kyp − xp k2 − 2 hgpy − gpx , yp − xp i +kgpy − gpx k2
| {z }
>0
2
6 kyp − xp k + kgpy − gpx k2
2
6 ky − xk [(3.66)]. ✷
 m
138 3. Fonctions convexes

On peut appliquer le résultat précédent en prenant f ∗ ∈ Conv(E) au lieu de f . Le

résultat (ii) s’écrit alors avec gpx = Pf ∗ (x) ∈ ∂f (xp ) et gpy = Pf ∗ (y) ∈ ∂f (yp ) :

hgpy −gpx , y−xi > kgpy −gpx k2 ,

qui n’est pas sans rappeler la proposition 3.69. Il y a deux différences toutefois : il n’y

No
a pas de facteur 1/L et gpx n’est pas un sous-gradient en x mais en xp .

3.7.2 Régularisée de Moreau-Yosida

Soient toujours E un espace euclidien (produit scalaire h·, ·i et norme associée

k · k) et f ∈ Conv(E). La régularisée de Moreau-Yosida de f est la fonction f˜ : E → R
définie par
 
˜ 1 1
f (x) = inf f (y) + ky − xk = f (xp ) + kxp − xk2 ,
2
(3.69)
y∈E 2 2

où xp est le point proximal de x. On observe que f˜ est bien à valeurs réelles car
xp ∈ dom f et f (xp ) > −∞ (f ne prend pas la valeur −∞).
Cette notion est illustrée en dimension 1 à la figure 3.10 lorsque f est la valeur
nom
ϕx
f

f˜
f (x) = |x|
f˜(x)

−1 xp x

Fig. 3.10. Régularisée de Moreau-Yosida f˜ de f : x 7→ |x|

absolue et k · k = | · |. La ligne en tirets représente la fonction ϕx dont on calcule le

Pre

minimum pour obtenir f˜(x).

La proposition suivante donne quelques propriétés intéressantes de la régularisée
de Moreau-Yosida. En particulier, elle montre que f˜ est toujours C 1,1 et régularise
donc f si celle-ci n’est pas différentiable. Cette régularisation se fait sans changer les
minima de f , ni sa valeur minimale.

Proposition 3.80 (régularisée de Moreau-Yosida) Soit f ∈ Conv(E).

Alors
 m
3.7. Proximalité 139

(i) f ◦ Pf 6 f˜ 6 f .
(ii) inf f˜ = inf f .
(iii) arg min f˜ = arg min f = {x ∈ E : f˜(x) = f (x)} = {x ∈ E : x = xp }.
(iv) f˜ ∈ Conv(E) et f˜ est C 1,1 avec ∇f˜(x) = x − xp .

No
Démonstration. [(i)] La première inégalité se déduit du fait que f˜(x) = f (xp ) +
1
2 kxp − xk > f (xp ). Pour la seconde, on prend y = x comme argument de l’infimum
2

définissant f˜.
[(ii)] Du point (i), on a inf f˜ 6 inf f . Par le même point (i), on a f˜(x) > f (xp ) >
inf f ; donc inf f˜ > inf f .
[(iii)] Montrons d’abord les équivalences :

f (x) = f˜(x) ⇐⇒ x = xp ⇐⇒ x ∈ arg min f. (3.70)

Si f (x) = f˜(x), l’infimum dans la définition de f˜ est atteint pour y = x, donc

xp = x ; réciproquement, si xp = x, l’expression (3.69) de f˜ montre que f (x) = f˜(x).
Considérons à présent la seconde équivalence. Si xp = x, gp = x − xp = 0 et donc 0 ∈
nom
∂f (x) (équivalence (3.63)), ce signifie que x ∈ arg min f ; réciproquement, 0 ∈ ∂f (x)
et x = x − 0 impliquent que xp = x (par l’équivalence (3.63)).
Il reste à montrer que
arg min f = arg min f˜.
Si x ∈ arg min f , on a par (3.70) puis le point (ii) que f˜(x) = f (x) = inf f = inf f˜,
donc x ∈ arg min f˜. Inversement, si x ∈ arg min f˜, on a par les points (i) et (ii) :
f (xp ) 6 f˜(x) = inf f˜ = inf f 6 f (xp ), si bien que l’on a en fait égalité partout. Alors
f˜(x) = f (xp ) implique que xp = x (voir la formule de f˜) et donc x ∈ arg min f par
3.70.
[(iv)] La régularisée f˜ est la fonction marginale de (x, y) 7→ f (y) + 12 kx − yk2 , qui
est dans Conv(E × E). Cette dernière est bornée inférieurement en y à x fixé ; donc
la régularisée est dans Conv(E) (proposition 3.34) et même dans Conv(E) car elle est
partout finie (proposition 3.13). D’après la proposition 3.75 :
   
˜ s x − xp
s ∈ ∂ f (x) ⇐⇒ = ,
0 gp + xp − x
Pre

pour un gp ∈ ∂f (xp ). Dès lors, ∂ f˜(x) est le singleton {x − xp }, ce qui implique la

différentiabilité de f˜, avec ∇f˜(x) = x − xp (proposition 3.68). Comme x − xp =
Pf ∗ (x), la caractère lipschitzien de ∇f˜ se déduit de celui de Pf ∗ (proposition 3.79,
formule (3.66)). ✷
 m
140 3. Fonctions convexes

3.8 Point-selle et convexité-concavité

3.8.1 Point-selle
La notion de point-selle (n dit aussi point-col) est très générale, comme l’est celle
d’un minimum d’une fonction. Elle est attachée à des fonctions définies sur un produit

No
d’ensembles n’ayant, a priori, pas de structure particulière.

Définitions 3.81 Soient X et Y deux ensembles et ϕ : X × Y → R. On dit que

(x̄, ȳ) ∈ X × Y est un point-selle de ϕ sur X × Y si
∀(x, y) ∈ X × Y : ϕ(x̄, y) 6 ϕ(x̄, ȳ) 6 ϕ(x, ȳ). (3.71)
Dans les conditions ci-dessus, ϕ(x̄, ȳ) est appelée la valeur-selle de ϕ. ✷
Autrement dit, (x̄, ȳ) est un point-selle de ϕ si, et seulement si, x 7→ ϕ(x, ȳ) atteint un
minimum en x̄ et y 7→ ϕ(x̄, y) atteint un maximum en ȳ. Rien n’est requis en dehors
de la « croix » ({x̄} × Y ) ∪ (X × {ȳ}), si bien l’image de la selle ou du col à laquelle fait
réfeerence l’appellation peut être trompeuse comme lorsque ϕ : R2 → R est définie
par ϕ(x, y) = x2 y 2 (tous les points de l’axe des ordonnées sont des points-selles).
Enfin, on pourra souvent se ramener à la définition précédente par un changement
variable. Par exemple, le point (0, 0) ∈ R2 n’est pas un point-selle de la fonction
nom
(x, y) ∈ R2 7→ xy + (x3 + y 3 ), au sens de la définition ci-dessus, mais le devient
localement après le changement de variables (x, y) y (x̃, ỹ) avec x̃ := x+y et ỹ := x−y
(voir le tracé de droite à la figure 3.11).
La définition est illustrée à la figure 3.11 dans le cas où X = Y = R. On y a

ȳ ȳ ȳ

x̄ x̄ x̄

Fig. 3.11. Courbes de niveau de fonctions ϕ avec point-selle (x̄, ȳ) = (0, 0) : ϕ(x, y) = x2 −y 2
à gauche, ϕ(x, y) = xy au milieu et ϕ(x, y) = (x + y)(x − y) + (x + y)3 + (x − y)3 à droite.
Pre

tracé les courbes de niveaux de trois fonctions ϕ. Le tracé de gauche correspond à la

fonction ϕ(x, y) = x2 − y 2 dont le graphe se présente comme une selle, strictement
convexe suivant l’axe des abscisses et strictement concave suivant l’axe des ordonnées :
il y a un unique point-selle (x̄, ȳ) = (0, 0). Le tracé du millieu est un peu moins lié à
l’idée que l’on peut se faire de point-selle et correspond à la fonction ϕ(x, y) = xy : on
a toujours le même unique point-selle (x̄, ȳ) = (0, 0). Le tracé de droite correspond à
une fonction non quadratique et le point-selle (x̄, ȳ) = (0, 0) n’est que local en x.
La notion de point-selle joue un rôle important en dualité min-max (section 14.1) ;
en particulier par le résultat énoncé au téorème 14.3.
 m
3.8. Point-selle et convexité-concavité 141

3.8.2 Fonction convexe-concave N

Si la convexité d’une fonction apporte une propriété singulière au problème de sa

minimisation, c’est tout naturellement la notion de convexité-concavité qui intervient
lorsque l’on s’intéresse aux points-selles d’une fonction.
Définition de la concavité et de la convexe-concavité. Fonction convexe-concave

No
fermée.

3.8.3 Sous-différentiels convexe-concave N

Le sous-différentiel concave et convexe-concave. Monotonie maximale.

3.8.4 Proximalité convexe-concave N

Proximalité.

Notes
nom
Bien que long, ces deux premiers chapitres ne donnent qu’un aperçu, utile à l’opti-
misation, de l’immense théorie qu’est l’Analyse Convexe. On en apprendra davantage
en travaillant les monographies de Rockafellar [535 ; 1970], d’Hiriart-Urruty et Lema-
réchal [332 ; 1993] et de Borwein et Lewis [81 ; 2000]. Elles traitent toutes les trois
de la théorie en dimension finie et sont orientées vers l’optimisation. Elles ont été
nos trois sources d’information principales. L’ouvrage de Rockafellar est très complet,
mais difficile. On trouve chez Hiriart-Urruty et Lemaréchal à peu près tout ce dont
on a besoin d’analyse convexe en optimisation et on y apprend à manier chaque
notion avec de multiples points de vue. Le livre de Borwein et Lewis se concentre sur
l’essentiel et laisse au lecteur la possibilité de mettre à l’épreuve ses connaissances et
sa maîtrise du sujet sur de nombreux exercices instructifs et stimulants. Mentionnons
aussi la monographie d’Auslender et Teboulle [32] consacrée à l’extension des notions
de cônes et fonctions asymptotiques à l’optimisation non convexe et à l’étude des
inéquations variationnelles.
Les livres d’Ekeland et Temam [199 ; 1974] et de Barbu et Precupanu [38 ; 1975]
sont des classiques de la dimension infinie. Pour des traitements plus récents, on pourra
consulter Aubin et Ekeland [28 ; 1984], Phelps [498 ; 1993] qui synthétise les questions
Pre

touchant aux liens entre la différentiabilité des fonctions convexes et la structure des
espaces de Banach sur lesquels elles sont définies (espaces d’Asplund en particulier)
Bonnans et Shapiro [77 ; 2000] et Borwein et Vanderwerff [82 ; 2010].
La notion de fonction conjuguée fut introduite par Mandelbrojt [422 ; 1939] pour
une fonction d’une seule variable réelle ; il montre la relation f ∗∗ = f pour une fonc-
tion convexe ne prenant que des valeurs finies. L’opération de conjugaison est pré-
cisée et améliorée par Fenchel [211 ; 1949], qui l’étend aux fonctions convexes dépen-
dant d’un nombre fini de variables et qui introduit la notation f ∗ . La conjugaison
généralise une transformation de fonction introduite bien plus tôt par Legendre [403 ;
1787]. L’extension aux espaces vectoriels topologiques est due à Brondsted [96 ; 1964],
Moreau [463 ; 1967] et Rockafellar.
 m
142 3. Fonctions convexes

L’expression « règle de bascule » (corollaire 3.58) a été empruntée à Hiriart-Ur-

ruty [331] et celle « formule du max » (proposition 3.66) à Borwein et Lewis [81]. Le
caractère monotone maximal du sous-différentiel a été mis en évidence par Minty [443 ;
1964] et Moreau [462 ; 1965].
Le lecteur trouvera des compléments sur la régularisée de Moreau-Yosida dans
le très bel article de Moreau [462], sur lequel nous nous sommes en partie fondés.

No
Cette notion s’étend aux opérateurs monotones maximaux (voir par exemple [92, 93]).
On peut aussi prendre des pénalisations autres que la pénalisation quadratique pour
construire cette régularisée [596, 194 ; 1992-93].

Exercices
3.1. Épigraphe d’une fonction. Soit f : E → R. Alors
1) aff(epi f ) = (aff(dom f )) × R,
2) f est convexe si, et seulement si, son épigraphe stricte est convexe,
3) si f est convexe, alors (epi f )−
◦
= {(x, α) : x ∈ (dom f )−
◦
, f (x) < α}.
3.2. Autre définition d’une fonction convexe. Soit f : E → R∪{+∞} une fonction. Alors f
est convexe si, et seulement si,
nom
∀ x, y ∈ dom f, ∀t ∈
/ [0, 1] : f ((1 − t)x + ty) > (1 − t)f (x) + tf (y). (3.72)

3.3. Fonction convexe propre. Soient E un espace vectoriel et f : E → R une fonction

convexe. S’il existe x ∈ (dom f )−
◦
tel que f (x) > −∞, alors f est propre.
3.4. Inégalités de convexité. Soient E un espace vectoriel (de dimension finie).
1) Inégalité de Jensen [350, 351]. Une fonction f : E → R est convexe si, et seu-
lement si, pour tout m-uplet (t1 , . . . , tm ) ∈ ∆m et pour tout (x1 , . . . , xm ) ∈
(dom f )m , on a Pm
Pm
f i=1 ti xi 6 i=1 ti f (xi ). (3.73)
2) Inégalité de Jensen, version intégrale. Une fonction f : E → R ∪ {+∞} est
convexe si, et seulement si, pour tout espace de
R probabilité (Ω, A, µ) et toute
fonction (A, µ)-intégrable F : Ω → E telle que Ω F dµ ∈ dom f , on a
R
R
f Ω F dµ 6 Ω (f ◦ F ) dµ. (3.74)

3) On suppose que f est convexe et on se donne x0 , x1 ∈ dom f et t > 1 tels que

(1−t)x0 + tx1 ∈ dom f . Alors f ((1−t)x0 + tx1 ) > (1−t)f (x0 ) + tf (x1 ).
4) Inégalité géométrico-arithmétique. La moyenne géométrique est inférieure à la
Pre

moyenne arithmétique : si {ai }n

i=1 sont n nombres positifs, on a
Qn P
( i=1 ai )1/n 6 n1 n i=1 ai . (3.75)

Remarque. Pour retenir le sens de cette inégalité, il suffit de constater que

l’inégalité inverse n’a pas lieu si un des ai est nul et un autre ne l’est pas.
5) Soient p et p′ ∈ ]0, 1[ reliés par p1 + p1′ = 1 (nombres conjugués). Pour tout a,
b ∈ R+ , on a
′
ab 6 1p ap + p1′ bp , (3.76)
′
avec égalité si, et seulement si, ap = bp .
3.5. Fonction asymptotique d’une pré-composition par une fonction affine. Démontrez la
proposition 3.29.
 m
3.8. Point-selle et convexité-concavité 143

3.6. Inf-convolution. Démontrez la proposition 3.35 sur l’inf-convolution, ainsi que les
propriétés suivantes :
1) f 6 g =⇒ f ⊎ h 6 g ⊎ h,
2) f ⊎ I{0} = f ,
3) IA ⊎ IB = IA+B .

No
3.7. Courbes de niveau d’une fonction convexe. Chaque dessin A, B et C de la figure 3.12
représente 3 courbes de niveau (iso-valeurs) d’une fonction f définie sur R2 à valeurs

1 2 3 1 2 3 1 2 3

A B C

Fig. 3.12. Courbes de niveau d’une fonction convexe ?

dans R. De manière plus précise, la courbe étiquetée « i » (i = 1, 2, 3) représente

nom
l’ensemble {x ∈ R2 : f (x) = i}. Ces fonctions peuvent-elles être convexes ?
3.8. Fonction quadratique convexe. On considère la fonction réelle définie sur Rn par
f (x) = g T x + 21 xT Hx, où g ∈ Rn et H est une matrice d’ordre n symétrique.
1) Montrez que f est convexe si, et seulement si, H < 0.
2) Montrez que f est strictement convexe si, et seulement si, H ≻ 0.
3) Calculez le cône asymptotique commun aux ensembles de sous-niveau non vides
de f lorsque H < 0 (voir la proposition 3.28).
3.9. Exemples d’inf-convolution. Soient A et B deux opérateurs auto-adjoints sur un
espace euclidien E. On note x 7→ f (x) = hAx, xi et x 7→ g(x) = hBx, xi les formes
quadratiques associées. Calculez f ⊎ g.
3.10. Différentiabilité directionnelle de la fonction max. Pour i ∈ [1 : m], on suppose don-
nées des fonctions fi : E → R qui en x ∈ E sont continues et ont des dérivées
directionnelles. On note fmax : R → R la fonction max, définie par fmax (x) =
max16i6m fi (x), et I(x) := {i ∈ [[1, m]] : fi (x) = fmax (x)}. Alors
′
fmax (x; d) = max fi′ (x; d).
i∈I(x)
Pre

3.11. Caractérisation de la forte convexité d’une fonction. Démontrez la proposition 3.23.

3.12. Problème d’optimisation sans solution. Soient F : Rn → Rm , X ⊆ Rn et k · k une
norme sur Rm . On considère le problème min{kF (x)k : x ∈ X}. On suppose que
0∈/ F (X) et que F (X) est un ouvert. Montrez que :
1) ce problème n’a pas de solution,
2) si F est continue et {xk } est une suite minimisante, ou bien kxk k → ∞, ou bien
lim inf dX c (xk ) = 0 (dX c (xk ) est la distance de xk au complémentaire de X,
supposée infinie si X = Rn ).
Remarque. Ce résultat s’applique par exemple au problème min{ex : x ∈ R}.
3.13. Minimisation concave. Supposons qu’un problème de minimisation d’une fonction
concave f sur un ensemble convexe C ait une solution x∗ . Alors f prend sa valeur
 m
144 3. Fonctions convexes

minimale f (x∗ ) sur la face de C engendrée par x∗ . En particulier, si C est fermé et

a un point extrême, le problème a un minimum en un point extrême de C.
3.14. Optimisation multicritère, Pareto optimalité [347]. Soient X un ensemble et f : X →
Rm une fonction. On considère les composantes de f comme m critères à minimiser
(on parle d’optimisation multicritère). On dit que x∗ ∈ X est Pareto optimal s’il
n’existe pas de x ∈ X vérifiant fi (x) < fi (x∗ ) pour tout i, ce qui s’écrit aussi

No
 
∀ x ∈ X, max fi (x) − fi (x∗ ) > 0.
16i6m

On dit que x∗ ∈ X est moyennement optimal s’il existe un r ∈ Rm + , non nul, tel que
x∗ minimise x 7→ r T f (x) sur X.
1) Montrez que x∗ est Pareto optimal si, et seulement si, (f (x∗ )−Rm ++ )∩f (X) = ∅.
2) On a représenté à la figure 3.13, dans le cas où m = 2, un exemple d’ensem-

f2

f (X)
nom
f1
Fig. 3.13. Un ensemble f (X) dans R2

ble f (X). Déterminez dans celui-ci l’image par f des points Pareto optimaux et
l’image par f des points moyennement optimaux.
3) Montrez qu’un point moyennement optimal est Pareto optimal.
4) Montrez que, lorsque f (X)+Rm + est convexe (a fortiori lorsque f (X) est convexe),
un point Pareto optimal est moyennement optimal.
5) Montrez que f (X) + Rm + est convexe si X est convexe et si les fonctions fi sont
convexes ; alors que f (X) ne l’est pas nécessairement.
3.15. Propriétés particulières aux fonctions convexes polyédriques. Soient f , f1 et f2 des
fonctions convexes polyédriques. Alors
Pre

1) f1 + f2 est polyédrique,
2) f1 ⊎ f2 est polyédrique, epi f1 ⊎ f2 = epi f1 + epi f2 et l’infimum dans la définition
de (f1 ⊎ f2 )(x) est atteint pour tout x ∈ dom(f1 ⊎ f2 ) = dom f1 + dom f2 ,
3) f ∗ est polyédrique.
3.16. Calcul de fonctions conjuguées. On note h·, ·i le produit scalaire utilisé pour définir
la conjuguée.
1) Fonction quadratique strictement convexe. Soient Q une matrice auto-adjointe
définie positive (pour le produit scalaire h·, ·i), q ∈ Rn et f : Rn → R la fonction
quadratique définie par
1
f (x) = hQx, xi + hq, xi.
2
 m
3.8. Point-selle et convexité-concavité 145

Alors, pour tout x∗ ∈ Rn ,

1 −1 ∗
f ∗ (x∗ ) = hQ (x −q), (x∗ −q)i.
2
Si Q est seulement semi-définie positive, on a f ∗ (Qx+q) = 1
2
hQx, xi pour tout
x ∈ Rn et f ∗ (x∗ ) = +∞ si x∗ ∈
/ R(Q) + q.

No
2) Si g(x) = f (x) + α, alors g ∗ (x∗ ) = f ∗ (x∗ ) − α.
3) Monotonie. Si f , g : E → R ∪ {+∞} sont propres avec une minorante affine et
f 6 g, alors f ∗ > g ∗ .
4) Enveloppe inférieure. Soient I un ensemble d’indices quelconque et, pour i ∈ I,
des fonctions fi : E → R ∪ {+∞} propres ayant une minorante affine commune,
c.-à-d., ∃ x∗0 ∈ E tel que supi∈I fi∗ (x∗0 ) < +∞. Alors leur enveloppe inférieure
finf : E → R ∪ {+∞} définie en x par finf (x) = inf i∈I fi (x) est propre avec une
minorante affine et on a
∗
finf = sup fi∗ .
i∈I

5) Enveloppe supérieure. Soient I un ensemble d’indices quelconque et, pour i ∈ I,

des fonctions fi ∈ Conv(E) telles que leur enveloppe supérieure fsup : E →
R ∪ {+∞} définie en x par fsup (x) = supi∈I fi (x) ait un domaine non vide.
Alors fsup ∈ Conv(E) et on a
nom
 ∗∗
∗
fsup = inf fi∗ .
i∈I

∗∗
3.17. Minimum de f et f . Soient E un espace euclidien et f : E → R une fonction non
nécessairement convexe. Montrez que
1) inf f = inf f ∗∗ ,
2) co(arg min f ) ⊆ arg min f ∗∗ (l’égalité n’a pas nécessairement lieu),
3) si f est propre et fermée, si arg min f 6= ∅ et si arg min f ∗∗ est borné, alors
co(arg min f ) = arg min f ∗∗ .
3.18. Enveloppe convexe fermée de fonctions convexes. Soient f , f1 et f2 ∈ Conv(E).
1) Si x0 ∈ (dom f )−◦
et x ∈ E, alors f ∗∗ (x) = limt↑1 f ((1−t)x0 + tx).
2) aff dom f = aff dom f ∗∗ , (dom f )−
◦
= (dom f ∗∗ )− ◦
et adh dom f = adh dom f ∗∗ .
3) Si f1 et f2 ∈ Conv(E) et (dom f1 ) ∩ (dom f2 ) 6= ∅, alors f1 + f2 ∈ Conv(E).
Si f1 et f2 ∈ Conv(E) et (dom f1 )−◦
∩(dom f2 )− ◦
6= ∅, alors (f1 +f2 )∗∗ = f1∗∗ +f2∗∗ .
3.19. Fonction d’appui du sous-différentiel. Soient f ∈ Conv(E) et x ∈ E tel que ∂f (x)
soit non vide. Alors la fonction d’appui de ∂f (x) est l’enveloppe convexe fermée de
δx (·) = f ′ (x; ·) : σ∂f (x) = δx∗∗ 6 δx .
Pre

3.20. Allure du sous-différentiel. Soit f ∈ Conv(E).

1) Soient x̄ ∈ (dom f )−
◦
et ε > 0. Montrez que B̄(0, ε) ⊆ ∂f (x̄) si, et seulement si,
f (x̄; h) > εkhk pour tout h ∈ E.
′

2) Supposons que f soit sous-différentiable en x ∈ E et que t ∈ R 7→ f (x + th) soit

différentiable en 0. Alors ∂f (x) ⊆ f ′ (x; h)h/khk2 + h⊥ .
3.21. Représentation du sous-différentiel. Soit f : R2 → R une fonction convexe, dont on
note ∂f (x) le sous-différentiel en x pour le produit scalaire euclidien. La figure 3.14
donne quatre dessins : A, B, C et D. Dans chacun d’eux, on a noté x un point de R2 ,
C une partie d’une courbe de niveau de f (c.-à-d., f est constante sur une courbe
contenant C) et S un ensemble. Pour chacun de ces dessins :
(a) dites si S peut être l’ensemble x + ∂f (x),
 m
146 3. Fonctions convexes

(b) dans l’affirmative en (a) et si S = x + ∂f (x), dites si x est un minimiseur de f ,

(c) dans l’affirmative en (a) et (b), et si S = x + ∂f (x), dites si x est l’unique
minimiseur de f .

S S C
x x

No
x
C
C C S
S x

A B C D
Fig. 3.14. Représentation du sous-différentiel d’une fonction convexe ?

3.22. Sous-différentiel de fonction fortement convexe [541 ; 1976, proposition 6]. Soient E
un espace euclidien dont le produit scalaire est noté h·, ·i, f ∈ Conv(E) et α > 0.
Alors les propriétés suivantes sont équivalentes :
(i) la fonction f est fortement convexe de module α,
(ii) la multifonction ∂f est fortement monotone de module α,
nom
(iii) ∀ x ∈ dom f , ∀ x∗ ∈ ∂f (x), ∀ y ∈ E, on a f (y) > f (x) + hx∗ , y − xi + (α/2)ky −
xk2 .
3.23. Minimum saillant [502 ; § 5.2.3]. Soient E un espace euclidien dont la norme est notée
k · k, f ∈ Conv(E), B̄ la boule unité fermée de E, x̄ ∈ dom f et α > 0 (un réel).
Montrez que les propriétés suivantes sont équivalentes :
(i) ∀ x ∈ E : f (x) > f (x̄) + αkx − x̄k,
(ii) ∀ d ∈ E : f ′ (x̄; d) > αkdk,
(iii) αB̄ ⊆ ∂f (x̄).
On dit qu’un point x̄ vérifiant ces propriétés est un minimum saillant de f ∈
Conv(E).
3.24. Ensemble saillant de minimiseurs. Soient E un espace euclidien de produit scalaire
noté h·, ·i (norme associée k · k), B̄ := {x ∈ E : kxk 6 1} la boule unité fermée de E,
f ∈ Conv(E) et fmin := inf{f (x) : x ∈ E}. On suppose que fmin est fini et que f a
un ensemble de minimiseurs S := {x ∈ E : f (x) = fmin } non vide.

1) Montrez que, quel que soit x ∈ E, le problème inf{kx − yk : y ∈ S} a une solution

et une seule. On la note PS (x).
Pre

On note dist(x, S) := kx − PS (x)k la distance de x à S, pour la norme k · k. On dit

que l’ensemble des minimiseurs S est saillant s’il existe α > 0 tel que

∀x ∈ E : f (x) > fmin + α dist(x, S). (3.77)

Dans une première partie, on se propose de montrer que cette propriété est équiva-
lente à l’inclusion suivante (pour le même α > 0)
[ 
S + αB̄ ⊆ x + ∂f (x) , (3.78)
x∈S

où le sous-différentiel ∂f (x) de f en x ∈ E est calculé pour le produit scalaire h·, ·i.

 m
3.8. Point-selle et convexité-concavité 147

Supposons dans un premier temps que (3.77) ait lieu et l’on se donne pour objectif
de démontrer (3.78). Soient x̄0 ∈ S, u ∈ B̄ et x̄ := PS (x̄0 + αu). On introduit
g := x̄0 + αu − x̄.

2) Montrez que kgk 6 α.

3) Montrez que ∀x ∈ E, f (x) > f (x̄) + hg, x − x̄i.

No
4) Montrez que (3.78) est vérifiée.

Supposons à présent que (3.78) ait lieu et l’on se donne pour objectif de démontrer
(3.77). Soient x ∈ E\S et x̄ := PS (x).

5) Montrez qu’il existe un x̄1 ∈ S et g1 ∈ ∂f (x̄1 ) tels que

x − x̄
x̄ + α = x̄1 + g1 .
kx − x̄k

6) Montrez que f (x) > fmin + hg1 , x − x̄1 i et en déduire (3.77).

Dans une seconde partie, on considère l’algorithme de minimisation de f , qui calcule

en x ∈ E le nouvel itéré x+ comme solution de
 
1
inf f (y) + ky − xk2 . (3.79)
y∈E 2
nom
7) Sachant que les fonctions de Conv(E) ont une minorante affine, montrez que le
problème (3.79) a une solution et une seule.
8) Supposons que f ait un ensemble saillant de minimiseurs. Montrez que si x est
suffisamment proche de S, alors x+ ∈ S.

3.25. Sous-différentiabilité et sous-lipschitzianité [245 ; lemme 2]. Soit f ∈ Conv(E) et

x ∈ dom f . Montrez que ∂f (x) 6= ∅ si, et seulement si, il existe une constante L > 0
telle que
∀ y ∈ E : f (y) > f (x) − Lky − xk.

3.26. Démontrez le corollaire 3.73.

3.27. Fonction indicatrice. Soient P une partie non vide d’un espace vectoriel E et IP son
indicatrice.
1) Démontrez la proposition 3.5.
Supposons à présent que E soit un espace euclidien, que C soit un convexe non vide
de E, que x ∈ C et que K est un cône non vide de E.
2) IP∗ = σP et IK∗
= IK − .
Pre

3) ∂IC (x) = NC (x).

3.28. Norme. Soient E un espace euclidien dont le produit scalaire est noté h·, ·i et f (·) :=
k·k une norme (pas nécessairement celle associée au produit scalaire). On note k·kd la
norme duale de k·k par rapport à ce produit scalaire (voir (A.8)) et B̄d la boule-unité
fermée pour la norme duale.
1) La norme k·k est une fonction convexe propre fermée, avec une minorante affine.
2) f ∗ = Id .
3) Soit k · kdd la norme biduale de k · k, c’est-à-dire la norme duale de k · kd par
rapport au produit scalaire donné :
kukdd := sup hv, ui.
kvkd 61
 m
148 3. Fonctions convexes

Montrez que k · kdd = k · k et que

∀ x ∈ E, ∃ x∗ ∈ E : kx∗ kd = 1 et hx, x∗ i = kxk. (3.80)
4) Le sous-différentiel de la norme s’écrit
∂f (x) = arg max hy, xi = {x∗ ∈ E : kx∗ kd 6 1 et hx∗ , xi = kxk}. (3.81)

No
kykd 61

En particulier :
– ∂f (0) = B̄D ,
– kx∗ kd = 1 si x∗ ∈ ∂f (x) et x 6= 0,
– si E = Rn , h·, ·i est le produit scalaire euclidien, x 6= 0 et p ∈ ]1, ∞[, on a
∂(k · k1 )(x) = {x∗ ∈ Rn : x∗i = −1 si xi < 0,
x∗i ∈ [−1, +1] si xi = 0,
x∗i = +1 si xi > 0}, (3.82a)
∇(k · kp )(x) = {sgn(xi )(|xi |/kxkp )p−1 }i∈[1 : n] , (3.82b)
∂(k · k∞ )(x) = co{sgn(xi )ei : i ∈ I}, (3.82c)
où ei est le i-ième vecteur de base de Rn et I := {i ∈ [1 : n] : |xi | = kxk∞ }.
5) On déduit de la formule du max (3.51) que la dérivée directionnelle de la norme
en x ∈ E dans la direction h ∈ E s’écrit
nom
(k · k)′ (x; h) = max hx∗ , hi. (3.83)
x∗ ∈B̄D
hx∗ ,xi=kxk

Démontrez :
– (3.83) en utilisant directement la définition (C.1) de la dérivée directionnelle,
– (k · k)′ (0; h) = khk,
– si E = Rn , h·, ·i est le produit scalaire euclidien, x 6= 0 et p ∈ ]1, ∞[, on a
(k · k1 )′ (x; h) = (3.84a)
(k · kp )′ (x; h) = (3.84b)
(k · k∞ )′ (x; h) = max (sgn xi )hi , (3.84c)
i: |xi |=kxk∞

3.29. Puissance de norme. Soient E un espace euclidien dont le produit scalaire est noté
h·, ·i et k · k une norme (pas nécessairement celle associée au produit scalaire). On
note k · kd la norme duale de k · k par rapport à ce produit scalaire (voir (A.8)) et
on considère la fonction f : E → R définie en x ∈ E par
1
f (x) = kxkp ,
p
Pre

où p > 1 est un réel. On note p′ = p/(p − 1) le nombre conjugué de p.

1) La fonction f est convexe propre et fermée.
2) La conjuguée f ∗ : E → R de f prend en s ∈ E la valeur
1 ′
f ∗ (s) = kskpd .
p′
Le sous-différentiel de f en x ∈ E s’écrit (pour le sous-différentiel de la norme,
voir l’exercice 3.28) :
′
∂f (x) = {s ∈ E : hs, xi = kxkp = kskpd } = kxkp−1 ∂(k · k)(x).
Remarque : la dernière expression du sous-différentiel ∂f (x) rappelle la dériva-
tion en chaîne de la composition de x ∈ E 7→ kxk et de t ∈ R 7→ tp /p.
 m
3.8. Point-selle et convexité-concavité 149

3.30. Compteur de composante non nulle. On note k · k0 le compteur de composante non

nulle d’un vecteur (donc kxk0 est le nombre de composantes non nulles du vecteur
x ∈ Rn , voir aussi la section ??). On note également kxkp la norme ℓp de x ∈ Rn
(p = 1 ou ∞) et B̄1 := {x ∈ Rn : kxk1 6 1} la boule unité fermée de Rn pour la
norme ℓ1 . On considère la fonction f : Rn → R définie en x ∈ Rn par

No
f (x) = kxk0 + IB̄1 (x),
où IB̄1 est l’indicatrice de B̄1 (IB̄1 (x) = 0 si x ∈ B̄1 et IB̄1 (x) = +∞ si x ∈
/ B̄1 ).
Montrez que sa conjuguée f ∗ et la biconjuguée f ∗∗ prennent les valeurs suivantes :
f ∗ (x∗ ) = (kx∗ k∞ − 1)+ . (3.85)
∗∗
f (x) = kxk1 + IB̄1 (x). (3.86)

Remarque : : on a montré que, sur la boule unité de la norme ℓ1 , k · k1 est la plus

grande fonction convexe qui minore la fonction non convexe k · k0 (alors que sur Rn
cette plus grande fonction convexe est nulle).
3.31. Fonction maximale. On suppose que Rn est muni du produit scalaire euclidien et
on considère la fonction maximale f : Rn → R définie en x ∈ Rn par f (x) =
max16i6n xi .
1) f ∈ Conv(Rn ).
nom
2) La conjuguée f ∗ de f prend en x∗ ∈ Rn la valeur
 P
0 si x∗ > 0 et n ∗
i=1 xi = 1,
f ∗ (x∗ ) =
+∞ sinon.

3) Le sous-différentiel ∂f (x) de f en x ∈ Rn s’écrit

∂f (x) = co{ei : i ∈ I},
où ei est le i-ième vecteur de base de Rn et I = {j ∈ [1 : n] : xj = maxi xi }.
4) La fonction f est différentiable en x si, et seulement si, le maximum des xi est
atteint pour un seul indice i. Dans ce cas, ∇f (x) = ei .
3.32. Valeur propre maximale. On note S n [resp. S+n
] l’ensemble des matrices d’ordre n
symétriques [resp. symétriques semi-définies positives], que l’on munit du produit
scalaire hA, Bi = tr AB. On note λmax : S n → R l’application valeur propre maxi-
male.
1) La fonction λmax est convexe.
2) La conjuguée de λmax est donnée par
Pre


∗ ∗ 0 si A∗ ∈ S+ n
et tr A∗ = 1
λmax (A ) =
+∞ sinon.

3) Le sous-différentiel de λmax est le compact donné par

∂λmax (A) = co{vv T : kvk2 = 1, Av = λmax (A)v}.

4) Déduire de la formule du sous-différentiel que

a) λmax (·) est différentiable en A si λmax (A) est simple, et que dans ce cas
∇λmax (A) = vv T , où ±v sont les uniques vecteurs propres unitaires cor-
respondants à la valeur propre maximale ; retrouvez ce dernier résultat en
utilisant le théorème des fonctions implicites (théorème C.14) ;
 m
150 3. Fonctions convexes

b) ∂λmax (0) = {S ∈ S+ n
: tr S = 1} ;
c) la dérivée directionnelle de λmax en A ∈ S n dans la direction D ∈ S n s’écrit

λ′max (A; D) = λmax (V T DV ),

où V est une matrice dont les colonnes forment une base orthonormale de

No
l’espace propre associé à λmax (A).
3.33. Valeur propre maximale d’une matrice hermitienne. On note Hn [resp. Hn + ] l’ensemble
des matrices d’ordre n hermitiennes [resp. hermitiennes semi-définies positives], que
l’on munit du produit scalaire hA, Bi = tr AB. L’écriture A < 0 signifie que A ∈ Hn +.
On note λmax : Hn → R l’application valeur propre maximale, qui est bien définie
car les valeurs propres d’une matrice hermitenne sont réelles. Les résultats ci-dessous
s’appliquent bien sûr aux matrices réelles symétriques, qui sont des matrices hermi-
tiennes avec une partie imaginaire nulle.
1) Démontrez (B.17) et en déduire que la fonction λmax est convexe.
2) La conjuguée de λmax est donnée par

0 si A∗ < 0 et tr A∗ = 1
λ∗max (A∗ ) = (3.87)
+∞ sinon.

3) Le sous-différentiel de λmax est le compact donné par

nom
∂λmax (A) = co{vv H : kvk = 1, Av = λmax (A)v}. (3.88)

3.34. Distance à un convexe. Soient E un espace vectoriel normé (norme notée k · k) et C

un ensemble convexe fermé non vide de E. On considère la fonction dC : E → R, la
distance à C, définie par dC (x) = inf y∈C kx − yk.
1) dC est convexe.
On suppose dorénavant que E est un espace euclidien (produit scalaire noté h·, ·i,
mais la norme k · k n’est pas nécessairement celle associée à ce produit scalaire).
On note B̄D la boule-unité fermée pour la norme duale, NC (x) le cône normal à C
en x et x̄ une projection d’un point x sur C (c’est-à-dire une solution du problème
inf{kx−yk : y ∈ C}, qui n’est pas nécessairement unique car la norme n’est pas
nécessairement associée à un produit scalaire).
2) d∞C = k P(C ∞ )− (·)k

3) d∗C = IB̄D + σC .

4) ∂ dC (x) = x∗ ∈ B̄D ∩ NC (x̄) : hx∗ , x − x̄i = kx − x̄k .
On suppose à présent que la norme k · k est celle associée au produit scalaire h·, ·i.
Pre

5) Si x ∈
/ C, alors dC est différentiable en x et ∇ dC (x) = (x−x̄)/kx−x̄k ;
si x ∈ C ◦ (l’intérieur de C), alors dC est différentiable en x et ∇ dC (x) = 0 ;
si x ∈ ∂C = C \ C ◦ (la frontière de C), alors ∂ dC (x) = B̄ ∩ NC (x).
6) Montrez par un contre-exemple que si P ⊆ E n’est pas convexe, dP n’est pas
nécessairement différentiable sur le complémentaire de P .
3.35. Constance du sous-différentiel. Soit f : E → R une fonction convexe et supposons
que f soit constante sur un ensemble A. Alors ∂f est constant sur A−◦
et ce sous-
différentiel commun est inclus dans celui de tout point de A.
3.36. Ensembles de sous-niveau bornés. Soient E un espace euclidien de dimension finie et
f : E → R ∪ {+∞} une application dont on considère les propriétés suivantes :
 m
3.8. Point-selle et convexité-concavité 151

(i) f vérifie la condition de croissance positive à l’infini suivante

f (x) f (x)
lim inf := lim inf > 0,
kxk→∞ kxk / r kxk
r→∞ x∈B

(ii) les ensembles de sous-niveau de f sont bornés,

(iii) f ∗ est continue en 0,

No
(iv) ∪x∈E ∂f (x) est un voisinage de 0.
Montrez que
1) (i) =⇒ (ii), mais que la réciproque n’est pas nécessairement vraie,
2) si f ∈ Conv(E), alors (i) ⇐⇒ (ii) ⇐⇒ (iii),
3) si f ∈ Conv(E), alors (i) ⇐⇒ (ii) ⇐⇒ (iii) ⇐⇒ (iv).
3.37. Proximité d’une solution et petitesse d’un sous-gradient. Soient E un espace euclidien
de dimension finie et f ∈ Conv(E). On suppose que l’ensemble S des minimiseurs de
f est non vide et borné. Montrez que, quel que soit r > 0, il existe un voisinage V
de 0 ∈ E tel que dS (x) 6 r lorsque x∗ ∈ ∂f (x) ∩ V . Montrez par un contre-exemple
que ce résultat ne tient plus si S n’est pas borné.
Remarque. Il n’y a pas de réciproque : x peut être proche de S sans qu’il y ait un
petit sous-gradient en x. La valeur absolue f = | · | sur R en est un contre-exemple :
|f ′ (x)| = 1 quel que soit x 6= 0.
nom
3.38. Croissance quadratique locale (adapté de [541, 542]). Soient E et F deux espaces
normés. On dit qu’une multifonction T : E ⊸ F est localement radialement lipschit-
zienne de module L > 0 en un point x0 ∈ E s’il existe un voisinage V de x0 tel que,
pour tout x ∈ V et pour tout y ∈ T (x), on a dT (x0 ) (y) 6 Lkx − x0 k. On considère
à présent, un espace euclidien E de dimension finie et une fonction f ∈ Conv(E)
ayant un ensemble de minimiseurs S non vide et borné. Montrez que les propriétés
suivantes sont équivalentes (L > 0).
(i) ∂f −1 est localement radialement lipschitzienne de module L en 0,
(ii) il existe un voisinage V de 0 ∈ E tel que dS (x) 6 Lkx∗ k lorsque x∗ ∈ ∂f (x)∩V ,
(iii) il existe une constante α > 0 et un rayon r > 0 tels que pour tout x ∈ S + B̄r ,
on a f (x) > inf f + α(dS (x))2 .
Si (i) ou (ii) a lieu et s’il y a un minimum unique, on peut prendre α = 1/(2L) dans
(iii). Si (iii) a lieu, on peut prendre L = 1/α dans (i) ou (ii).
3.39. Point proximal limite. Soient E un espace euclidien de dimension finie, f ∈ Conv(E)
et r > 0. On note xp (r) le point proximal de x ∈ E, défini comme l’unique solution
de  
1
inf f (y) + ky − xk2 .
y∈E 2r
Pre

Montrez que lorsque r ↑ ∞ :

(i) kxp (r) − xk croît,
(ii) f (xp (r)) décroît,
(iii) si arg min f 6= ∅, xp (r) converge vers la projection de x sur arg min f .
3.40. Proximalité pondérée. Cet exercice propose d’étendre la notion de point proximal au
cas d’une pénalisation quadratique générale. Soient E un espace euclidien (produit
scalaire h·, ·i et norme associée k · k) et f ∈ Conv(E). On se donne un opérateur
auto-adjoint défini positif M auquel on associe un produit scalaire h·, ·iM = hM ·, ·i
1/2
et une norme k · kM = h·, ·iM . Pour x donné dans E, le point proximal, toujours
noté xp , est ici défini comme l’unique solution de
 m
152 3. Fonctions convexes
 
1
inf f (y) + ky − xk2M . (3.89)
y∈E 2

On note Pf,M : E → E : x 7→ xp l’application proximale pondérée par M . Le sous-

différentiel ∂f est calculé par rapport au produit scalaire non pondéré h·, ·i. Montrez
que

No
(i) x̃ = Pf,M (x) ⇐⇒ ∃ g̃ ∈ ∂f (x̃) : x̃ = x − M −1 g̃,
(ii) I − Pf,M = M −1 ◦ Pf ∗ ,M −1 ◦ M ,
(iii) pour tout x et y ∈ E, hyp −xp , y−xiM > kyp −xp k2M ,
(iv) pour tout x et y ∈ E, kyp −xp k2M + kgpy −gpx k2M −1 6 ky−xk2M , où gpx = M −1
(x−xp ) et gpy = M −1 (y−yp ).
3.41. Régularisée de Moreau-Yosida d’une fonction quadratique convexe. On suppose que
f : x ∈ E 7→ f (x) = 12 hAx, xi − hb, xi avec A symétrique définie positive et on
considère sa régularisée de Moreau-Yosida
 
1
x ∈ E 7→ f˜(x) = inf f (y) + ky − xk2M ,
y∈E 2

où k · kM = hM ·, ·i1/2 et M est une matrice symétrique définie positive. Montrez que

f˜ est quadratique et que sa hessienne s’écrit ∇2 f˜ = (A−1 + M −1 )−1 .
nom
Extrait de Fragments d’Optimisation Différentiable : Théorie et Algorithmes,
J. Ch. Gilbert ([email protected]), à paraître. Version du 1 oc-
tobre 2020.
Pre