ENSAE Optimisation différentiable

Examen du cours d’optimisation différentiable

Durée : 2 heures
Les documents ainsi que les calculatrices ne sont pas autorisés.
**********************

Exercice 0.1 (transformée de Fenchel)

Soit φ : Rd → R. La transformée de Fenchel de φ est définie pour tout u ∈ Rd par

φ∗ (u) = sup u, v − φ(v) .

v∈Rd

1. Calculer la transformée de Fenchel de φ(v) = (1/2) kvk22 où kvk2 est la norme `d2 de v ∈ Rd .
2. On considère la fonction suivante : pour tout v = (vj )dj=1 ∈ Rd ,
d
X
φ(v) = exp(vj ).
j=1

2.1 Calculer la transformée φ∗ de φ en tout point u = (uj )dj=1 ∈ Rd où uj > 0 pour

j = 1, . . . , d.
2.2 Calculer ∇φ∗ (u) en tout point u = (uj )dj=1 ∈ Rd où uj > 0 pour j = 1, . . . , d.
2.3 Soit u = (uj )dj=1 ∈ Rd où uj > 0 pour j = 1, . . . , d. Calculer ∇φ∗ (∇φ(u)).

**********************

Correction de l’exercice 0.1 1. Soit u ∈ Rd . On pose f (v) = u, v − φ(v) = u, v − (1/2) kvk22 . On a

∇f (v) = u − v et ∇2 f (v) = −Id ≺ 0. Donc f est strictement concave. On a donc v ∗ ∈ argmaxv∈ f (v) si et
seulement si ∇(v ∗ ) = 0 càd v ∗ = u. On obtient alors

kuk22 kuk22
φ∗ (u) = u, v ∗ − φ(v ∗ ) = u, u − = = φ(u).
2 2
2.1 Soit u ∈ Rd un vecteur à coordonnées strictement positives. On a
   
Xd d
X d
X
φ∗ (u) = sup  u, v − exp(vj ) = sup  uj vj − exp(vj ) = sup (uj vj − exp(vj )) .
v∈Rd j=1 v∈Rd j=1 j=1 vj ∈R

Par ailleurs, comme g : x ∈ R → tx − exp(x) atteint son maximum en x = log(t) dès que t > 0 et vaut en
ce point t(log(t) − 1), on a
d
X
φ∗ (u) = uj (log(uj ) − 1).
j=1

1
ENSAE Optimisation différentiable

2.2 On a pour tout u ∈ Rd à coordonnées strictement positives,

∇φ∗ (u) = (log(uj ))dj=1 .

2.3 On a alors pour tout u ∈ Rd à coordonnées strictement positives,

 
∇φ∗ (∇φ(u)) = ∇φ∗ (exp(uj ))dj=1 = (uj )dj=1 = u.

**********************

Exercice 0.2
Soit le problème d’optimisation suivant
 
min yz + y 2 + z 2 : z ≤ −1 . (1)

1. Réduire le problème de minimisation (1) à un problème de la forme

min f (t)
t∈K

où f est une fonction à valeurs réelles et

K = {t : g(t) ≤ 0}

avec g : R2 → R convexe de classe C 1 .

2. Montrer que f est convexe.
3. Montrer que la contrainte K est qualifiée.
4. Écrire le lagrangien de (P ).
5. Écrire le problème dual de (P ) et le résoudre.
6. Écrire les conditions KKT de (P ) et résoudre (P ) à partir de ces équations.

**********************

Correction de l’exercice 0.2

1. On considère le problème suivant :
min f (t)
t∈K

où f est une fonction de R2 dans R donnée par f (y, z) = yz + y 2 + z 2 et

K = {(y, z)> ∈ R2 : g(y, z) ≤ 0}

avec g(y, z) = z + 1 convexe de classe C1

2. On a f (y, z) = (y + z/2)2 + 3z 2 /4. C’est une somme de carré de formes linéaires donc c’est une
fonction convexe.
3. Il n’a y qu’une contrainte d’inégalité affine et la contrainte K est non vide donc la contrainte est
qualifiée.

2
ENSAE Optimisation différentiable

4. Le Lagrangien de (P ) est donné pour tout (y, z)> ∈ R2 et λ ≥ 0 par

L((y, z), λ) = f (y, z) + λg(y, z) = yz + y 2 + z 2 + λ(z + 1).

5. Le problème dual est

−λ2
sup d(λ) où d(λ) = min L(t, λ) = +λ
λ≥0 t∈R2 3
qui a pour solution λ∗ = 3/2.
6. On rappelle que (y ∗ , z ∗ , λ∗ )> ∈ R3 vérifient les conditions KKT du problème (2) quand
(a) (y ∗ , z ∗ )> ∈ K, λ∗ ≥ 0,
(b) ∇(y,z) L((y ∗ , z ∗ ), λ∗ ) = 0,
(c) λ∗ g(y ∗ , z ∗ ) = 0.
Le problème (2) est un problème d’OCD donc (y ∗ , z ∗ ) est solution du problème (2) si et seulement si il
existe λ∗ une solution du problème dual tel que (y ∗ , z ∗ , λ∗ )> ∈ R3 vérifient les conditions KKT. En résolvant
les conditions KKT, on obtient que y ∗ = 1/2 et z ∗ = −1. Donc la valeur du problème d’optimisation est
1.75 atteint en (y ∗ , z ∗ ) = (1/2, −1)> .

**********************

Exercice 0.3
Résoudre
min x21 + x22 + x23 + x24 : x1 + x2 + x3 + x4 = 1


(2)

**********************

Correction de l’exercice 0.3 La fonction de Lagrange associée à (2) est définie en tout point x =
(xj )4j=1 ∈ R4 et λ ∈ R par

L(x, λ) = x21 + x22 + x23 + x24 + λ(x1 + x2 + x3 + x4 − 1).

Le problème dual associé est

max Ψ(λ) où Ψ(λ) = inf L(x, λ).
λ∈R x∈R4

Comme x ∈ R4 → L(x, λ) est convexe et deux fois différentiable, L(·, λ) atteint son minimum sur R4 en un
point x∗ si et seulement si ∇L(x∗ , λ) = 0 càd pour 2x∗i + λ = 0 pour i = 1, 2, 3, 4. On a alors

Ψ(λ) = L((−λ/2)4i=1 , λ) = −λ2 − λ.

Ainsi Ψ est maximale en λ = −1/2.

Le problème (2) est un problème d’OCD dont la contrainte est qualifiée vue que toutes les contraintes
sont affines et la contrainte est non vide. On a donc, d’après KKT, l’équivalence entre les deux points
suivant :
1. x∗ est solution de (2)
2. il existe λ∗ solution du problème dual tel que

3
ENSAE Optimisation différentiable

i) x∗ ∈ K
ii) ∇x L(x∗ , λ∗ ) = 0
(Il n’y a pas de “complementary slackness condition” pour ce problème vu qu’il n’y a pas de contraintes
d’inégalité).
On en déduit donc que x∗ est solution de (2) si et seulement si
1. x1 + x2 + x3 + x4 = 1
2. 2x∗i + λ∗ = 0 pour i = 1, 2, 3, 4 et λ∗ = −1/2.
Ainsi l’unique solution de (2) est (1/4)4i=1 .
Rem. : On aurait pu ne pas utiliser le fait que λ∗ est solution du problème dual ici car la valeur de λ∗
aurait pu être déduite de l’équation “x1 + x2 + x3 + x4 = 1”.

**********************

Exercice 0.4 (Descente de gradient et régularisation)

Soit T fonctions linéaires f1 , . . . , fT : Rd → R et η > 0. On considère l’algorithme de descente
de gradient suivant :
at+1 = at − η∇ft (at ), ∀t = 0, . . . , T, a0 = 0.
Montrer que
T
!
X 1
aT +1 ∈ argmin ft (a) + kak22
a∈Rd 2η
t=1

où on rappelle que kak2 est la norme `d2 de a ∈ Rd définie par

 1/2
Xd
kak2 =  a2j 
j=1

et pour toute fonctions f : Rd → R, argmina∈Rd f (a) = {a ∈ Rd : f (a) ≤ f (b), ∀b ∈ Rd }.

**********************

Correction de l’exercice 0.4 On note

T
X 1
f (a) = ft (a) + kak22 .
2η
t=1

f est une fonction convexe de classe C∞ sur Rd .

Les minima de f sont les points critiques de f , càd
n o
argmin f (a) = a ∈ Rd : ∇f (a) = 0 .
a∈Rd

Par ailleurs, on a
T
X a
∇f (a) = ∇ft (a) + .
η
t=1
On a donc a ∈ argmina∈Rd f (a) si et seulement si
T
X
a = −η ∇ft (a).
t=1

4
ENSAE Optimisation différentiable

De plus, les fonctions ft , t = 1, . . . , T sont linéaires, on a ft (a) = gt , a pour un certain gt , on obtient que
a ∈ argmina∈Rd f (a) si et seulement si
T
X T
X
a = −η ∇ft (a) = −η gt .
t=1 t=1

Par ailleurs, l’algorithme de descente de gradient pour des fonctions linéaires est tel que
T
X
aT +1 = aT − η∇fT (aT ) = aT − ηgT = −η gt
t=1

car a0 = 0.