Optimisation continue, Istil 2ème année

Corrigé de la feuille 2 1

Optimisation Continue
ISTIL 2ème année
Corrigé de la feuille 21

Exercice 1

Rappel
On dit qu’une fonctionnelle J de Rn vers R est α-elliptique si J est C 1 , et si

∀u, v ∈ Rn (J′ (u) − J′ (v), u − v) > αku − vk2

On dit que J est elliptique s’il existe α > 0 tel que J est α-elliptique.

1.a Soient u et v dans V. Appliquons la formule de Taylor avec reste intégral à la

fonction ϕ(t) = J(u + t(v − u)), entre t = 0 et t = 1.
Z 1
J(v) = ϕ(1) = ϕ(0) + ϕ′ (t) dt
0
Z 1
= J(u) + (J′ (u + t(v − u)), (v − u)) dt
0
= J(u) + (J′ (u), v − u) − (J′ (u), v − u)
Z 1
+ (J′ (u + t(v − u)), (v − u)) dt
0 Z 1
′
= J(u) + (J (u), v − u) − (J′ (u), v − u) dt
Z 1 0

+ (J′ (u + t(v − u)), (v − u)) dt

0 Z 1
J(v) = J(u) + (J′ (u), v − u) + (J′ (u + t(v − u)) − J′ (u), (v − u)) dt
0
Minorons le reste intégral à l’aide de la propriété d’ellipticité de J. La propriété
d’ellipticité permet de minorer l’intégrande de la manière suivante
1 ′
(J′ (u + t(v − u)) − J′ (u), (v − u)) = (J (u + t(v − u)) − J′ (u), t(v − u))
t
1
> αkt(v − u)k2
t
> αtkv − uk2
On en déduit la suite d’inégalités suivantes pour le reste intégral
Z 1 Z 1
(J′ (u + t(v − u)) − J′ (u), (v − u)) dt > αkv − uk2 t dt
0 0 2 1
t
> αkv − uk2
2 0
Z 1
α
(J′ (u + t(v − u)) − J′ (u), (v − u)) dt > kv − uk2
0 2
1 généré avec L
AT X 2ε . Tous les commentaires, compléments, insultes et remarques désobligeantes
E
sont les bienvenus à [email protected]
 Optimisation continue, Istil 2ème année
2 Corrigé de la feuille 2

α
d’où J(v) > J(u) + (J′ (u), v − u) + kv − uk2
2

1.b À la question précédente, nous avons montré que

α
J(v) > J(u) + (J′ (u), v − u) + kv − uk2
2
On en déduit que si u 6= v

J(v) > J(u) + (J′ (u), v − u)

Ceci prouve que J est strictement convexe

Rappel Soit J une fonctionnelle C 1 alors

1. J est convexe
⇐⇒ ∀u, v J(v) > J(u) + (J′ (u), v − u)
2. J est strictement convexe
⇐⇒ ∀u 6= v J(v) > J(u) + (J′ (u), v − u)

1.c Montrons que J est coercive

Rappel
On dit que J est coercive si J(v) admet une limite lorsque kvk tend vers +∞,
et si cette limite est +∞.

Appliquons l’inégalité trouvée à la question 1.a, entre un point v et un autre point

fixé, par exemple 0. On obtient ainsi
α
J(v) > J(0) + (J′ (0), v) + kvk2
2
Comme J′ (0) est continue, on a

|(J′ (0), v)| 6 Kkvk

ce qui donne −Kkvk 6 (J′ (0), v) 6 Kkvk

α α 
Ainsi J(v) > J(0) − Kkvk + kvk2 = J(0) + kvk kvk − K
2 2
et le membre de droite de cette dernière inégalité tend vers +∞. D’après le théorème
d’encadrement
lim J(v) = +∞
kvk→∞

1.d.i Comme F est un ensemble fermé, non vide, et que J est coercive, J admet un
minimum sur F, qui est atteint.

Rappel : Théorème d’existence d’un minimum

Soit F un fermé non vide de Rn , et J : F → R une fonctionnelle continue, et
 Optimisation continue, Istil 2ème année
Corrigé de la feuille 2 3

coercive si l’ensemble F est non vide.

Alors il existe au moins un élément u tel que

u∈F et J(u) = inf J(v)

v∈F

Montrons maintenant l’unicité. Supposons que le minimum de J est atteint en au

moins deux points distincts u1 et u2 . Alors pour tout λ ∈ ] 0 ; 1 [, λu1 + (1 − λu2 ) est
dans F, car F est convexe. Comme J est strictement convexe, on a l’inégalité
J(λu1 + (1 − λ)u2 ) < λJ(u1 ) + (1 − λ)J(u2 ) = min J(u)
u∈F

Ceci contredit la définition du minimum de J. On en déduit que le minimum de J est

atteint en au plus un point.

Remarque
On retrouve ainsi le résultat du cours qui dit que si J est une fonctionnelle
strictement convexe, sur un ensemble convexe, alors son minimum est atteint
en au plus un point.

1.d.ii La fonctionnelle J admet un minimum sur la partie U, qui est convexe, fermée
et non vide. On en déduit que
∀v ∈ F (J′ (u), v − u) > 0

Rappel (Théorème 3.2 du cours)

Soit J : Ω → R, où Ω est un ouvert de V, et soit K une partie convexe de
Ω. Si J est (Gâteaux) différentiable en un point u ∈ K, et si elle admet un
minimum relatif en u par rapport à K, alors

∀v ∈ K (J′ (u), v − u) > 0 (Inéquation d’Euler)

Soit v un vecteur de V. Alors on peut écrire l’inégalité trouvée pour

v′ = u + v donne 0 > (J′ (u), v)
v′ = u − v donne 0 > −(J′ (u), v)
ce qui veut dire que (J′ (u), v) = 0. Ceci étant vrai pour n’importe quel v, on a en fait
J′ (u) = 0

Remarque
On retrouve ainsi le théorème suivant du cours
Théorème 3.1
Soit Ω un ouvert de V, espace vectoriel normé, et J : Ω → R une fonc-
tionnelle ; Si J admet un extremum relatif en un point u ∈ Ω, et si J est
(Gâteaux)-différentiable en ce point, alors

J′ (u) = 0 (Équation d’Euler)

 Optimisation continue, Istil 2ème année
4 Corrigé de la feuille 2

Exercice 2
∂J
2.a Le vecteur J′ (u) admet pour coordonnées . Le calcul donne
∂vi
   
∂J ′ vi − vi−1 ′ vi+1 − vi
=ϕ −ϕ
∂vi h h

∂2J
La matrice Hessienne de J a pour coefficients . Si j 6= i, j 6= i − 1 et j 6= i + 1,
∂vi ∂vj
alors le coefficient (i, j) de la matrice Hessienne est nul. Dans les autres cas, on obtient

∂2J
    
1 ′′ vi − vi−1 ′′ vi+1 − vi−1
= ϕ +ϕ si i = j
∂vi ∂vj h h h
2
 
∂ J 1 vi+1 − vi
= − ϕ′′ si j = i + 1
∂vi ∂vj h h
2
 
∂ J 1 vi − vi−1
= − ϕ′′ si j = i − 1
∂vi ∂vj h h

2.b Notons  
1 ′′ vi+1 − vi
αi = ϕ
h h
Formellement, la matrice Hessienne de J peut se récrire de la manière suivante
α0 + α1 −α1 0 ... ... ... 0
 
..
.
 
 −α1 α1 + α1 −α1 0 
. .
 

 0 −α2 α2 + α3 −α3 . . .
.


.. .. .. .. .. .. .
 

 . . . . . . .. 

.
 

.. . .. . .. . .. . ..

 0 
..
 
 .. 
 . . −αn−2 αn−2 + αn−1 −αn−1 
0 ... ... ... 0 −αn−1 αn−1 + αn
On en déduit que
 
(α0 + α1 )w1 − α1 w2
 −α1 w1 + (α1 + α2 )w2 − α2 w3 
..
 
 
 . 
′′
 
 −αi−1 wi−1 + (αi + αi+1 )wi − αi wi+1
J (u)w =  
..

 

 . 

 −αn−2 wn−2 + (αn−1 + αn )wn−1 − αn wn 
−αn−1 wn−1 + (αn−1 + αn )wn
 
soit (J′′ (u)w, w) = (α0 + α1 )w1 − α1 w2 w1
n−1
P 
+ − αi−1 wi−1 + (αi + αi+1 )wi − αi wi+1 wi
i=2
 
+ − αn−1 wn−1 + (αn−1 + αn )wn wn
 Optimisation continue, Istil 2ème année
Corrigé de la feuille 2 5

Commençons par transformer la somme :

n−1
P 
− αi−1 wi−1 + (αi + αi+1 )wi − αi wi+1 wi
i=2
n−1
P 
= αi−1 (wi − wi−1 ) − αi (wi+1 − wi ) wi
i=2
n−1
P n−1
P
= αi−1 (wi − wi−1 )wi − αi (wi+1 − wi )wi
i=2 i=2
n−2
P n−1
P
= αi (wi+1 − wi )wi+1 − αi (wi+1 − wi )wi
i=1 i=2
n−2
αi (wi+1 − wi )2 + α1 (w2 − w1 )w2
P
=
i=2
−αn−1 (wn − wn−1 )wn−1

On obtient alors
J′′ (u)w, w = α0 w12 + α1 (w1 − w2 )w2 + αn−1 (wn − wn n − 1)wn + αn wn2


n−2
αi (wi+1 − wi )2 + α1 (w2 − w1 )w2 − αn−1 (wn − wn−1 )wn−1
P
+
i=2
n−2
αi (wi+1 − wi )2 + α0 w12 + αn wn2
P
=
i=2

Cette dernière quantité est strictement positive, si w 6= 0. On en déduit que J′′ (u)
est définie positive, donc
J est strictement convexe.

n
2.c Montrons d’abord que v ∈ Rn 7−→ |vi+1 − vi | est une norme.
P
i=0
n
• Si |vi+1 − vi | = 0, alors v1 = vn = 0, et pour tout i dans [[ 1 ; n − 1 ]],
P
i=0
vi = vi+1 , donc v = 0.
• Pour tout v ∈ Rn , et tout λ ∈ R,
n
P
kλvk = |λvi+1 − λvi |
i=0
n
P
= |λ| |vi+1 − vi |
i=0
kλvk = |λ| kvk

• Pour tout u, v ∈ Rn ,
n
P
ku + vk = |vi+1 + ui+1 − vi − ui |
i=0
Pn n
P
6 |vi+1 − vi | + |ui+1 − ui |
i=0 i=0
6 kvk + kuk

On en déduit que
n
On en déduit que v ∈ Rn 7−→ |vi+1 − vi | est une norme
P
i=0
 Optimisation continue, Istil 2ème année
6 Corrigé de la feuille 2

Montrons à présent que J1 est coercive. D’une part, on a

 
t 
 b v  6 kbk2 kvk2

t
d’où − b v > −kbk2 kvk2
Par ailleurs, d’après la propriété de ϕ
 
n n v
 
P vi+1 − vi P i+1 − vi 
h ϕ > hc  
i=0 h i=0 h 
ckvk

Comme la norme k · k et la norme k · k2 sont équivalentes, il existe α tel que

n
 
P vi+1 − vi
h ϕ > αckvk2
i=0 h

Il vient alors J1 (v) > (αc − h)kvk2

On en déduit que si h < αc, alors la fonctionnelle J1 est coercive. La fonctionnelle J1
admet donc un minimum sur Rn .
Les fonctionnelles J1 et J diffèrent d’une partie linéaire. On en déduit que J′′1 = J′′ ,
donc J1 est strictement convexe. On en déduit que le minimum de J1 est unique.

Exercice 3
3.a La matrice e est de rang 1. D’après le théorème du rang

n = dim Ker e + dim Im e = dim Ker e + 1

On en déduit que dim Ker e = n − 1, c’est à dire que 0 est valeur propre d’ordre
n − 1. La trace de e est égale à n, donc n est l’autre valeur propre de e. Un vecteur
propre associé à cette valeur propre est (1, 1, . . . , 1). Finalement,
0 est valeur propre d’ordre n − 1. Son espace propre
associé est (1, 1, . . . , 1)⊥ . n est valeur propre d’ordre
1, et son espace propre est dirigé par (1, 1, . . . , 1).

3.b Calculons chacune des composantes du gradient

1/n
!
n
∂J ∂ ∂uj 1
∂uj
=
∂uj
Π ui
i=1
1/n
= Π ui 1/n
i6=j ∂uj
=
n
Π ui 1/n uj1/n−1 = J(u)
i6=j nuj

n J(u)v
i
d’où J′ (u)v =
P
i=1 nu i

Calculons à présent les coefficients diagonaux de la Hessienne

∂2J
 
1 ∂J 1 J(u) 1 1 1 J(u)
= − J(u) = − J(u) = −
∂uj 2 nuj ∂uj nu2j (nuj )2 nu2j n2 n u2i
 Optimisation continue, Istil 2ème année
Corrigé de la feuille 2 7

Calculons enfin les coefficients extra-diagonaux de la Hessienne

∂2J
 
∂ J(u) 1 ∂J 1 1 J(u)
= = = J(u) = 2
∂uj ∂uk ∂uk nuj nuj ∂uk nuj nuk n uj uk
On en déduit l’expression suivante
P J(u)vj wk n (1 − n)J(u) v w
j j
(J′′ (u)v, w) =
P
+
k6=j n2 u j u k j=1 n 2 u2j

3.c Montrons que la Hessienne de J est positive

P J(u)wj wk n (1 − n)J(u) w w
j j
(J′′ (u)w, w) =
P
2u u
+ 2 2
k6=j n j k j=1 n u j
P J(u) n (1 − n)J(u)
2
P
= 2
vj v k + vj
k6=j n j=1 n2
J(u) t
= 2 v (e − n id ) v
n
où v est le vecteur dont la composante i est wi /ui . D’après la question 3.a, la matrice
e peut se réduire sous la forme
 
n 0 ... 0
. 
 0 0 . . . .. 

 . .
.. ... 0 
 
 ..


0 ... 0 0

On en déduit que, dans cette même base, e − n id se réduit sous la forme

 
0 0 ... 0
. .. 
−n . .

 0 . 
 . .. ..
 
 .. . . 0 


0 . . . 0 −n

Cette matrice est positive, mais pas définie positive. Cela veut dire que
J est convexe, mais pas strictement convexe.

3.d Pour montrer que j est strictement convexe sur U, il suffit de montrer que si
deux éléments w1 et w2 de U sont tels que

(J′′ (u)(w1 − w2 ), w) = 0

alors w1 = w2 . Soit w le vecteur w1 − w2 . Ce vecteur admet la décomposition ortho-

gonale suivante :
w = λ(1, 1 . . . , 1) + w′
Où w′ ∈ Ker e. De plus, comme w1 , w2 ∈ U, en sommant les composantes des
vecteurs, on a la relation suivante
n
wi′
P
0 = λn +
i=1
 Optimisation continue, Istil 2ème année
8 Corrigé de la feuille 2

1 Pn
d’où λ=− w′
n i=1 i
Il reste à calculer (J′′ (u)w, w).
t
(J′′ (u)w, w) = w (e − n id ) w
t
= w (−nw′ )
t t
= λ (1, . . . , 1) w′ + w′ w′
′ 2
= kw k

On en déduit que w′ = 0, d’où λ = 0. Ainsi, w1 = w2 , donc

j est strictement convexe.

3.e D’après le calcul effectué à la question 3.b, on a

n J(ε)v n
J(ε) P
i
J′ (ε)v =
P
= vi = J(ε)
i=1 nεi n i=1

d’où (J′ (ε), v − ε) = 0

La fonctionnelle J est strictement convexe sur le convexe U. On en déduit que
∀v 6= ε J(v) > J(ε) + J′ (ε)(v − ε) = J(ε)
Donc ε est un minimum global de J sur U. De plus, J étant strictement convexe sur
cet ensemble,
le point en lequel est atteint le minimum est unique.

3.f Soient v1 , . . . , vn des réels positifs. Notons v̄ le réel suivant

1 Pn
v̄ = vi
n i=1
Alors le vecteur u = v/v̄ appartient à U. On en déduit qu’il vérifie
J(u) > J(ε) = 1
avec égalité si et seulement si v est égal à ε. On en déduit que
!1
n
Π ui
i=1
/n > 1

!1 !1
n n
vi 1
d’où Π
i=1 v̄
/n =
(ū)n
Π vi
i=1
/n > 1

!
n n
1 P
soit Π ui
i=1
>
n i=1
ui

Le cas d’égalité se déduit immédiatement de la condition d’optimalité de J sur U

Il y a égalité dans l’inégalité, si et seulement si tous les ui sont égaux