TD02TUN
TD02TUN
TD02TUN
25 novembre 2021
où g, w ∈ Rd et µ > 0.
2 TD 02 Optim. - 2021/2022
Une telle distinction provient généralement d’une disparité dans les données entre deux populations
(par exemple entre hommes et femmes, ou entre deux générations).
Pour chacun des groupes, on souhaite construire un modèle linéaire qui explique les données,
c’est-à-dire que l’on recherche un vecteur w1 ∈ Rd tel que X 1 w1 ≈ y 1 et un vecteur w2 ∈ Rd tel
que X 2 w2 ≈ y 2 . On peut parfois souhaiter que les deux modèles obtenus diffèrent le moins possible
l’un de l’autre, c’est-à-dire que w1 ≈ w2 . Ces considérations conduisent au problème d’optimisation
suivant :
1 1 λ
min kX 1 w1 − y 1 k22 + kX 2 w2 − y 2 k22 + kw1 − w2 k22 , (3)
w1 ∈R ,w2 ∈R 2
d d 2 2
où λ ≥ 0.
TD 02 Optim. - 2021/2022 3
w1
a) En posant w := ∈ R2d , la fonction objectif du problème (3) peut se réécrire sous la
w2
forme
T
XT XT
1 1 X 1 + λI −λI 1y 1
f (w) := wT w+ w + (y T y + yT
2 y 2 ),
2 −λI XT
2 X 2 + λI XT
2y 2 1 1
w∗
b) En observant la valeur de l’objectif en ∗ , on voit que
z =0
∗
w 1
f = kXw∗ + z ∗ e − yk2
z∗ 2
1
= kXw∗ − yk2
2
= 0.
w∗
Par conséquent, le point conduit à une valeur de l’objectif nulle. Comme
0
w 1
f = kXw + ze − yk2 ≥ 0,
z 2
w∗
pour tous w ∈ Rd et z ∈ R, le point est un minimum global du problème.
0
Solutions de l’exercice 2
But de l’exercice : revoir les définitions d’argument minimal, identifier des solutions évidentes
2
1
b) Si on développe l’expression
v − w − µ1 g
, on obtient
2 2
2 T
2
1
v − w − 1 g
= 1 v T (Id )v + 1 g − w
1
1
v +
w − g
,
2
µ
2 2 µ 2 µ
où le dernier terme ne dépend pas de v. Comme µ > 0, on applique le même argument qu’en
question a) (avec cette fois a = µ et b = 12 kw − µ1 gk2 ), et on obtient
µ
argmin ϕ(v) = argmin v T (Id )v + (g − µw)T v
v∈Rd v∈Rd 2
1 1
= argmin v T (Id )v + ( g − w)T v
v∈Rd 2 µ
2
1
1
= argmin
v − w − g
.
v∈Rd 2 µ
On en conclut que ce problème (et, par conséquent, la fonction ϕ) admet une unique solution
donnée par v ∗ = w − µ1 g.
Solutions de l’exercice 3
a) En reformulant l’objectif de la question (3), on obtient une fonction quadratique en les coor-
données de w : le problème est donc un problème d’optimisation quadratique.
6 TD 02 Optim. - 2021/2022
b) La matrice définissant la partie quadratique de la fonction f est symétrique. On sait alors que la
condition d’optimalité au premier ordre s’écrit
T T
X 1 X 1 + λI −λI X1 y
∇f (w) = T w+ = 0.
−λI X 2 X 2 + λI XT2y
c) On utilisera ci-dessous la notation générique f (w) mais en considérant toujours le cas particulier
λ = 0.
Il s’agit donc d’une somme de deux termes de moindres carrés linéaires dépendant chacun de
composantes différentes du vecteur w. Le terme 21 kX 1 w1 − y 1 k2 ne dépend que de w1 et
est une fonction convexe de w1 , donc de w également. De même, le terme 12 kX 2 w2 − y 2 k2
ne dépend que de w2 et est une fonction convexe de w2 , donc de w. Par conséquent,
la fonction objectif est une fonction convexe de w. Remarque : Un tel problème est dit
partiellement séparable car on peut dissocier deux groupes de variables.
ii) Le vecteur " #
∗ X †1 y 1
w =
X †2 y 2
est une solution de ce problème. En effet, les vecteurs w∗1 := X †1 y 1 et w∗2 := X †2 y 2 sont
respectivement solutions de
1 1
minimiser kX 1 w1 − y 1 k2 et minimiser kX 2 w2 − y 2 k2 .
w1 ∈Rd 2 w2 ∈Rd 2
v
Par conséquent, pour tout v = 1 ∈ R2d , on a :
v2
1 1 1 1
kX 1 v 1 − y 1 k2 ≥ kX 1 w∗1 − y 1 k2 et kX 2 v 2 − y 2 k2 ≥ kX 2 w∗2 − y 2 k2
2 2 2 2
par définition de w∗1 et w∗2 . Il en résulte que
1 1 1 1
f (v) = kX 1 v 1 − y 1 k2 + kX 2 v 2 − y 2 k2 ≥ kX 1 w∗1 − y 1 k2 + kX 2 w∗2 − y 2 k2 = f (w∗ ),
2 2 2 2
ce qui montre bien que w∗ est une solution du problème.