VII.3. La convexification d’une fonction
** Probl` eme VII.27. Minimisation de différences de fonctions convexes
Soient g et h deux fonctions convexes de R n dans R et on considère le
problème d’optimisation suivant :
(P)
Minimiser f (x) := g(x) − h(x) sur R
n .
1 ◦ ) Comment trouver une décomposition de f sous la forme f = ˜
g − ˜
h, où
˜
g et ˜
h sont toutes les deux fortement convexes ?
2 ◦ ) Pour cette question et la suivante, on fait l’hypothèse (H 1 ) ci-dessous :
(H 1 )
{x ∈ R
n : g(x) − h(x) r} est borné pour tout r ∈ R.
a) Indiquer brièvement pourquoi le problème (P) a au moins une solution.
Cette solution est-elle unique ?
b) On dit que x est un point T-critique de (P) lorsque ∂g(x) ∩ ∂h(x) = ∅.
Montrer que toute solution de (P) est un point T-critique de (P).
3 ◦ ) Dans cette question, on suppose de plus
(H 2 )
g et h sont fortement convexes sur R
n .
On considère alors l’algorithme décrit comme suit :
k = 0 : x 0 ∈ R n ;
k → k + 1 : on prend un élément quelconque s k de ∂h(x k ) et on choisit x k+1
de sorte que s k ∈ ∂g(x k+1 ).
a) Montrer que la suite {f (x k ) = g(x k ) − h(x k )} k est décroissante.
b) Montrer que les suites {x k } et {s k } sont bornées.
c) Montrer que
+∞
k=0
x k+1 − x k
2 < +∞.
d) Montrer que si ˜
x est limite d’une suite extraite de la suite {x k }, alors ˜
x
est un point T-critique de (P).
e) Soit θ : t −→ θ(t) := f [tx k+1 + (1 − t)x k ]. En supposant x k+1 = x k ,
montrer que θ est strictement décroissante sur [0,1]. En déduire que f (x k+1 ) <
f (x k ).
4 ◦ ) On considère le problème (Q) suivant (dans R n+1 ) :
(Q)
Minimiser g(x) − y
sous la contrainte : (x, y) ∈ R n × R, h(x) y.
Établir les relations existant entre les solutions et valeurs optimales de (P)
et celles de (Q).
313