2. FONCTIONS S.C.I. À VALEURS DANS R ∪ {+∞}
163
Proposition 6.17 Dans le problème d’optimisation (P) (ou (Q)), tout point
admissible est minimiseur local. Démonstration. Nous la faisons dans le cas
du problème (P). Les deux ingrédients essentiels sont la semicontinuité
inférieure de f : A → f (A) = rang de A et le fait que f ne puisse prendre
qu’un nombre fini de valeurs.
Soit donc A ∈ C . Puisque f est s.c.i. en A,
lim inf
B→ A
f (B) ≥ f (A).
D’une manière détaillée, pour tout ε > 0, il existe un voisinage V de A tel
que
f (B) ≥ f (A) − ε pour tout B ∈ V.
(6.42)
Choisissons ε < 1, disons ε = 1/2. Puisque f ne peut prendre que des
valeurs entières allant de 0 à p := min(m, n), nous déduisons de (6.42) :
f (B) ≥ f (A) pour tout B ∈ V ∩ C .
Ainsi, A est un minimiseur local de f sur C .
Qu’il y ait un ensemble-contrainte ou pas dans le problème (P) ou (Q)
n’affecte en rien le résultat de la Proposition 6.17.
Il a été vu à la fin du Chapitre 5 (Exercices 3 et 4) que des relaxations convexes
de la fonction de comptage et de la fonction rang peuvent être explicitées.
Questions naturelles à présent : à quoi ressemblent les sous-différentiels généralisés de la fonction de comptage et de la fonction rang ? Nous fournissons
la réponse pour la fonction de comptage seulement, mais elle est du même
tonneau pour la fonction rang.
Théorème 6.18 Les sous-différentiels généralisés de la fonction de comptage c en x ∈ R p , au sens proximal, de Fréchet-viscosité, ou de Clarke,
coïncident tous et ont pour valeur commune
∂ c(x) =
x
∗
= (x
∗
1 , . . . , x
∗
p ) ∈ R
p
| x
∗
i = 0 pour tout i /
∈ I (x)
,
où I (x) = {i = 1, . . . , p tels que x i = 0}.
Démonstration. Elle passe par l’évaluation de quotients différentiels de la
forme
c(x +d)−c(x )
d
, pour x voisin de x, ou seulement pour x = x, évaluation
pouvant être explicitée en raison de la structure particulière de la fonction c.
163
Proposition 6.17 Dans le problème d’optimisation (P) (ou (Q)), tout point
admissible est minimiseur local. Démonstration. Nous la faisons dans le cas
du problème (P). Les deux ingrédients essentiels sont la semicontinuité
inférieure de f : A → f (A) = rang de A et le fait que f ne puisse prendre
qu’un nombre fini de valeurs.
Soit donc A ∈ C . Puisque f est s.c.i. en A,
lim inf
B→ A
f (B) ≥ f (A).
D’une manière détaillée, pour tout ε > 0, il existe un voisinage V de A tel
que
f (B) ≥ f (A) − ε pour tout B ∈ V.
(6.42)
Choisissons ε < 1, disons ε = 1/2. Puisque f ne peut prendre que des
valeurs entières allant de 0 à p := min(m, n), nous déduisons de (6.42) :
f (B) ≥ f (A) pour tout B ∈ V ∩ C .
Ainsi, A est un minimiseur local de f sur C .
Qu’il y ait un ensemble-contrainte ou pas dans le problème (P) ou (Q)
n’affecte en rien le résultat de la Proposition 6.17.
Il a été vu à la fin du Chapitre 5 (Exercices 3 et 4) que des relaxations convexes
de la fonction de comptage et de la fonction rang peuvent être explicitées.
Questions naturelles à présent : à quoi ressemblent les sous-différentiels généralisés de la fonction de comptage et de la fonction rang ? Nous fournissons
la réponse pour la fonction de comptage seulement, mais elle est du même
tonneau pour la fonction rang.
Théorème 6.18 Les sous-différentiels généralisés de la fonction de comptage c en x ∈ R p , au sens proximal, de Fréchet-viscosité, ou de Clarke,
coïncident tous et ont pour valeur commune
∂ c(x) =
x
∗
= (x
∗
1 , . . . , x
∗
p ) ∈ R
p
| x
∗
i = 0 pour tout i /
∈ I (x)
,
où I (x) = {i = 1, . . . , p tels que x i = 0}.
Démonstration. Elle passe par l’évaluation de quotients différentiels de la
forme
c(x +d)−c(x )
d
, pour x voisin de x, ou seulement pour x = x, évaluation
pouvant être explicitée en raison de la structure particulière de la fonction c.