VII.3. La convexification d’une fonction
Solution : 1 ◦ ) Preuve 1. Soit f : x −→ f (x) := max i=1,...,k s i , x . Ce que
dit (P 1 ) est que la fonction convexe (et même linéaire par morceaux) f est
minimisée en 0. Une condition nécessaire et suffisante pour qu’il en soit ainsi
est donc : 0 ∈ ∂f (0). Sachant que ∂f (0) = conv{s 1 , . . . , s k } , l’équivalence de
(P 1 ) et (P 2 ) s’ensuit.
Preuve 2 (directe).
[(P 2 ) ⇒ (P 1 )]. Il est clair que (P 2 ) implique l’égalité (pour tout x)
k
i=1
α i s i , x = 0. S’il existait x tel que max i=1,...,k s i , x < 0, on aurait (sachant que l’un au moins des α i est > 0)
k
i=1
α i s i , x < 0. D’où contradiction.
[(P 1 ) ⇒ (P 2 )]. Soit L : R k → R n définie par L(α 1 , . . . , α k ) = −
k
i=1
α i s i .
Comme L est linéaire continue, elle transforme le simplexe-unité Δ k de R k en
un (polyèdre) convexe compact L(Δ k ) de R n .
Supposons (P 2 ) fausse. Alors 0 /
∈ L(Δ k ). Nous allons, sans le dire explicitement, séparer strictement {0} et L(Δ k ). Désignons par p 0 la projection de
0 sur L(Δ k ). D’après la caractérisation de la projection d’un élément sur un
convexe fermé,
c − p 0 , 0 − p 0 = p 0 , p 0 − c 0 pour tout c ∈ L(Δ k ).
C’est notamment le cas pour c = −s i , i = 1, . . . , k. D’où
s i , p 0 − −p 0 , p 0 = − − p 0
2 < 0,
ce qui induit max i=1,...,k s i , p 0 < 0. D’où contradiction avec (P 1 ).
2 ◦ ) Les deux propositions (P 3 ) et (P 4 ) sont équivalentes.
[(P 4 ) ⇒ (P 3 )]. Supposons qu’il existe x = 0 tel que max i=1,...,k s i , x 0
et montrons qu’on arrive à une contradiction. Comme
0 =
k
i=1
α i s i , x
=
k
i=1
α i s i , x
et que tous les α i sont > 0, il s’ensuit :
s i , x = 0 pour tout i = 1, . . . , k.
277
Solution : 1 ◦ ) Preuve 1. Soit f : x −→ f (x) := max i=1,...,k s i , x . Ce que
dit (P 1 ) est que la fonction convexe (et même linéaire par morceaux) f est
minimisée en 0. Une condition nécessaire et suffisante pour qu’il en soit ainsi
est donc : 0 ∈ ∂f (0). Sachant que ∂f (0) = conv{s 1 , . . . , s k } , l’équivalence de
(P 1 ) et (P 2 ) s’ensuit.
Preuve 2 (directe).
[(P 2 ) ⇒ (P 1 )]. Il est clair que (P 2 ) implique l’égalité (pour tout x)
k
i=1
α i s i , x = 0. S’il existait x tel que max i=1,...,k s i , x < 0, on aurait (sachant que l’un au moins des α i est > 0)
k
i=1
α i s i , x < 0. D’où contradiction.
[(P 1 ) ⇒ (P 2 )]. Soit L : R k → R n définie par L(α 1 , . . . , α k ) = −
k
i=1
α i s i .
Comme L est linéaire continue, elle transforme le simplexe-unité Δ k de R k en
un (polyèdre) convexe compact L(Δ k ) de R n .
Supposons (P 2 ) fausse. Alors 0 /
∈ L(Δ k ). Nous allons, sans le dire explicitement, séparer strictement {0} et L(Δ k ). Désignons par p 0 la projection de
0 sur L(Δ k ). D’après la caractérisation de la projection d’un élément sur un
convexe fermé,
c − p 0 , 0 − p 0 = p 0 , p 0 − c 0 pour tout c ∈ L(Δ k ).
C’est notamment le cas pour c = −s i , i = 1, . . . , k. D’où
s i , p 0 − −p 0 , p 0 = − − p 0
2 < 0,
ce qui induit max i=1,...,k s i , p 0 < 0. D’où contradiction avec (P 1 ).
2 ◦ ) Les deux propositions (P 3 ) et (P 4 ) sont équivalentes.
[(P 4 ) ⇒ (P 3 )]. Supposons qu’il existe x = 0 tel que max i=1,...,k s i , x 0
et montrons qu’on arrive à une contradiction. Comme
0 =
k
i=1
α i s i , x
=
k
i=1
α i s i , x
et que tous les α i sont > 0, il s’ensuit :
s i , x = 0 pour tout i = 1, . . . , k.
277