3) Éléments d’analyse convexe

Rappel mathématique

Zakia ANKHILI
Université Cadi Ayyad
ENSA, Marrakech

Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 1/20

3) Éléments d’analyse convexe

3) Éléments d’analyse convexe

3.1) Ensemble convexe
Définition
Soit E ⊂ IRn . E est dit convexe si

∀x1 , x2 ∈ E, ∀λ ∈ [0, 1], λx1 + (1 − λ)x2 ∈ E.

Exercice
Supposons que E est convexe. Soit x1 , x2 , ..., xn ∈ E, alors
n
X n
X
∀λ = (λ1 , λ2 , ..., λn ), λi = 1, λi ∈ [0, 1], on a λi xi ∈ E
i=1 i=1

Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 2/20

3) Éléments d’analyse convexe

3) Éléments d’analyse convexe

3.1) Ensemble convexe
Définition
Soit E ⊂ IRn . E est dit convexe si

∀x1 , x2 ∈ E, ∀λ ∈ [0, 1], λx1 + (1 − λ)x2 ∈ E.

Exercice
Supposons que E est convexe. Soit x1 , x2 , ..., xn ∈ E, alors
n
X n
X
∀λ = (λ1 , λ2 , ..., λn ), λi = 1, λi ∈ [0, 1], on a λi xi ∈ E
i=1 i=1

Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 2/20

3) Éléments d’analyse convexe

Théorème
Soit E1 , E2 deux ensemble convexes de IRn . Alors,
1 E1 ∩ E2 est convexe.
2 E1 + E2 = {x1 + x2 / x1 ∈ E1 , x2 ∈ E2 } est convexe.
3 E1 − E2 = {x1 − x2 / x1 ∈ E1 , x2 ∈ E2 } est convexe.

3.2 Enveloppe convexe

Définition
Soit E ⊂ IRn . L’enveloppe convexe de E, noté Co(E) ou
conv(E) est l’ensemble de toute les combinaisons convexes
d’éléments de E.
n
nX n
X o
conv(E) = λi xi tel que xi ∈ E, λi = 1, λi ∈ [0, 1] .
i=1 i=1

Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 3/20

3) Éléments d’analyse convexe

Théorème
Soit E1 , E2 deux ensemble convexes de IRn . Alors,
1 E1 ∩ E2 est convexe.
2 E1 + E2 = {x1 + x2 / x1 ∈ E1 , x2 ∈ E2 } est convexe.
3 E1 − E2 = {x1 − x2 / x1 ∈ E1 , x2 ∈ E2 } est convexe.

3.2 Enveloppe convexe

Définition
Soit E ⊂ IRn . L’enveloppe convexe de E, noté Co(E) ou
conv(E) est l’ensemble de toute les combinaisons convexes
d’éléments de E.
n
nX n
X o
conv(E) = λi xi tel que xi ∈ E, λi = 1, λi ∈ [0, 1] .
i=1 i=1

Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 3/20

3) Éléments d’analyse convexe

Théorème
Soit E ⊂ IRn un ensemble convexe tel que int E 6= ∅. Soit
◦
x1 ∈ cl E et x2 ∈ int E (où cl E = Ē et int E = E), alors

λx1 + (1 − λ)x2 ∈ int E, ∀λ ∈ [0, 1[.

Corollaire
E est convexe ⇒ int E est convexe.
E est convexe et int E 6= ∅ ⇒ cl(int E)=cl E.
E est convexe et int E 6= ∅ ⇒ int (cl E)=int E.
E est convexe et int E 6= ∅ ⇒ cl E est convexe.

Preuve : ex.

Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 4/20

3) Éléments d’analyse convexe

Théorème
Soit E ⊂ IRn un ensemble convexe tel que int E 6= ∅. Soit
◦
x1 ∈ cl E et x2 ∈ int E (où cl E = Ē et int E = E), alors

λx1 + (1 − λ)x2 ∈ int E, ∀λ ∈ [0, 1[.

Corollaire
E est convexe ⇒ int E est convexe.
E est convexe et int E 6= ∅ ⇒ cl(int E)=cl E.
E est convexe et int E 6= ∅ ⇒ int (cl E)=int E.
E est convexe et int E 6= ∅ ⇒ cl E est convexe.

Preuve : ex.

Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 4/20

3) Éléments d’analyse convexe

3.3) Fonction convexe

Définition
Soit f : E ⊂ IRn → IR une fonction. Supposons que E est
convexe non vide.
f est dite convexe ssi ∀x1 , x2 ∈ E, ∀λ ∈ [0, 1],

f (λx1 + (1 − λ)x2 ) ≤ λf (x1 ) + (1 − λ)f (x2 ).

f est dite concave ssi ∀x1 , x2 ∈ E, ∀λ ∈ [0, 1],

f (λx1 + (1 − λ)x2 ) ≥ λf (x1 ) + (1 − λ)f (x2 ).

f est dite strictement convexe ssi

∀x1 , x2 ∈ E, x1 6= x2 , ∀λ ∈]0, 1[,

f (λx1 + (1 − λ)x2 ) < λf (x1 ) + (1 − λ)f (x2 ).

Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 5/20
3) Éléments d’analyse convexe

f est dite strictement concave ssi

∀x1 , x2 ∈ E, x1 6= x2 , ∀λ ∈]0, 1[,

f (λx1 + (1 − λ)x2 ) > λf (x1 ) + (1 − λ)f (x2 ).

Proposition
Soit E ⊂ IRn un ensemble convexe non vide et soit
f : E → IR une fonction convexe. Alors l’ensemble de
niveaux Eα = {x ∈ E/ f (x) ≤ α} est un ensemble convexe.

Preuve :
Théorème
Soit E ⊂ IRn un ouvert convexe non vide et soit f : E → IR
une fonction convexe. Alors f est continue sur E.

Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 6/20

3) Éléments d’analyse convexe

f est dite strictement concave ssi

∀x1 , x2 ∈ E, x1 6= x2 , ∀λ ∈]0, 1[,

f (λx1 + (1 − λ)x2 ) > λf (x1 ) + (1 − λ)f (x2 ).

Proposition
Soit E ⊂ IRn un ensemble convexe non vide et soit
f : E → IR une fonction convexe. Alors l’ensemble de
niveaux Eα = {x ∈ E/ f (x) ≤ α} est un ensemble convexe.

Preuve :
Théorème
Soit E ⊂ IRn un ouvert convexe non vide et soit f : E → IR
une fonction convexe. Alors f est continue sur E.

Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 6/20

3) Éléments d’analyse convexe

3.4 Dérivée directionnelle

Définition
Soint E ⊂ IRn un ouvert non vide, f : E → IR une
application, x̄ ∈ E et d ∈ IRn tel que x̄ + λd ∈ E pour un
λ > 0 (suffisamment petit). La dérivée directionnelle de f au
point x̄ dans la direction d, notée f 0 (x̄, d) est donnée quand
elle existe par :
f (x̄ + λd) − f (x̄)
f 0 (x, d) = lim+
λ→0 λ

Proposition
f : E → IR une application convexe. Soit x̄ ∈ E et d ∈ IRn .
Alors, f 0 (x̄, d) existe et on a

f (x̄ + λd) − f (x̄)

f 0 (x, d) = inf
λ>0 λ
Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 7/20
3) Éléments d’analyse convexe

3.4 Dérivée directionnelle

Définition
Soint E ⊂ IRn un ouvert non vide, f : E → IR une
application, x̄ ∈ E et d ∈ IRn tel que x̄ + λd ∈ E pour un
λ > 0 (suffisamment petit). La dérivée directionnelle de f au
point x̄ dans la direction d, notée f 0 (x̄, d) est donnée quand
elle existe par :
f (x̄ + λd) − f (x̄)
f 0 (x, d) = lim+
λ→0 λ

Proposition
f : E → IR une application convexe. Soit x̄ ∈ E et d ∈ IRn .
Alors, f 0 (x̄, d) existe et on a

f (x̄ + λd) − f (x̄)

f 0 (x, d) = inf
λ>0 λ
Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 7/20
3) Éléments d’analyse convexe

3.5 Sous gradient, sous différentiel d’une fonction

convexe

Définition
Soit E ⊂ IRn un ouvert convexe non vide et soit f : E → IR
une fonction convexe.
On appelle sous différentielle de f en a ∈ E et on le note
∂f (a) l’ensemble défini par

∂f (a) = {x∗ ∈ E/ f (x) ≥ f (a) + x∗ T (x − a) ∀x ∈ E}

Un vecteur x∗ ∈ ∂f (a) est dit sous gradient de f en a.

Relions maintenant la notion de sous différentiel et de la

dérivée directionnelle.
Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 8/20
3) Éléments d’analyse convexe

Théorème
Soient E ⊂ IRn un ouvert convexe non vide, f : E → IR une
fonction convexe et a ∈ E. Alors on a,

∂f (a) = {x∗ ∈ E/ x∗ T d ≤ f 0 (a, d) ∀d ∈ E}

Preuve : Soit x∗ ∈ ∂f (a), d ∈ E et λ > 0/ a + λd ∈ E. Par

définition de ∂f (a),
f (a + λd) − f (a) ≥ λx∗ T d
donc f 0 (a, d) ≥ x∗ T d. Réciproquement, soit x∗ ∈ E tel que
f 0 (a, d) ≥ x∗ T d, ∀d ∈ E. Soit x ∈ E. Par hypothèse, on a
x∗ T (x − a) ≤ f 0 (a, x − a)
f (a + λ(x − a)) − f (a)
= inf
λ>0 λ
≤ f (a+(x−a))−f
1
(a)

Par conséquent x∗ ∈ ∂f (a).

Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 9/20
3) Éléments d’analyse convexe

Théorème
Soient E ⊂ IRn un ouvert convexe non vide, f : E → IR une
fonction convexe et a ∈ E. Alors on a,

∂f (a) = {x∗ ∈ E/ x∗ T d ≤ f 0 (a, d) ∀d ∈ E}

Preuve : Soit x∗ ∈ ∂f (a), d ∈ E et λ > 0/ a + λd ∈ E. Par

définition de ∂f (a),
f (a + λd) − f (a) ≥ λx∗ T d
donc f 0 (a, d) ≥ x∗ T d. Réciproquement, soit x∗ ∈ E tel que
f 0 (a, d) ≥ x∗ T d, ∀d ∈ E. Soit x ∈ E. Par hypothèse, on a
x∗ T (x − a) ≤ f 0 (a, x − a)
f (a + λ(x − a)) − f (a)
= inf
λ>0 λ
≤ f (a+(x−a))−f
1
(a)

Par conséquent x∗ ∈ ∂f (a).

Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 9/20
3) Éléments d’analyse convexe

3.6 Épigraphe d’une fonction

Définition
Soit f : E → IR une application.
L’ensemble {(x, f (x)) ∈ E × IR} est dit graphe de f .
epi f = {(x, y) ∈ E × IR/ f(x) ≤ y} est dit épigraphe de
f.

Théorème
Soit E ⊂ IRn un ens convexe non vide et soit f : E → IR une
application.
f est convexe ssi epi(f ) est convexe.

Preuve : ex

Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 10/20

3) Éléments d’analyse convexe

3.6 Épigraphe d’une fonction

Définition
Soit f : E → IR une application.
L’ensemble {(x, f (x)) ∈ E × IR} est dit graphe de f .
epi f = {(x, y) ∈ E × IR/ f(x) ≤ y} est dit épigraphe de
f.

Théorème
Soit E ⊂ IRn un ens convexe non vide et soit f : E → IR une
application.
f est convexe ssi epi(f ) est convexe.

Preuve : ex

Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 10/20

3) Éléments d’analyse convexe

Théorème
Soit E ⊂ IRn un ens convexe non vide et soit f : E → IR une
application. Si pour tout x̄ ∈ E, il existe un vecteur sous
gradient x∗ ∈ IRn de f en x̄

(i.e. f (x) ≥ f (x̄) + x∗ T (x − x̄) ∀x ∈ E),

alors f est convexe sur int E.

Preuve: Soit x1 , x2 ∈int E et soit λ ∈ [0, 1].On a int E est

convexe donc λx1 + (1 − λ)x2 ∈ int E. Par hypothèse on a
f (x1 ) ≥ f (λx1 + (1 − λ)x2 ) + (1 − λ)x∗ T (x1 − x2 )
f (x2 ) ≥ f (λx1 + (1 − λ)x2 ) + (1 − λ)x∗ T (x2 − x1 ). D’où

λf (x1 ) + (1 − λ)f (x2 ) ≥ f (λx1 + (1 − λ)x2 ).

Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 11/20

3) Éléments d’analyse convexe

Théorème
Soit E ⊂ IRn un ens convexe non vide et soit f : E → IR une
application. Si pour tout x̄ ∈ E, il existe un vecteur sous
gradient x∗ ∈ IRn de f en x̄

(i.e. f (x) ≥ f (x̄) + x∗ T (x − x̄) ∀x ∈ E),

alors f est convexe sur int E.

Preuve: Soit x1 , x2 ∈int E et soit λ ∈ [0, 1].On a int E est

convexe donc λx1 + (1 − λ)x2 ∈ int E. Par hypothèse on a
f (x1 ) ≥ f (λx1 + (1 − λ)x2 ) + (1 − λ)x∗ T (x1 − x2 )
f (x2 ) ≥ f (λx1 + (1 − λ)x2 ) + (1 − λ)x∗ T (x2 − x1 ). D’où

λf (x1 ) + (1 − λ)f (x2 ) ≥ f (λx1 + (1 − λ)x2 ).

Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 11/20

3) Éléments d’analyse convexe

Théorème
Soit E ⊂ IRn un ens convexe non vide et soit f : E → IR une
application. Si pour tout x̄ ∈ E, il existe un vecteur sous
gradient x∗ ∈ IRn de f en x̄

(i.e. f (x) ≥ f (x̄) + x∗ T (x − x̄) ∀x ∈ E),

alors f est convexe sur int E.

Preuve: Soit x1 , x2 ∈int E et soit λ ∈ [0, 1].On a int E est

convexe donc λx1 + (1 − λ)x2 ∈ int E. Par hypothèse on a
f (x1 ) ≥ f (λx1 + (1 − λ)x2 ) + (1 − λ)x∗ T (x1 − x2 )
f (x2 ) ≥ f (λx1 + (1 − λ)x2 ) + (1 − λ)x∗ T (x2 − x1 ). D’où

λf (x1 ) + (1 − λ)f (x2 ) ≥ f (λx1 + (1 − λ)x2 ).

Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 11/20

3) Éléments d’analyse convexe

3.7 Fonction différentiable

Définition
Soit E ⊂ IRn un ens non vide et soit f : E → IR une
application. f est dite différentiable au point x̄ ∈ int E
s’il existe un vecteur noté ∇f (x) appelé vecteur gradient
de f au point x̄ et une fonction α : IRn → IR t.q

∀x ∈ E, f (x) = f (x̄) + ∇f (x̄)T (x − x̄) + kx − x̄kα(x)

où lim α(x) = 0.
x→x̄
Si f est diff au point x̄, alors le vecteur gradient ! est
∂f ∂f
unique et on a ∇f (x̄) = (x̄), ..., (x̄)
∂x1 ∂xn
f est dite diff sur l’ouvert E 0 ⊂ E si f est diff en tout
point de E 0 .
Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 12/20
3) Éléments d’analyse convexe

3.7 Fonction différentiable

Définition
Soit E ⊂ IRn un ens non vide et soit f : E → IR une
application. f est dite différentiable au point x̄ ∈ int E
s’il existe un vecteur noté ∇f (x) appelé vecteur gradient
de f au point x̄ et une fonction α : IRn → IR t.q

∀x ∈ E, f (x) = f (x̄) + ∇f (x̄)T (x − x̄) + kx − x̄kα(x)

où lim α(x) = 0.
x→x̄
Si f est diff au point x̄, alors le vecteur gradient ! est
∂f ∂f
unique et on a ∇f (x̄) = (x̄), ..., (x̄)
∂x1 ∂xn
f est dite diff sur l’ouvert E 0 ⊂ E si f est diff en tout
point de E 0 .
Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 12/20
3) Éléments d’analyse convexe

3.7 Fonction différentiable

Définition
Soit E ⊂ IRn un ens non vide et soit f : E → IR une
application. f est dite différentiable au point x̄ ∈ int E
s’il existe un vecteur noté ∇f (x) appelé vecteur gradient
de f au point x̄ et une fonction α : IRn → IR t.q

∀x ∈ E, f (x) = f (x̄) + ∇f (x̄)T (x − x̄) + kx − x̄kα(x)

où lim α(x) = 0.
x→x̄
Si f est diff au point x̄, alors le vecteur gradient ! est
∂f ∂f
unique et on a ∇f (x̄) = (x̄), ..., (x̄)
∂x1 ∂xn
f est dite diff sur l’ouvert E 0 ⊂ E si f est diff en tout
point de E 0 .
Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 12/20
3) Éléments d’analyse convexe

Corollaire
Soit f : E ⊂ IRn → IR une application diff en x ∈ E. Alors
f 0 (x, d) existe et on a f 0 (x, d) = ∇f (x)T d.

Théorème
Soit f une fonction diff définie sur un ouvert convexe E de
IRn . Alors, f est convexe ssi

∀(x, y) ∈ E × E, f (y) − f (x) ≥ ∇f (x)T (y − x)

Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 13/20

3) Éléments d’analyse convexe

Corollaire
Soit f : E ⊂ IRn → IR une application diff en x ∈ E. Alors
f 0 (x, d) existe et on a f 0 (x, d) = ∇f (x)T d.

Théorème
Soit f une fonction diff définie sur un ouvert convexe E de
IRn . Alors, f est convexe ssi

∀(x, y) ∈ E × E, f (y) − f (x) ≥ ∇f (x)T (y − x)

Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 13/20

3) Éléments d’analyse convexe

Preuve Supposons que f est convexe.

∀x, y ∈ E, ∀λ ∈ [0, 1], f (λy+(1−λx)) ≤ λf (y)+(1−λ)f (x).
f (x + λ(y − x)) − f (x) ≤ λ(f (y) − f (x))
ce qui implique que
f (x + λ(y − x)) − f (x)
f (y) − f (x) ≥ .
λ
On a le résultat en tendant λ → 0. Réciproquement, soit
x, y ∈ E. S est convexe, donc λx1 + (1 − λ)y ∈ E. Par
hypothèse on a,
(1) f (y) − f (λx + (1 − λ)y) ≥ λ∇f (λx + (1 − λ)y)T (y − x)
(2)
f (x) − f (λx + (1 − λ)y) ≥ (1 − λ)∇f (λx + (1 − λ)y))T (x − y)
En multipliant (1) par (1 − λ) et (2) par λ et en sommant on
trouve
λf (x) + (1 − λ)f (y) ≥ f (λx + (1 − λ)y).
Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 14/20
3) Éléments d’analyse convexe

Preuve Supposons que f est convexe.

∀x, y ∈ E, ∀λ ∈ [0, 1], f (λy+(1−λx)) ≤ λf (y)+(1−λ)f (x).
f (x + λ(y − x)) − f (x) ≤ λ(f (y) − f (x))
ce qui implique que
f (x + λ(y − x)) − f (x)
f (y) − f (x) ≥ .
λ
On a le résultat en tendant λ → 0. Réciproquement, soit
x, y ∈ E. S est convexe, donc λx1 + (1 − λ)y ∈ E. Par
hypothèse on a,
(1) f (y) − f (λx + (1 − λ)y) ≥ λ∇f (λx + (1 − λ)y)T (y − x)
(2)
f (x) − f (λx + (1 − λ)y) ≥ (1 − λ)∇f (λx + (1 − λ)y))T (x − y)
En multipliant (1) par (1 − λ) et (2) par λ et en sommant on
trouve
λf (x) + (1 − λ)f (y) ≥ f (λx + (1 − λ)y).
Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 14/20
3) Éléments d’analyse convexe

Théorème
Soit E ⊂ IRn un ensemble convexe non vide et soit
f : E → IR une app convexe.
Si f est différentiable au point x̄ ∈ int E, alors

∂f (x̄) = {∇f (x̄)}

Théorème
Soit E ⊂ IRn un ouvert convexe non vide et soit f : E → IR
une app diff sur E. Alors
f est convexe ssi
∀x1 , x2 ∈ E, (∇f (x2 ) − ∇f (x1 ))T (x2 − x1 ) ≥ 0.
f est strictement convexe ssi
∀x1 , x2 ∈ E, (∇f (x2 ) − ∇f (x1 ))T (x2 − x1 ) > 0.
Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 15/20
3) Éléments d’analyse convexe

Théorème
Soit E ⊂ IRn un ensemble convexe non vide et soit
f : E → IR une app convexe.
Si f est différentiable au point x̄ ∈ int E, alors

∂f (x̄) = {∇f (x̄)}

Théorème
Soit E ⊂ IRn un ouvert convexe non vide et soit f : E → IR
une app diff sur E. Alors
f est convexe ssi
∀x1 , x2 ∈ E, (∇f (x2 ) − ∇f (x1 ))T (x2 − x1 ) ≥ 0.
f est strictement convexe ssi
∀x1 , x2 ∈ E, (∇f (x2 ) − ∇f (x1 ))T (x2 − x1 ) > 0.
Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 15/20
3) Éléments d’analyse convexe

Preuve : Supposons que f est convexe. ∀x1 , x2 ∈ E, on a

f (x1 ) ≥ f (x2 ) + ∇f (x2 )T (x1 − x2 )

f (x2 ) ≥ f (x1 ) + ∇f (x1 )T (x2 − x1 ).

En sommant,

f (x1 )+f (x2 ) ≥ f (x2 )+f (x1 )+(∇f (x1 )T −∇f (x2 )T )(x2 −x1 ).

càd (∇f (x1 )T − ∇f (x2 )T )(x1 − x2 ) ≥ 0. Inversement,

supposons que (∗) est vérifiée. Soit x1 , x2 ∈ E. Il existe alors
x = λx1 + (1 − λx2 ), λ ∈]0, 1[ tel que

f (x2 ) − f (x1 ) = ∇f (x)T (x2 − x1 ).

Par hypothèse, on a (∇f (x) − ∇f (x1 ))T (x − x1 ) ≥ 0. Donc,

(1 − λ)(∇f (x) − ∇f (x1 ))T (x2 − x1 ) ≥ 0, d’où
∇f (x)T (x2 − x1 ) ≥ ∇f (x1 )T (x2 − x1 ). Par conséquent,
f (x2 ) − f (x1 ) ≥ ∇f (x1 )T (x2 − x1 ). D’où f est convexe
Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 16/20
3) Éléments d’analyse convexe

Preuve : Supposons que f est convexe. ∀x1 , x2 ∈ E, on a

f (x1 ) ≥ f (x2 ) + ∇f (x2 )T (x1 − x2 )

f (x2 ) ≥ f (x1 ) + ∇f (x1 )T (x2 − x1 ).

En sommant,

f (x1 )+f (x2 ) ≥ f (x2 )+f (x1 )+(∇f (x1 )T −∇f (x2 )T )(x2 −x1 ).

càd (∇f (x1 )T − ∇f (x2 )T )(x1 − x2 ) ≥ 0. Inversement,

supposons que (∗) est vérifiée. Soit x1 , x2 ∈ E. Il existe alors
x = λx1 + (1 − λx2 ), λ ∈]0, 1[ tel que

f (x2 ) − f (x1 ) = ∇f (x)T (x2 − x1 ).

Par hypothèse, on a (∇f (x) − ∇f (x1 ))T (x − x1 ) ≥ 0. Donc,

(1 − λ)(∇f (x) − ∇f (x1 ))T (x2 − x1 ) ≥ 0, d’où
∇f (x)T (x2 − x1 ) ≥ ∇f (x1 )T (x2 − x1 ). Par conséquent,
f (x2 ) − f (x1 ) ≥ ∇f (x1 )T (x2 − x1 ). D’où f est convexe
Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 16/20
3) Éléments d’analyse convexe

Preuve : Supposons que f est convexe. ∀x1 , x2 ∈ E, on a

f (x1 ) ≥ f (x2 ) + ∇f (x2 )T (x1 − x2 )

f (x2 ) ≥ f (x1 ) + ∇f (x1 )T (x2 − x1 ).

En sommant,

f (x1 )+f (x2 ) ≥ f (x2 )+f (x1 )+(∇f (x1 )T −∇f (x2 )T )(x2 −x1 ).

càd (∇f (x1 )T − ∇f (x2 )T )(x1 − x2 ) ≥ 0. Inversement,

supposons que (∗) est vérifiée. Soit x1 , x2 ∈ E. Il existe alors
x = λx1 + (1 − λx2 ), λ ∈]0, 1[ tel que

f (x2 ) − f (x1 ) = ∇f (x)T (x2 − x1 ).

Par hypothèse, on a (∇f (x) − ∇f (x1 ))T (x − x1 ) ≥ 0. Donc,

(1 − λ)(∇f (x) − ∇f (x1 ))T (x2 − x1 ) ≥ 0, d’où
∇f (x)T (x2 − x1 ) ≥ ∇f (x1 )T (x2 − x1 ). Par conséquent,
f (x2 ) − f (x1 ) ≥ ∇f (x1 )T (x2 − x1 ). D’où f est convexe
Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 16/20
3) Éléments d’analyse convexe

3.8 Fonction 2 fois différentiable

Définition
Soit E ⊂ IRn , f : E → IR une app et x̄ ∈ int E.
On dit que f est 2 fois diiff en x̄ s’il existe un vecteur
∇f (x̄) ∈ IRn , une matrice carré H(x̄) d’ordre n appelée
le hessien de f au point x̄ et α : IRn → IR tq ∀x ∈ E,
1
f (x) = f (x̄) + ∇f (x̄)T (x − x̄) + (x − x̄)T H(x̄)(x −
2
x̄) + kx − x̄k2 α(x), où lim α(x) = 0.
x→x̄
f est dite 2 fois diff sur l’ouvert E 0 ⊂ E si f est diff en
tout point de E 0 .
!
∂ 2f
H(x̄) =
∂xi ∂xj i,j=1,...,n

Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 17/20

3) Éléments d’analyse convexe

Exemple
f (x1 , x2 ) = 2x1 + 6x2 − 2x21 − 3x22 + 4x1 x2 .
f est 2 fois diff au point (0, 0).

Théorème
Soit E ⊂ IRn un ouvert convexe non vide et soit f : E → IR
une app 2 fois diff sur E. f est convexe ssi ∀x̄ ∈ E, H(x̄) est
semi défini positif. i.e.

xT H(x̄)x ≥ 0 ∀x ∈ IRn .

Preuve: Supposons f convexe. montrons que

∀x̄ ∈ E, xT H(x̄)x ≥ 0, ∀x ∈ IRn . En effet, ∀x ∈ IRn il existe
λ suffisamment petit tel que x̄ + λx ∈ E

f (x̄ + λx) ≥ f (x̄) + λ∇f (x̄)T x

Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 18/20
3) Éléments d’analyse convexe

Exemple
f (x1 , x2 ) = 2x1 + 6x2 − 2x21 − 3x22 + 4x1 x2 .
f est 2 fois diff au point (0, 0).

Théorème
Soit E ⊂ IRn un ouvert convexe non vide et soit f : E → IR
une app 2 fois diff sur E. f est convexe ssi ∀x̄ ∈ E, H(x̄) est
semi défini positif. i.e.

xT H(x̄)x ≥ 0 ∀x ∈ IRn .

Preuve: Supposons f convexe. montrons que

∀x̄ ∈ E, xT H(x̄)x ≥ 0, ∀x ∈ IRn . En effet, ∀x ∈ IRn il existe
λ suffisamment petit tel que x̄ + λx ∈ E

f (x̄ + λx) ≥ f (x̄) + λ∇f (x̄)T x

Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 18/20
3) Éléments d’analyse convexe

D’autre part, f (x̄ + λx) =

f (x̄) + λ∇f (x̄)T x + 12 λ2 xT H(x̄)x + λ2 kxk2 α(x̄ + λx). Donc

1 2 T
λ x H(x̄)x + λ2 kxk2 α(x̄ + λx) ≥ 0.
2
En simplifiant par λ2 et en tendant λ → 0, on obtient
xT H(x̄)x ≥ 0, ∀x ∈ IRn . Inversement, supposons le hessien
est semi-défini positif. Soit x, x̄ ∈ E
1
f (x) = f (x̄) + ∇f (x̄)T (x − x̄) + (x − x̄)T H(x̂)(x − x̄)
2
où x̂ = λx + (1 − λ)x̄, pour un λ ∈]0, 1[. puisque x̂ ∈ E et
H(x̂) est semi-défini positif, donc (x − x̄)T H(x̂)(x − x̄) ≥ 0.
D’où f (x) ≥ f (x̄) + ∇f (x̄)T (x − x̄).

Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 19/20

3) Éléments d’analyse convexe

D’autre part, f (x̄ + λx) =

f (x̄) + λ∇f (x̄)T x + 12 λ2 xT H(x̄)x + λ2 kxk2 α(x̄ + λx). Donc

1 2 T
λ x H(x̄)x + λ2 kxk2 α(x̄ + λx) ≥ 0.
2
En simplifiant par λ2 et en tendant λ → 0, on obtient
xT H(x̄)x ≥ 0, ∀x ∈ IRn . Inversement, supposons le hessien
est semi-défini positif. Soit x, x̄ ∈ E
1
f (x) = f (x̄) + ∇f (x̄)T (x − x̄) + (x − x̄)T H(x̂)(x − x̄)
2
où x̂ = λx + (1 − λ)x̄, pour un λ ∈]0, 1[. puisque x̂ ∈ E et
H(x̂) est semi-défini positif, donc (x − x̄)T H(x̂)(x − x̄) ≥ 0.
D’où f (x) ≥ f (x̄) + ∇f (x̄)T (x − x̄).

Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 19/20

3) Éléments d’analyse convexe

D’autre part, f (x̄ + λx) =

f (x̄) + λ∇f (x̄)T x + 12 λ2 xT H(x̄)x + λ2 kxk2 α(x̄ + λx). Donc

1 2 T
λ x H(x̄)x + λ2 kxk2 α(x̄ + λx) ≥ 0.
2
En simplifiant par λ2 et en tendant λ → 0, on obtient
xT H(x̄)x ≥ 0, ∀x ∈ IRn . Inversement, supposons le hessien
est semi-défini positif. Soit x, x̄ ∈ E
1
f (x) = f (x̄) + ∇f (x̄)T (x − x̄) + (x − x̄)T H(x̂)(x − x̄)
2
où x̂ = λx + (1 − λ)x̄, pour un λ ∈]0, 1[. puisque x̂ ∈ E et
H(x̂) est semi-défini positif, donc (x − x̄)T H(x̂)(x − x̄) ≥ 0.
D’où f (x) ≥ f (x̄) + ∇f (x̄)T (x − x̄).

Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 19/20

3) Éléments d’analyse convexe

Théorème
Soit E ⊂ IRn un ouvert non vide et soit f : E → IR une
application 2 fois diff sur E. Alors,
Si ∀x̄ ∈ E, H(x̄) est défini positif (i.e.
∀x̄ ∈ E, xT H(x̄)x > 0, ∀x ∈ IRn∗ ), alors f est strictement
convexe.

Zakia ANKHILI Chapitre 2 Cours d’optimisation ENSA (Marrakech) 2015/2016 20/20