Convexité et optimisation

Préparation à l’agrégation (2020–2021)

Jean-François Babadjian

Dans ce chapitre nous rappelons des propriétés élémentaires des ensembles et fonc-
tions convexes dans Rn , que nous appliquons dans un second temps à la recherche de
minima en dimension finie.

1 Convexité

Définition 1. Un ensemble C ⊂ Rn est convexe si pour tout x, y ∈ C et tout θ ∈ [0, 1],

θx + (1 − θ)y ∈ C.

Exemple 1. 1. Les boules (ouvertes ou fermées) de Rn sont convexes (quelque soit

la norme) ;
2. Les sous-espaces vectoriels de Rn sont convexes ;
3. Les sous-espaces affines de Rn sont convexes.

Définition 2. Soit C ⊂ Rn un ensemble convexe. Une fonction f : C → R est dite

convexe si pour tout x, y ∈ C et tout θ ∈ [0, 1],

f (θx + (1 − θ)y) ≤ θf (x) + (1 − θ)f (y).

Si l’inégalité ci-dessus est stricte quelque soient x 6= y et θ ∈ ]0, 1[, on dit que f est
strictement convexe.

Remarque 1. De façon équivalente, f : C → R est convexe si et seulement Pk si pour

tout entier k ≥ 2, tout x1 , . . . , xk ∈ C et tout θ1 , . . . , θk ∈ [0, 1] tels que i=1 θi = 1,
on a
k k
!
X X
f θi xi ≤ θi f (xi ).
i=1 i=1

Par définition de la convexité, cette inégalité est vraie pour k = 2. Supposons que cela
est vrai pour un certain entier k ≥ 2. Soient alors x1 , . . . , xk+1 ∈ C et θ1 , . . . , θk+1 ∈

1
 Pk+1 Pk
[0, 1] tels que i=1 θi = 1. On pose t = θk+1 de sorte que 1 − t = 1 − θk+1 = i=1 θi .
Alors
k+1 k
X X θi
θi xi = (1 − t) xi + txk+1 .
1−t
i=1 i=1
Par définition de la convexité de f , il vient
k+1 k
! !
X X θi
f θi xi ≤ (1 − t)f xi + tf (xk+1 )
1−t
i=1 i=1
Pk θi
puis, en utilisant l’hypothèse de récurrence, comme i=1 1−t = 1,

k+1 k k+1
!
X X θi X
f θ i xi ≤ (1 − t) f (xi ) + tf (xk+1 ) = θi f (xi ).
1−t
i=1 i=1 i=1

Proposition 1. Soit C ⊂ Rn un ensemble convexe. Une fonction f : C → R est

convexe si et seulement si l’épigraphe Epi(f ) = {(x, t) ∈ C × R : f (x) ≤ t} est convexe.

Démonstration. Supposons que Epi(f ) est convexe, alors pour tout x et y ∈ C, on

a que (x, f (x)) et (y, f (y)) ∈ Epi(f ). Par convexité de Epi(f ), pour tout θ ∈ [0, 1], on
a que θ(x, f (x)) + (1 − θ)(y, f (y)) = (θx + (1 − θ)y, θf (x) + (1 − θ)f (y)) ∈ Epi(f ), i.e.

f (θx + (1 − θ)y) ≤ θf (x) + (1 − θ)f (y),

ce qui montre que f est convexe.

Réciproquement, si f est convexe, considérons (x, t) et (y, s) ∈ Epi(f ). Pour tout

θ ∈ [0, 1], on a

f (θx + (1 − θ)y) ≤ θf (x) + (1 − θ)f (y) ≤ θt + (1 − θ)s,

ce qui montre que (θx + (1 − θ)y, θt + (1 − θ)s) = θ(x, t) + (1 − θ)(y, s) ∈ Epi(f ) et donc
que Epi(f ) est convexe. 

1.1 Le cas de la dimension n = 1

Les fonctions convexes jouissent de propriétés de régularité. En dimension 1, cela se

traduit par la propriété de croissance du taux d’accroissement.

Proposition 2. Soit f : ]a, b[ → R (avec −∞ ≤ a < b ≤ +∞) une fonction convexe.

Alors pour tout a < x < y < z < b, on a
f (y) − f (x) f (z) − f (x) f (z) − f (y)
≤ ≤ .
y−x z−x z−y

2
Démonstration. Comme y ∈ ]x, z[, alors y = tx + (1 − t)z, avec

z−y
t= ∈ ]0, 1[.
z−x

Par convexité de f , il vient

y−x
f (y) = f (tx + (1 − t)y) ≤ tf (x) + (1 − t)f (z) = f (x) + [f (x) − f (z)],
x−z

ce qui implique que

f (y) − f (x) f (z) − f (x)
≤ .
y−x z−x
La deuxième inégalité se montre de façon similaire. 

Corollaire 1. Soit f : ]a, b[ → R (avec −∞ ≤ a < b ≤ +∞) une fonction convexe.

Alors f est localement Lipschitzienne.

Démonstration. Soient a < a0 < a1 < b1 < b0 < b. Pour tout x, y ∈ [a1 , b1 ] (avec
par exemple x < y), on a par la Proposition 2,

f (a1 ) − f (a0 ) f (y) − f (x) f (b0 ) − f (b1 )

m= ≤ ≤ = M.
a1 − a0 y−x b0 − b1

En posant L := max(|m|, |M |), il vient

|f (y) − f (x)| ≤ L(y − x),

ce qui montre que f est Lipschtzienne sur [a1 , b1 ]. 

Corollaire 2. Soit f : ]a, b[ → R (avec −∞ ≤ a < b ≤ +∞) une fonction convexe.

Alors f admet des dérivées à gauche et à droite en tout point qui satisfont fg0 (x) ≤ fd0 (x)
pour tout x ∈ ]a, b[.

Démonstration. Soit h > 0 petit, alors d’après la Proposition 2,

f (x) − f (x − h) f (x + h) − f (x)
≤ .
h h
Comme les deux quantités ci-dessus sont monotones par rapport à h, elles admettent
des limites quand h → 0+ , ce qui montre que fg0 (x) et fd0 (x) existent et satisfont

f (x) − f (x − h) f (x + h) − f (x)
fg0 (x) = lim ≤ lim = fd0 (x).
h→0+ h h→0 + h

3
1.2 Le cas de la dimension n ≥ 2

Proposition 3. Soit f : Rn → R une fonction convexe, alors f est continue.

Démonstration.
Pn
Etape 1. Soit x = (x1 , . . . , xn ) ∈ Rn tel que kxk1 := i=1 |xi | = 1. On note
I = {i ∈ {1, . . . , n} : xi ≥ 0} et J = {i ∈ {1, . . . , n} : xi < 0}. Alors, en désignant par
{e1 , . . . , en } la base canonique de Rn , on a
n
X X X X X
x= xi e i = xi e i + (−xi )(−ei ) = |xi |ei + |xi |(−ei ).
i=1 i∈I i∈J i∈I i∈J

Par convexité de f (voir la Remarque 1), il vient

X X
f (x) ≤ |xi |f (ei ) + |xi |f (−ei ).
i∈I i∈J

Soit M : max1≤i≤n max{f (ei ), f (−ei )}, on en déduit que f (x) ≤ M pour tout x ∈ Rn
tel que kxk1 = 1.

Etape 2. Fixons a ∈ Rn et x ∈ Rn tel que kxk1 = 1. Considérons φ : R → R la

fonction définie par φ(t) = f (a + xt) − f (a) pour tout t ∈ R. La convexité de f montre
que φ est également convexe. D’après la Proposition 2, on en déduit que pour tout
t ∈ [−1, 1], on a
φ(−1) − φ(0) φ(t) − φ(0) φ(1) − φ(0)
≤ ≤ ,
−1 − 0 t−0 1−0
soit
f (a + tx) − f (a)
f (a) − f (a − x) ≤ ≤ f (a + x) − f (a).
t
Comme les fonctions x 7→ f (a ± x) − f (a) sont convexes, l’étape 1 montre l’existence
d’une constante Ma > 0 telle que f (a ± x) − f (a) ≤ Ma pour tout x ∈ Rn tel que
kxk1 = 1. Par conséquent

−Ma t ≤ f (a + tx) − f (a) ≤ Ma t pour tout t ∈ [−1, 1].

x
Etape 3. Si x ∈ Rn et x 6= 0, on écrit que x = kxk1 kxk 1
. L’étape 2 montre alors que
|f (a + x) − f (a)| ≤ Ma kxk1 , ce qui implique que f (a + x) → f (a) quand kxk1 → 0 et
donc la continuité de f et a. 
Remarque 2. Tout comme dans le cas de la dimension 1, on peut montrer que toute
fonction convexe est en fait localement Lipschitzienne (à l’intérieur de son domaine).

Dans les résultats qui suivent nous nous intéressons à des caractérisation de la
convexité pour des fonctions plus régulières.

4
Proposition 4. Soient U ⊂ Rn un ouvert, f une fonction de classe C 1 sur U et C ⊂ U
un ensemble convexe. Alors les propriétés suivantes sont équivalentes :
(i) f est convexe sur C ;
(ii) pour tout x et y ∈ C, f (y) ≥ f (x) + ∇f (x) · (y − x).
(iii) pour tout x et y ∈ C, (∇f (y) − ∇f (x)) · (y − x) ≥ 0.

Démonstration. (i) =⇒ (ii) : Supposons f convexe, alors pour tout x, y ∈ C et tout

0 < t ≤ 1, on a f (ty + (1 − t)x) ≤ tf y) + (1 − t)f (x), ce qui implique que

f (x + t(y − x)) − f (x)

≤ f (y) − f (x).
t
Par passage à la limite quand t → 0, on obtient

∇f (x) · (y − x) = df (x)(y − x) ≤ f (y) − f (x).

(ii) =⇒ (iii) : Pour tout x et y ∈ C, on a

(
f (y) ≥ f (x) + ∇f (x) · (y − x),
f (x) ≥ f (y) + ∇f (y) · (x − y).

On additionne les deux inégalités précédentes et on en déduit que (∇f (y) − ∇f (x)) ·
(y − x) ≥ 0.

(iii) =⇒ (ii) : Soient x et y ∈ C. Comme x ∈ U qui est ouvert, il existe r > 0 tel
que B(x, r) ⊂ U . Pour tout t ∈ I := ] − r/kx − yk, r/kx − yk[, on a que x + t(y − x) ∈
B(x, r) ⊂ U . On peut donc définir la fonction φ : I → R par φ(t) = f (x + t(y − x))
pour tout t ∈ I. La fonction φ est de classe C 1 sur I comme composée de fonctions
de classe C 1 . De plus, par le théorème de différentiation des fonctions composées, on a
φ0 (t) = df (x + t(y − x))(y − x) = ∇f (x + t(y − x)) · (y − x) et
Z 1 Z 1
f (y) − f (x) = φ(1) − φ(0) = φ0 (t) dt = ∇f (x + t(y − x)) · (y − x) dt.
0 0

Par hypothèse, on a (comme t > 0)

[∇f (x + t(y − x)) − ∇f (x)] · (y − x) ≥ 0

de sorte que
Z 1
f (y) − f (x) ≥ ∇f (x) · (y − x) dt = ∇f (x) · (y − x),
0

ce qu’il fallait montrer.

5
 (ii) =⇒ (i) : Soient x, y ∈ C et t ∈ [0, 1]. Par convexité de C, on a y + t(x − y) =
tx + (1 − t)y ∈ C d’où
(
f (y) ≥ f (y + t(x − y)) − t∇f (y + t(x − y)) · (x − y),
f (x) ≥ f (y + t(x − y)) + (1 − t)∇f (y + t(x − y)) · (x − y).

On multiplie la première inégalité par (1 − t), la deuxième par t puis on additionne, il

vient
(1 − t)f (y) + tf (x) ≥ f (tx + (1 − t)y),
ce qui montre la convexité de f sur C. 

Remarque 3. Dans le cas des fonctions f : R → R, la propriété (iii) montre que pour
les fonctions de classe C 1 , la croissance de f 0 est une condition nécessaire et suffisante
à la convexité de f .

Exemple 2. 1. La fonction x ∈ ]0, +∞[ 7→ (− ln)0 (x) = − x1 étant croissante, on en

déduit que la fonction − ln est convexe sur ]0, +∞[. Par conséquent, si a et b > 0
et p, q > 1 sont tels que p1 + 1q = 1, on a

ap bq
 
1 1
− ln + ≤ − ln(ap ) − ln(bq ) = − ln a − ln b = − ln(ab),
p q p q

puis, par passage à l’exponentielle,

ap bq
ab ≤ + .
p q
Cette inégalité de Young s’étend de manière triviale au cas a ≥ 0 et b ≥ 0.
2. Soientx, y ∈ Rn non nuls, en appliquant l’inégalité de Young à |xi | et |yi | pour
tout 1 ≤ i ≤ n, il vient
|xi |p |yi |q
|xi yi | ≤ + .
p q
En sommant pour i = 1, . . . , n on obtient

kxkpp kykqq
|x · y| ≤ + .
p q

En remplaçant x et y par x/kxkp et y/kykq , respectivement, on en déduit que

1 1
|x · y| ≤ + = 1,
p q
soit
|x · y| ≤ kxkp kykq ,
ce qui correspond à l’inégalité de Hölder. De nouveau, cette inégalité s’étend de
manière évidente à tout vecteurs x et y ∈ Rn .

6
 3. Pour tout x1 , . . . , xn > 0, on a
 !1/n 
n n n
!
1X 1 Y Y
ln xi = ln xi = ln  xi .
n n
i=1 i=1 i=1

La fonction exponentielle étant croissante et de dérivée égale à elle même, elle est
convexe sur R, d’où
n
!1/n " n # n n
Y 1X 1X 1X
xi = exp ln xi ≤ exp(ln xi ) = xi .
n n n
i=1 i=1 i=1 i=1

Cette inégalité arithmético-géométrique s’étend à tout x1 , . . . , xn ≥ 0.

Le résultat suivant donne une caractérisation de la convexité à l’ordre 2 pour les

fonctions de classe C 2 .
Proposition 5. Soient U ⊂ Rn un ouvert, f une fonction de classe C 2 sur U et C ⊂ U
un ensemble convexe. Alors les propriétés suivantes sont équivalentes :
(i) f est convexe sur C ;
(ii) pour tout x et y ∈ C, [D2 f (x)(y − x)] · (y − x) ≥ 0.

Démonstration. (i) =⇒ (ii) : Supposons f convexe sur C et soient x, y ∈ C. Par

convexité de C, si t ∈ ]0, 1], on a ty + (1 − t)x = x + t(y − x) ∈ C puis, d’après la
Proposition 4,
(∇f (x + t(y − x)) − ∇f (x)) · (y − x) ≥ 0.
On divise l’inégalité précédente par t puis on passe à la limite quand t → 0 ce qui
implique [D2 f (x)(y − x)] · (y − x) ≥ 0.

(ii) =⇒ (i) : Soient x et y ∈ C. Comme x ∈ U qui est ouvert, il existe r > 0 tel que
B(x, r) ⊂ U . Pour tout t ∈ I := ] − r/kx − yk, r/kx − yk[, on a que x + t(y − x) ∈
B(x, r) ⊂ U . On peut donc définir la fonction φ : I → R par φ(t) = f (x + t(y − x))
pour tout t ∈ I. La fonction φ est de classe C 2 sur I comme composée de fonctions
de classe C 2 . De plus, par le théorème de différentiation des fonctions composées, on a
φ0 (t) = ∇f (x + t(y − x)) · (y − x) et φ00 (t) = [D2 f (x + t(y − x))(y − x)] · (y − x). D’après
la formule de Taylor-Lagrange, il existe t̄ ∈ [0, 1] tel que
1
φ(1) = φ(0) + φ0 (0) + φ00 (t̄).
2
En posant z̄ = t̄x + (1 − t̄)y, il vient
1
f (y) = f (x) + ∇f (x) · (y − x) + [D2 f (z̄)(y − x)] · (y − x).
2
1
Or [D2 f (z̄)(y − x)] · (y − x) = (1−t̄)2
[D2 f (z̄)(x − z̄)] · (x − z̄) ≥ 0 ce qui implique que

f (y) ≥ f (x) + ∇f (x) · (y − x).

La convexité de f résulte de la Proposition 4. 

7
2 Optimisation sur un ouvert

Soient U est un ouvert de Rn et f une fonction de classe C 1 sur U . Nous avons

déjà vu dans le cours de calcul différentiel que si f admet un minimum (ou même un
extremum) local en x0 ∈ U , alors x0 est un point critique de f :

∇f (x0 ) = 0. (1)

Il s’agit d’une condition nécessaire d’optimalité d’ordre 1 également appelée équation

d’Euler-Lagrange. De plus, si f est de classe C 2 sur U , alors les valeurs propres de la
matrice hessienne D2 f (x0 ) sont toutes positives ou nulles, ce qui se traduit par le fait
que la matrice D2 f (x0 ) est positive, i.e.,

hD2 f (x0 )u, ui ≥ 0 pour tout u ∈ Rn .

La condition (1) n’est en général pas suffisante (pensez par exemple à la fonction
f : x ∈ R 7→ x3 dont la dérivée s’annule en 0 qui n’est pas un point d’extremum
local). En revanche, dans le cas des fonctions convexes, cette condition est également
suffisante.
Proposition 6. Soit f : U → R une fonction de classe C 1 sur un ouvert U ⊂ Rn . On
suppose que x0 ∈ U est un point critique de f et que f est convexe dans un voisinage
convexe de x0 . Alors x0 est un point de minimum local de f sur U .

Démonstration. Soit r > 0 tel que B(x0 , r) ⊂ U et f est convexe sur B(x0 , r). D’après
la caractérisation à l’ordre 1 des fonctions convexes, on a pour tout y ∈ B(x0 , r),

f (y) ≥ f (x0 ) + h∇f (x0 ), y − x0 i = f (x0 ),

ce qui montre effectivement que x0 est un point minimum de f sur B(x0 , r), et donc
un point de minimum local de f sur U . 
Exemple 3. Soit f : Rn → R la fonctionnelle quadratique définie par
1
f (x) = hAx, xi − hb, xi pour tout x ∈ Rn ,
2
où A ∈ Mn (R) est symétrique et b ∈ Rn . Il s’agit d’une fonction de classe C ∞ sur Rn .
De plus, pour tout x ∈ Rn , on a

∇f (x) = Ax − b, D2 f (x) = A.

Donc si f admet un minimum en x0 , alors x0 est solution du système linéaire Ax =

b et la matrice A est positive, autrement dit, la fonction f est convexe d’après la
caractérisation à l’ordre 2 de la convexité. Réciproquement, si f est convexe sur Rn , i.e.
si A est positive, et si x0 est un point critique de f , alors x0 est un point de minimum
(global) sur Rn .

8
3 Optimisation sur un convexe

Commençons par un résultat général d’existence et d’unicité.

Proposition 7. Soit C ⊂ Rn un ensemble fermé non vide et f : C → R une fonction
semi-continue inférieurement. On suppose soit C borné, soit f coercive, i.e.

lim f (x) = +∞.

kxk→∞

Alors f admet des points de minimum sur C. Si de plus C est convexe et f est stric-
tement convexe, il y a unicité du point de minimum.

Démonstration. On définit I = inf C f et on note que I < +∞ (à ce stade, il n’est

pas exclu que I = −∞). Par définition de l’infimum, pour tout k ∈ N∗ , il existe xk ∈ C
tel que
— si I = −∞, alors I ≤ f (xk ) ≤ −k ;
— si I ∈ R, alors I ≤ f (xk ) ≤ I + 1/k.
On définit ainsi une suite (xk )k∈N d’éléments de C ayant la propriété limk f (xk ) = I.
Une telle suite s’appelle suite minimisante.

On prétend que la suite (xk )k∈N est bornée. Si l’ensemble C est borné, cette pro-
priété est immédiate. Si f est coercive, supposons par l’absurde que, pour une sous-
suite (xϕ(k) )k∈N de (xk )k∈N , on ait kxϕ(k) k → +∞. Par coercivité de f , on aurait que
f (xϕ(k) ) → +∞ ce qui rentre en contradiction avec le fait que

lim f (xϕ(k) ) = lim f (xk ) = I < +∞.

k→+∞ k→+∞

On en déduit que dans cet autre cas, la suite (xk )k∈N ne peut être que bornée.

D’après le théorème de Bolzano-Weierstrass, on peut extraire de (xk )k∈N une sous-

suite (xσ(k) )k∈N qui converge vers un élément x̄ ∈ C (car C est fermé). Comme f est
semi-continue inférieurement, on en déduit que

f (x̄) ≤ lim inf f (xσ(k) ) = lim f (xσ(k) ) = lim f (xk ) = I ≤ f (y) pour tout y ∈ C.
k→+∞ k→+∞ k→+∞

Pour l’unicité, considérons deux points de minimum x̄1 et x̄2 ∈ C tels que x̄1 6= x̄2 .
Par convexité de C, on a que x̄1 +x̄
2
2
∈ C et par stricte convexité de f , il vient
 
x̄1 + x̄2 1
I≤f < (f (x̄1 ) + f (x̄2 )) = I,
2 2
ce qui est absurde. Par conséquent x̄1 = x̄2 . 

Nous nous intéressons à présent à une condition nécessaire et suffisante d’optimalité

dans le cas convexe.

9
Proposition 8. Soit f : U → R une fonction convexe et de classe C 1 sur un ouvert U
de Rn . Soit C ⊂ U un ensemble convexe, fermé non vide. Alors x̄ ∈ C est solution de

inf f (x)
x∈C

si et seulement si x̄ est solution de l’inéquation d’Euler

h∇f (x̄), y − x̄i ≥ 0 pour tout y ∈ C.

Démonstration. Commençons par la condition nécessaire. Il s’agit de faire des petites

variations autour du point x̄, mais dans des directions admissibles de façon à rester dans
le convexe. Pour ce faire, on considère t ∈ ]0, 1[ et y ∈ C de sorte que, par convexité de
C, ty + (1 − t)x̄ = x̄ + t(y − x̄) ∈ C. Par conséquent,

f (x̄) ≤ f (x̄ + t(y − x̄)),

d’où
f (x̄ + t(y − x̄)) − f (x̄)
h∇f (x̄), y − x̄i = lim ≥ 0.
t→0+ t

Pour la condition suffisante, nous utilisons la caractérisation à l’ordre 1 de la convexité

qui donne, pour tout y ∈ C,

f (y) ≥ f (x̄) + h∇f (x̄), y − x̄i ≥ f (x̄),

ce qui conclut la preuve de la proposition. 

Exemple 4. On s’intéresse à la projection orthogonale d’un élément x ∈ Rn sur un
convexe fermé non vide C de Rn . Pour ce faire on considère le problème de minimisation

inf kx − yk2 , (2)

y∈C

où k · k est une norme euclidienne sur Rn . On pose f (y) = kx − yk2 (attention, ici x est
fixé et y est la variable). La fonction f est de classe C ∞ sur Rn , car polynômiale. Elle
est strictement convexe car si y1 et y2 ∈ Rn avec y1 6= y2 et t ∈]0, 1[, alors

f (ty1 + (1 − t)y2 ) = kt(x − y1 ) + (1 − t)y2 k2

= tkx − y1 k2 + (1 − t)kx − y2 k2 − t(1 − t)ky1 − y2 k2
< tf (y1 ) + (1 − t)f (y2 ).

La fonction f est coercive car, par l’inégalité de Cauchy-Schwarz,

f (y) = kyk2 − 2hx, yi + kxk2 ≥ kyk2 − 2kxkkyk + kxk2 = P (kyk),

où P (t) = t2 − 2kxkt + kxk2 → +∞ quand t → +∞. D’après la Proposition 7, il existe

un unique ȳ solution de (2). Il s’agit du projeté orthogonal de x sur C, parfois noté
PC (x).

10
 Question : pourquoi cette preuve d’existence et d’unicité de la projection orthogonale
ne fonctionne pas dans un espace de Hilbert général ?

Le calcul du gradient de f donne, pour tout y ∈ Rn ,

∇f (y) = 2(y − x)

de sorte que la condition nécessaire et suffisante donnée par la Proposition 8 s’écrit ici

hȳ − x, y − ȳi ≥ 0 pour tout y ∈ C

ou encore
hx − PC (x), y − PC (x)i ≤ 0 pour tout y ∈ C.

Question : cela vous rappelle-t-il quelque chose ?

11