Chapitre 1.

Éléments d’analyse convexe: rappels et compléments

Ensembles convexes
Definition (Ensemble convexe)
Soit X ⊆ Rn . L’ensemble X est dit convexe si :

∀(x1 , x2 ) ∈ X × X , ∀α ∈ [0, 1], αx1 + (1 − α)x2 ∈ X .

2 / 23
Ensembles convexes
Propriétés (à démontrer à titre d’exercice pour manipuler la définition d’un ensemble convexe)

1 Soit X un ensemble convexe et β ∈ R. Alors l’ensemble

βX = {βx ; x ∈ X }

est convexe.

2 L’intersection d’une collection d’ensembles convexes est un convexe.

3 / 23
Quelques ensembles remarquables

Definition (Combinaison convexe)

Soient x1 , .., xm , m éléments de Rn . On dit que x est combinaison convexe de ces points
s’il existe des réels positifs (α1 , ..., αm ) tels que:
m
X m
X
x= αi xi avec: αi = 1.
i=1 i=1

Definition (Enveloppe convexe)

Soit X ⊆ Rn un ensemble. On appelle enveloppe convexe de X et on note conv (X )
l’ensemble convexe le plus petit contenant X . En dimension finie, c’est aussi l’ensemble
des combinaisons convexes d’éléments de X :
p p
X X
conv (X ) = {x ∈ Rn | x = αi xi où xi ∈ X , p ∈ N et αi = 1, αi ≥ 0}.
i=1 i=1

4 / 23
Quelques ensembles remarquables
Illustrations

5 / 23
Cône convexe et cône dual
On verra plus tard dans ce cours des applications à l’optimisation conique i.e. à des
problèmes d’optimisation de la forme:

minhc, xi sous Ax = b
x∈K

où K est un cône de Rn .

Definition (Cône)
L’ensemble K ⊆ Rn est un cône si:

∀x ∈ K , ∀λ ≥ 0, λx ∈ K .

De plus:
1 K est appelé cône convexe si K est un cône et si K est convexe.
2 K est appelé cône pointé si K est un cône et si K ne contient pas de droite
vectorielle i.e. K ∩ (−K ) ⊂ {0}.
3 K est appelé cône solide si K est un cône et si K est d’intérieur non vide.
4 K est appelé cône propre si K est un cône convexe fermé solide et pointé.

6 / 23
Cône convexe
Illustrations

7 / 23
Inégalités généralisées - Inégalités sur un cône convexe
Soit K un cône propre. K induit un ordre partiel sur Rn :
a K b ⇔ a − b ∈ K .
Quelques exemples.
K = Rn+

Cône de Lorentz: Ln = {(x, z) ∈ Rn × R | ||x||2 ≤ z}.

Cône SDP: S+
n = {M ∈ R
n×n
| M > = M, v > Mv ≥ 0, ∀v ∈ Rn }.

8 / 23
Cône SDP
Illustrations

Montrer que le cône SDP en dimension 2 peut être défini à l’aide d’inégalités
fonctionnelles "classiques".

9 / 23
Cône dual

Definition (Cône dual)

Soit X un sous-ensemble quelconque de Rn . L’ensemble:

X ∗ = {y ∈ Rn | hx, y i ≥ 0, ∀x ∈ X }

est appelé cône dual de l’ensemble X .

10 / 23
Cône dual
Application

1 Les cônes Rn+ et Sn+ sont auto-adjoints:

∗
∗
(Rn+ ) = Rn+ , Sn+ = Sn+ .

2 Calculer (Ln )∗ .

11 / 23
Propriétés du cône dual (1/2)
1 Soit X ⊂ Rn quelconque. Alors X ∗ est un cône convexe.

2 Soit K un cône.
∗
1 K est un cône convexe fermé. .

2 K ⊂ K ∗∗ et K ∗∗ est la fermeture du plus petit cône convexe contenant K .

12 / 23
Propriétés du cône dual (2/2)

3 Si K est un cône convexe fermé non vide alors: K ∗∗ = K .

4 Soient K1 et K2 deux cônes dans Rn tels que: K1 ⊂ K2 . Alors:

K2∗ ⊂ K1∗ .

13 / 23
Inégalités généralisées duales

Definition
Soit K ⊆ Rn un cône propre. Alors:

x K y ⇔ ∀λ K ∗ 0, hλ, xi ≤ hλ, y i.

Cas où K = Rn+ .

14 / 23
Fonctions convexes (rappels)

On considère des fonctions f : Rn → R ∪ {+∞}. Autoriser les fonctions à valoir +∞

présente l’intérêt de pouvoir représenter les problèmes contraints sous une forme non
contrainte: par exemple
inf f (x) = infn f˜(x)
x∈X x∈R
n
avec X sous-ensemble non vide de R et

f (x) si x ∈ X ,
f¯(x) =
+∞ sinon.

On définit alors la notion de domaine d’une fonction f : Rn → R ∪ {+∞}:

Definition (Domaine d’une fonction)

dom(f ) = {x ∈ Rn , f (x) < +∞}.

15 / 23
Fonctions convexes
Definition (Fonction convexe)
• f : Rn → R ∪ {+∞} est dite convexe si :

∀(x, y ) ∈ dom(f )2 , ∀λ ∈ [0, 1], f ((1 − λ)x + λy ) ≤ (1 − λ)f (x) + λf (y ).

• f est dite strictement convexe si :

∀(x, y ) ∈ dom(f )2 , x 6= y , ∀λ ∈ [0, 1], f ((1 − λ)x + λy )<(1 − λ)f (x) + λf (y ).

16 / 23
Caractérisation différentielle de la convexité (1/2)

Soit f : Rn → R une fonction différentiable. Les propositions suivantes sont équivalentes:

(a) f est convexe.

(b)
∀(x, y ) ∈ Rn × Rn , f (y ) ≥ f (x) + h∇f (x), y − xi.
(c) Le gradient de f est un opérateur monotone:

∀(x, y ) ∈ Rn × Rn , h∇f (y ) − ∇f (x), y − xi ≥ 0.

17 / 23
Caractérisation différentielle de la convexité (2/2)

Soit f : Rn → R une fonction de classe C 2 .

• f est convexe ssi:
∀x ∈ Rn , H[f ](x)  0
(i.e. la hessienne de f est semi-définie positive en tout point).
• f est strictement convexe ssi:

∀x ∈ Rn , H[f ](x)  0

(i.e. la hessienne de f est définie positive en tout point).

18 / 23
Eléments d’analyse pour l’algorithmie

Les algorithmes que nous allons étudier dans ce cours vont générer des suites de points
(xk )k∈N qui vont converger suivant les propriétés géométriques de f vers un point
stationnaire/un point de minimum de f .

On s’intéressera dans ce cours à la convergence et à la vitesse de convergence de nos

algorithmes en fonction des propriétés géométriques de f :
Différentiabilité de f
Fonctions à gradient Lipschitz:

∃L > 0, ∀(x, y ) ∈ Rn × Rn , k∇f (x) − ∇f (y )k ≤ Lkx − y k.

Fonctions fortement convexes:

µ
∃µ > 0, ∀(x, y ) ∈ Rn × Rn , f (y ) ≥ f (x) + h∇f (x), y − xi + ky − xk2 .
2

19 / 23
Eléments d’analyse pour l’algorithmie
Propriété clé des fonctions à gradient Lipschitz

Lemma
Soit f : Rn → R une fonction différentiable à gradient L-Lipschitz. Alors:
L
f (y ) ≤ f (x) + h∇f (x), y − xi + ky − xk2
| {z } 2
Approximation linéaire

20 / 23
Eléments d’analyse pour l’algorithmie
Propriété clé des fonctions à gradient Lipschitz

Démonstration:

21 / 23
Eléments d’analyse pour l’algorithmie
Caractérisation par la hessienne

f : Rn → R est une fonction C 2 , convexe à gradient L Lipschitz si et seulement si :

∀x ∈ Rn , λmin (Hf (x)) ≥ 0 convexité

n
∀x ∈ R , λmax (Hf (x)) ≤ L gradient Lipschitz.

1 Montrer que f (x) = 12 kAx − bk2 est convexe à gradient Lipschitz et calculer sa
constante L.
2 Montrer que f (x) = − log(x) est convexe sur R∗+ , mais que son gradient n’est pas
Lipschitz.
3 Montrer que f (x) = exp(x) est convexe sur R, mais que son gradient n’est pas
Lipschitz.
De même : f : Rn → R est une fonction C 2 µ-fortement convexe si et seulement si :

∀x ∈ Rn , λmin (Hf (x))  µ

22 / 23
Eléments d’analyse pour l’algorithmie

23 / 23