136
CHAPITRE 5 DUALISATION, CAS NON CONVEXES
co S
r
k =
M ∈ M m,n (R) | M ∗ ≤ k r et M sp ≤ r
.
Hint : Utiliser une décomposition en valeurs singulières de M.
Exercice 3 (Relaxation convexe de la fonction de comptage)
Soit c : x = (x 1 , . . . , x n ) ∈ R n → c(x) := nombre de i tels que x i = 0.
1) Lister toutes les propriétés de c que vous connaissez.
2) Pour r > 0, on pose :
c r (x) :=
c(x) si x ∞ ≤ r,
+∞ sinon.
Montrer que la relaxation convexe co c r de c r s’exprime comme suit :
(co c r ) (x) :=
1
r x 1 si x ∞ ≤ r,
+∞ sinon.
Exercice 4 (Relaxation convexe de la fonction rang)
Pour r > 0, on définit rang r : M m,n (R) → R de la manière suivante :
rang r (M) :=
rang de M si M sp ≤ r,
+∞ sinon.
Montrer que la relaxation convexe co (rang r ) de la fonction rang r s’évalue
comme suit :
co (rang r ) (M) =
1
r M ∗ si M sp ≤ r,
+∞ sinon.
Hint : On peut utiliser le résultat démontré en Exercice 2.
Exercice 5 (Dualisation de la notion de copositivité d’une matrice)
A ∈ S n (R) est dite copositive lorsque Ax, x ≥ 0 pour tout x ∈ R n
+ .
On considère le problème d’optimisation suivant :
(P)
Minimiser
1
2 Ax, x
x ∈ R n
+ .