École polytechnique APM_43035_EP

Optimisation et Contrôle

PC1 : Optimisation et convexité - Correction

Exercice 1 Optimisation en dimension finie

On considère les fonctions de R2 → R suivantes :
1 4
J1 (x, y) = (x + y 2 ), J2 (x, y) = 2|x| + y 2
4
et la fonction de R3 → R :
1 2
J3 (x, y, z) = (x + y 2 + z 2 ).
2
1. Les fonctions J1 , J2 , J3 sont-elles convexes ? Strictement convexes ? α-convexes ?
Correction :
• Soit θ ∈ [0, 1], alors en utilisant que les fonctions x 7→ x4 et y 7→ y 2 sont strictement convexes
on a :
1
(θx1 + (1 − θ)x2 )4 + (θy1 + (1 − θ)y2 )2


J1 (θx1 + (1 − θ)x2 , θy1 + (1 − θ)y2 ) =
4
1
≤ θx41 + (1 − θ)x42 + θy12 + (1 − θ)y22


4
= θJ1 (x1 , y1 ) + (1 − θ)J1 (x2 , y2 ),

avec inégalité stricte si (x1 , y1 ) ̸= (x2 , y2 ) pour θ ∈]0, 1[.

Notons qu’on aurait également pu utiliser les caractérisations avec les dérivées :
1
∂x J1 (x, y) = x3 , ∂y J1 (x, y) = y,
2
et
1
∂xx J1 (x, y) = 3x2 , ∂xy J1 (x, y) = 0, ∂yy J1 (x, y) = .
2
Donc la Hessienne s’écrit :
3x2
 
0
HJ1 (x, y) = 1 .
0 2
Cette matrice est bien symétrique positive, donc J1 est convexe.
Or on a     
1 1
HJ1 (0, y) , = 0,
0 0
et on rappelle que J1 est α-convexe est équivalent à :

⟨HJ1 (X)Y, Y ⟩ ≥ α∥Y ∥2 ,

 J
ce qui est impossible ici. Donc  α-convexe.
1 n’est pas  Il reste à déterminer si elle est strictement
x1 x2
convexe. Pour tout X1 = , X2 = on a :
y1 y2

1
⟨∇J1 (X1 ) − ∇J1 (X2 ), X1 − X2 ⟩ = (x31 − x32 )(x1 − x2 ) + (y1 − y2 )2
2
1
= (x1 − x2 )2 (x21 + x1 x2 + x22 ) + (y1 − y2 )2 ≥ 0,
2
car x21 + x1 x2 + x22 ≥ 12 (x21 + x22 ) ≥ 0 (avec égalité si et seulement si x1 = x2 = 0).
Donc la quantité ci-dessus s’annule si et seulement x1 = x2 et y1 = y2 , c’est à dire X1 = X2 .
On a donc bien J1 strictement convexe.

1
 • Soit θ ∈ [0, 1], alors en utilisant que les fonctions x 7→ |x| et y 7→ y 2 sont convexes on a :
2
J2 (θx1 + (1 − θ)x2 , θy1 + (1 − θ)y2 ) =2 |θx1 + (1 − θ)x2 | + (θy1 + (1 − θ)y2 )
≤2 (θ|x1 | + (1 − θ)|x2 |) + θy12 + (1 − θ)y22
= θJ2 (x1 , y1 ) + (1 − θ)J2 (x2 , y2 ).

Cependant cette fonction n’est pas strictement convexe (et donc fortement convexe). En effet,
choisissons y1 = y2 = y et x1 ̸= x2 avec x1 , x2 ≥ 0, pour θ ∈]0, 1[, on a :

J2 (θx1 + (1 − θ)x2 , θy1 + (1 − θ)y2 ) =2 |θx1 + (1 − θ)x2 | + y 2

=2 (θx1 + (1 − θ)x2 ) + y 2

et

θJ2 (x1 , y1 ) + (1 − θ)J2 (x2 , y2 ) =θ 2|x1 | + y 2 + (1 − θ) 2|x2 | + y 2

=2 (θx1 + (1 − θ)x2 ) + y 2 .

On a donc J2 (θx1 + (1 − θ)x2 , θy1 + (1 − θ)y2 ) = θJ2 (x1 , y1 ) + (1 − θ)J2 (x2 , y2 ) alors que
(x1 , y1 ) ̸= (x2 , y2 ).

2
2
• Commençons par remarquer que a+b 2 = 12 a2 + 12 b2 − a−b
2 , alors :
   2  2  2 !
X1 + X2 1 x1 + x2 y1 + y2 z1 + z2
J3 = + +
2 2 2 2 2
1 1
(x1 − x2 )2 + (y1 − y2 )2 + (z1 − z2 )2


= (J3 (X1 ) + J3 (X2 )) −
2 8
1 1 2
= (J3 (X1 ) + J3 (X2 )) − ∥X1 − X2 ∥2 .
2 8
La fonction est donc fortement convexe (et donc strictement convexe et convexe).
Notons qu’en utilisant les caractérisations sur les dérivées, on voit clairement que :
 
x
∇J3 (x, y, z) = y 
z

et donc :
⟨∇J3 (X1 ) − ∇J3 (X2 ), X1 − X2 ⟩ = ∥X1 − X2 ∥22
et J3 est 1-convexe (et donc strictement convexe et convexe).
2. On définit maintenant les 3 ensembles suivants :

K1 = {(x, y) ∈ R2 : x + y = 3}, K2 = {(x, y) ∈ R2 : x2 + y 2 = 1},

K3 = {(x, y, z) ∈ R3 : x + y + z = 8, x + 2y − z = 10}
Les ensembles K1 , K2 , K3 sont-ils convexes ? Fermés ? Bornés ? Non-vides ?
Correction :
• L’ensemble K1 est une droite. C’est un convexe fermé non borné.
• L’ensemble K2 est le cercle unité du plan. C’est un fermé borné mais ce n’est pas un ensemble
convexe.
• L’ensemble K3 est l’intersection de deux plans non parallèles, donc c’est une droite qui est un
convexe fermé non vide.
3. Pour i ∈ {1, 2, 3}, les problèmes

(Pi ) xi ∈ Ki , Ji (xi ) ≤ Ji (y), ∀y ∈ Ki

admettent-ils au moins une solution ? Cette solution, si elle existe, est-elle unique a priori ?
Correction : On applique le théorème 2.2.1 pour l’existence et la proposition 2.3.4 pour l’unicité.

2
 • La fonction J1 est continue, strictement convexe et est infinie à l’infinie. De plus, l’ensemble
K1 est un convexe fermé non vide. Donc il existe une unique solution au problème (P1 ).
• La fonction J2 est continue. L’ensemble K2 est fermé, borné, non vide. Alors il existe au moins
une solution au problème (P2 ). L’ensemble K2 n’est pas convexe et/ou J2 n’est pas strictement
convexe donc rien ne garantit l’unicité.
• La fonction J3 est continue, infinie à l’infinie et α-convexe (donc strictement convexe). De plus
l’ensemble K3 est un convexe fermé non vide. Donc il existe une unique solution au problème
(P3 ).

Exercice 2 Un exemple en dimension infinie

Soit Ω un ouvert de RN . Soient f ∈ L2 (Ω) et c ∈ R+ . On considère la fonctionnelle suivante :
Z Z Z
1 2 c 2
J(u) = |∇u(x)| dx + u(x) dx − f (x)u(x)dx,
2 Ω 2 Ω Ω

et on travaillera avec la norme :

Z Z  12
2 2
∥u∥ = |u(x)| dx + |∇u(x)| dx .
Ω Ω

1. Cette fonctionnelle est-elle convexe ? Strictement convexe ? Fortement convexe ?

Correction :
2
2
En notant que a+b 2 = 21 a2 + 12 b2 − a−b
2 , on a :
  Z Z
u+v J(u) + J(v) 1 2 c
J = − |∇(u − v)(x)| dx − (u − v)(x)2 dx
2 2 8 Ω 8 Ω
Z Z 
J(u) + J(v) min(1, c) 2
≤ − |∇(u − v)(x)| dx + (u − v)(x)2 dx .
2 8
| Ω {z Ω }
:=∥u−v∥2

Donc J est fortement convexe et donc également convexe et strictement convexe.

2. Calculer les dérivées directionnelles premières et secondes de J.
Correction :

Z Z Z 
J (u + tv) =J(u) + t ∇u(x) · ∇v(x)dx + c u(x)v(x)dx − f (x)v(x)dx
Ω Ω Ω
t2
Z Z 
2
+ |∇v(x)| dx + c v(x)2 dx .
2 Ω Ω

On a donc
J (u + tv) − J(u)
Z Z Z
lim = ∇u(x) · ∇v(x)dx + c u(x)v(x)dx − f (x)v(x)dx
t→0 t Ω Ω Ω

Donc J est dérivable en u suivant le vecteur v et on a :

Z Z Z
DJ(u)(v) = ∇u(x) · ∇v(x)dx + c u(x)v(x)dx − f (x)v(x)dx.
Ω Ω Ω

De la même manière on a :
Z Z
(J ′′ (u)(w), v) = ∇w(x) · ∇v(x)dx + c w(x)v(x)dx.
Ω Ω

3
 Exercice 3 Minimisation d’une énergie quadratique
Soit (V, ∥ · ∥) un espace vectoriel normé et K un convexe fermé non vide de V . Soit a(·, ·) une forme
bilinéaire symétrique et continue sur V × V , et L une forme linéaire continue sur V .
On pose J(v) = 12 a(v, v) − L(v).
1. Montrer que J est dérivable sur V et calculer J ′ (v). Que se passe-t-il si a n’est plus symétrique ?
Correction :
En utilisant la symétrie de a(·, ·) :
1 1
J(v + h) = a(v + h, v + h) − L(v + h) = J(v) + a(v, h) − L(h) + a(h, h),
2 2
comme par hypothèse a(·, ·) et L(·) sont continues sur (V, ∥ · ∥), on en déduit que J est dérivable
sur V et J ′ (v)(h) = a(v, h) − L(h).
Si a n’est plus symétrique, on obtient :
1 1
J(v + h) = J(v) + (a(v, h) + a(h, v)) − L(h) + a(h, h),
2 2
et J ′ (v)(h) = 1
2 (a(v, h) + a(h, v)) − L(h).
On suppose désormais que V est de dimension finie et que a(·, ·) est coercive sur (V, ∥ · ∥), c’est à dire :
∃ν > 0 tel que a(u, u) ≥ ν∥u∥2 , ∀u ∈ V.
2. Montrer que le problème J(u) = inf v∈K J(v) admet une unique solution.
Correction :
La coercivité de a(·, ·) implique
     
u+v 1 u+v u+v u+v
J = a , −L
2 2 2 2 2
 
1 1 1 u−v u−v 1 1
= a(u, u) + a(v, v) − a , − L(u) − L(v)
4 4 2 2 2 2 2
J(u) + J(v) 1
= − a(u − v, u − v)
2 8
J(u) + J(v) ν
≤ − ∥u − v∥2
2 8
donc J est fortement convexe et donc strictement convexe.
J est strictement convexe, donc admet au plus un minimum sur K convexe (proposition 2.3.4, p.19).
Pour montrer que J admet un minimum, commençons par vérifier que J est infinie à l’infini. Si
(vn )n≥0 est une suite de K telle que limn→+∞ ∥vn ∥ = +∞, la coercivité de a(·, ·) et la continuité
de L(·) impliquent :
1 ν
J(vn ) = a(vn , vn ) − L(vn ) ≥ ∥vn ∥2 − ∥L∥∥vn ∥,
2 2
donc limn→+∞ J(vn ) = +∞. On peut alors raisonner comme dans le théorème 2.2.1 p.15 (compacité
des fermés bornés en dimension finie) pour conclure que J admet au moins un point de minimum
dans K fermé.
Notons que puisque J est fortement convexe, on aurait également pu appliquer le théorème 2.3.9
d’existence d’un minimum dans le cas fortement convexe pour obtenir directement l’existence et
l’unicité.

Exercice 4 Approximation par moindres carrés et régularisation

On se donne m réels distincts x1 , . . . , xm , et m réels b1 , . . . , bm . On considère un espace V de dimension
finie n ≤ m, engendré par une base de fonctions réelles continues (ωj )j=1:n . On note respectivement ∥ · ∥
et (·, ·) la norme euclidienne et le produit scalaire associé, indifféremment sur Rn et Rm .
On cherche à construire une fonction ψ ∈ V telle que ψ(xi ) approche bi , i = 1, . . . , m. Plus précisément
on s’intéresse au problème d’optimisation :
m
X 2
inf |φ(xi ) − bi | . (M)
φ∈V
i=1

4
1. Écrire le problème (M) sous la forme
inf J(v), (P)
v∈Rn

avec J(v) = 21 ∥Av − b∥2 où A est une matrice m × n et b ∈ Rm .

Correction :
Pn
On cherche φ dans V , donc sous la forme φ(x) = j=1 vj ωj (x) :
m
X m X
X n
|φ(xi ) − bi |2 = | vj ωj (xi ) − bi |2 = ∥Av − b∥2
i=1 i=1 j=1

avec A = [ωj (xi )]i=1:m,j=1:n , v = (vj )j=1:n , b = (bi )i=1:m .

2. Montrer que J est dérivable sur Rn et calculer sa dérivée.
Correction :
On a :
1 1 1
J(v + h) = J(v) + (Av − b, Ah) + (Ah, Av − b) + (Ah, Ah)
2 2 2
T T 1
= J(v) + (A Av − A b, h) + (Ah, Ah) (1)
2
Or |(Ah, Ah)| ≤ ∥A∥2 ∥h∥2 , donc (Ah, Ah) = o(h). Ceci montre que J est dérivable sur Rn et que
J ′ (v)(h) = (AT Av − AT b, h).
3. Montrer que J est convexe. À quelle condition J est-elle strictement convexe ?
Correction :
D’après (1), J(w) = J(v) + J ′ (v)(w − v) + 21 ∥A(w − v)∥2 ≥ J(v) + J ′ (v)(w − v), ∀v, w ∈ Rn . Donc
J est convexe.
J est strictement convexe si et seulement si (cf. Exercice 2.4.5, p.27) :

J(w) > J(v) + J ′ (v)(w − v), ∀v, w ∈ Rn , v ̸= w.

D’après (1), ceci est vrai si et seulement si (Ah, Ah) > 0 pour tout h ∈ Rn , h ̸= 0, donc si et
seulement si Ker A = {0}, i.e. rang A = n.
4. Soit M une matrice réelle m × n. Montrer que Ker M T M = Ker M . En déduire que Im M T M =
Im M T .
Correction :
On a évidemment Ker M ⊂ Ker M T M .
Si v ∈ Ker M T M , alors (v, M T M v) = 0, donc (M v, M v) = 0, et donc M v = 0. Ainsi Ker M T M =
Ker M . Donc rang M = rang M T M , et donc, en écrivant l’identité précédente pour M T , il vient
rang M T = rang M T M . Comme on a évidemment Im M T M ⊂ Im M T , on en déduit que Im M T M =
Im M T .
Autre argument : En partant de Ker M T M = Ker M , et en utilisant que pour toute matrice N on
a (Ker N )⊥ = Im N T , on en déduit immédiatement que Im M T M = Im M T .
5. En déduire qu’il existe toujours une solution ū ∈ Rn au problème de minimisation (P). Montrer
que l’espace des solutions est ū + Ker A.
Correction :
La fonction J étant convexe et dérivable sur Rn , il existe un u ∈ Rn tel que J(u) = inf v∈Rn J(v) si
et seulement si J ′ (u) = 0, i.e. si AT Au = AT b. Or ce problème admet toujours une solution d’après
la question précédente. En notant ū une solution, on a :
1
J(v) = J(ū) + (A(v − ū), A(v − ū)).
2
On voit donc que v est également solution si et seulement si v − ū ∈ Ker A. On a unicité de la
solution si et seulement si Ker A = {0}, c’est-à-dire si rang A = n (ce qu’on savait déjà puisque
c’est la condition pour que J soit strictement convexe, et qu’une fonction strictement convexe a au
plus un minimum sur un convexe (proposition 2.3.4 p.19)).

5
6. A-t-on unicité quand on choisit les monômes ωj (x) = xj−1 , j = 1, . . . , n ?
Correction :
On a bien unicité quand ωj (x) = xj−1 , j = 1, . . . , n, car on peut alors extraire de A une matrice
n × n de Vandermonde, qui est régulière puisque les xi sont supposés distincts.
ε
7. Quand il n’y a pas unicité, on peut régulariser le problème en introduisant Jε (v) = J(v) + 2 ∥v∥2 ,
pour ε > 0. On considère alors le problème :

inf Jε (v). (Pε )

v∈Rn

Montrer que (Pε ) admet un unique minimiseur uε ∈ Rn .

Correction :
On a
Jε′ (v)(h) = J ′ (v)(h) + ε(v, h) = ((AT A + εI)v − AT b, h).
La fonction Jε est convexe comme somme de deux fonctions convexes. Le problème de minimisa-
tion (Pε ) admet donc pour solution uε si et seulement si Jε′ (uε ) = 0. Or Jε′ (uε ) = 0 admet une
unique solution puisque la matrice AT A + εI est définie positive pour ε > 0.
8. Montrer que ∥uε ∥ ≤ ∥u∥ pour toute solution u de (P).
Correction :
Les conditions d’optimalité sur u et uε donnent (AT A + εI)uε = AT b = AT Au. Donc

uε = (AT A + εI)−1 AT Au.

On peut par
Pexemple
n Pn u sur une base orthonormée (ei )i=1...n de vecteurs propres de
décomposer
AT A : u = i=1 ui ei , ∥u∥2 = i=1 u2i ,
n
X λi
uε = ui ei ,
i=1
λi + ε

Pn λ2i
où les λi sont les valeurs propres de AT A. D’où ∥uε ∥2 = 2
i=1 (λi +ε)2 ui ≤ ∥u∥2 .
Autre argument (plus rapide !) :
ε ε ε
J(uε ) + ∥uε ∥2 = Jε (uε ) ≤ Jε (u) = J(u) + ∥u∥2 ≤ J(uε ) + ∥u∥2 .
2 2 2

9. En déduire que, lorsque ε → 0+ , uε converge vers la solution de (P) de norme minimale.

Correction :
Soit (εn )n≥0 une suite décroissante et tendant vers 0. D’après la question précédente, la suite (uεn )
est bornée. On peut donc en extraire une sous-suite convergente. Notons û sa limite. Par passage à
la limite dans la condition d’optimalité, on a :

AT Aû = AT b

donc û est une solution de (P), et û a une norme inférieure ou égale à toutes celles des solutions
de (P). On voit immédiatement que û est la projection orthogonale de l’origine sur le sous-espace
affine ū + Ker A, d’où son unicité.
Si on extrait une autre sous-suite convergente de (uεn ), par passage à la limite dans l’équation
d’Euler, et unicité de la solution de (P) de norme minimale, on en déduit qu’elle converge également
vers û. Ainsi la suite (uεn ) est bornée et admet û comme unique valeur d’adhérence, elle est donc
convergente vers û.
Autre argument : on peut trouver le résultat directement, sans passer par des suites extraites, en
décomposant uε et u sur une base orthonormée (ei )i=1...n de vecteurs propres de AT A. On a :

(λi + ε)uε,i = λi ui .

Si λi = 0, uε,i = 0 (donc uε ∈ (Ker A)⊥ ). Si λi > 0, uε,i → ui quand ε → 0.