École polytechnique APM_43035_EP

Optimisation et Contrôle

PC2 : Optimisation

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
On définit également les 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}.
En utilisant la méthode de votre choix, écrire toutes les solutions éventuelles Xi de chacun des problèmes
suivants :
Xi ∈ Ki , Ji (Xi ) ≤ Ji (Y ), ∀Y ∈ Ki . (Pi )
Correction :
   
1 0
• Posons F (x, y) = x + y − 3 donc ∇F (x, y) = ̸= . On peut donc appliquer le théorème des
1 0
multiplicateurs de Lagrange dans le cas de contraintes égalités (Théorème 2.5.6), il existe λ ∈ R tel
que :
∇J1 (x, y) + λ∇F (x, y) = 0,
ce qui s’écrit (en prenant en compte la contrainte) :

x3 + λ = 0
 1
  λ=− y
2
 
1
 
y+λ=0 ⇒ y = 2x3
 2

 

x + 2x3 − 3 = (x − 1)(2x2 + 2x + 3) = 0

x+y−3=0

et donc l’unique solution est x = 1, y = 2 et λ = −1.

Ainsi la solution du problème (P1 ) est donc (x̄, ȳ) = (1, 2) et J1 (x̄, ȳ) = 45 .
• 1ère possibilité :
Ramenons nous à un problème à une seule variable. On cherche le minimum de la fonctionnelle J2
sur l’ensemble K2 , cela revient donc à étudier la fonction à une seule variable J(x)
e = 2|x| + 1 − x2
pour x ∈ [−1, 1]. En étudiant les variations de cette fonction on voit qu’elle atteint son minimum
en x = 0. Ainsi, la fonction J2 admet deux minima sur K2 atteints en (0, 1) et (0, −1) avec
J2 (0, 1) = J2 (0, −1) = 1.
2ème possibilité :
On cherche ici à appliquer le théorème des multiplicateurs de Lagrange dans le cas de contraintes
égalités (Théorème 2.5.6). Notons que la fonctionnelle J2 est dérivable sur K2 \ (0, ±1).
   
2x 0
Posons F (x, y) = x2 + y 2 − 1 donc ∇F (x, y) = ̸= sur K2 (car le point (0, 0) ∈
/ K2 ). On
2y 0
peut donc appliquer le théorème des multiplicateurs de Lagrange à tout point (x, y) ∈ K2 \ (0, ±1),
il existe λ ∈ R tel que :
∇J2 (x, y) + λ∇F (x, y) = 0,

1
 ce qui s’écrit (en prenant en compte la contrainte) :

x>0 x<0
 

 


 2 + 2λx = 0  −2 + 2λx = 0

ou .

 2y + 2λy = 0 
 2y + 2λy = 0
 
x2 + y 2 − 1 = 0
 2
x + y2 − 1 = 0


Ainsi, si (x, y) ∈ K2 \ (0, ±1) est un minimum de J2 sur K2 alors :

x>0 x<0
 

 

λx = −1 λx = 1

 

ou ,

 y(1 + λ) = 0 
 y(1 + λ) = 0

 2 
x + y2 − 1 = 0 x2 + y 2 − 1 = 0


ce qui donne :  
x = 1
 x = −1

λ = −1 ou λ = −1 .
 
y=0 y=0
 

Il reste maintenant à comparer la valeur de J2 aux points (±1, 0) avec les points (0, ±1) qui n’entrent
pas dans les hypothèses du théorème des multiplicateurs de Lagrange.
Or on a J2 (1, 0) = J2 (−1, 0) = 2 > 1 = J2 (0, 1) = J2 (0, −1). Donc la fonction J2 admet deux
minima sur K2 atteints en (0, 1) et (0, −1) avec J2 (0, 1) = J2 (0, −1) = 1.
• On pose F1 (x,  = x + y + z − 8et F
y, z) 2 (x, y, z) = x + 2y − z − 10 dont les gradients sont
1 1
∇F1 (x, y, z) = 1 et ∇F2 (x, y, z) =  2  qui forment une famille libre de R3 .
1 −1
On peut donc appliquer le théorème des multiplicateurs de Lagrange, il existe λ1 , λ2 ∈ R tels que :

∇J3 (x, y, z) + λ1 ∇F1 (x, y, z) + λ2 ∇F2 (x, y, z) = 0,

ce qui s’écrit (en prenant en compte les contraintes) :

 

 x + λ1 + λ2 = 0 
 x + λ1 + λ2 =0
 
 y + λ1 + 2λ2 = 0 y + λ1 + 2λ2 =0

 

 
z + λ1 − λ2 = 0 ⇒ z + λ1 − λ2 =0
 
x +y+z−8=0  3λ1 + 2λ2 = −8

 


 
 
x + 2y − z − 10 = 0 λ1 + 3λ2 = −5
 

et donc l’unique solution est λ2 = −1, λ1 = −2, x = 3, y = 4 et z = 1.

Ainsi la solution du problème (P3 ) est donc (x̄, ȳ, z̄) = (3, 4, 1) et J3 (x̄, ȳ, z̄) = 13.

Exercice 2 Approximation par des splines

On se donne n points sur [0, 1] : 0 = x1 < x2 < . . . < xn−1 < xn = 1 et n réels (yi )i=1:n . On cherche à
construire une fonction v : [0, 1] → R assez régulière et telle que v(xi ) ≈ yi . On se propose pour cela de
minimiser la fonctionnelle
n
1 1 ′′
Z
1X
J(v) = (v (x))2 dx + (v(xi ) − yi )2 .
2 0 2 i=1

1. Commenter le rôle des deux termes de la somme définissant J.

Correction :
Le premier terme permet de contrôler la régularité de v, le second mesure la distance des v(xi ) aux
valeurs cibles yi .

2
Pour simplifier, nous supposerons que les fonctions sont dans l’espace C 2 ([0, 1]), muni de la norme ∥v∥2H 2 =
∥v∥2L2 + ∥v ′ ∥2L2 + ∥v ′′ ∥2L2 . Cet espace n’étant pas de Hilbert, nous ne pourrons pas effectuer une analyse
complète du problème. Le “bon” problème de minimisation s’écrit en fait sur un espace plus grand (l’espace
de Sobolev (H 2 (]0, 1[), ∥ · ∥H 2 )).
2. Écrire J(v) sous la forme 12 a(v, v) − L(v) + c où a est une forme bilinéaire, L une forme linéaire et
c une constante que l’on explicitera. Montrer que J est dérivable.
Correction :
On a J(v) = 12 a(v, v) − L(v) + c avec :
Z 1 n n n
X X 1X 2
a(u, v) = u′′ (x)v ′′ (x)dx + u(xi )v(xi ), L(v) = yi v(xi ), c= y .
0 i=1 i=1
2 i=1 i

Pour vérifier la continuité de a(·,R·) et L(·) sur (C 2 (]0, 1[), ∥ · ∥H 2 ), remarquer qu’on peut écrire, pour
y
tout x, y ∈ [0, 1], u(y) = u(x) + x u′ (ξ)dξ, d’où, avec l’inégalité de Cauchy-Schwarz,
Z 1 1/2
′ 2
|u(y)| ≤ |u(x)| + |u | .
0
√
En élevant au carré et en intégrant en x, il vient |u(y)|2 ≤ 2(∥u∥2L2 +∥u′ ∥2L2 ), d’où |u(y)| ≤ 2∥u∥H 2 .
On en déduit qu’il existe c1 et c2 tels que
|a(u, v)| ≤ c1 ∥u∥H 2 ∥v∥H 2 , et |L(v)| ≤ c2 ∥v∥H 2 .
On a :
1
J(v + h) = J(v) + a(v, h) − L(h) + a(h, h),
2
avec a(h, h) = o(∥h∥H 2 ) et h 7→ a(v, h) − L(h) linéaire et continue sur (C 2 (]0, 1[), ∥ · ∥H 2 ). Donc J
est dérivable et J ′ (v)(h) = a(v, h) − L(h).
3. Montrer que J est convexe.
Correction :
On a J(v) = J(u) + J ′ (u)(v − u) + 21 a(v − u, v − u). Or a(·, ·) est positive, donc J(v) ≥ J(u) +
J ′ (u)(v − u), ce qui prouve que J est convexe.
Remarque : l’existence d’un unique minimiseur vient d’une propriété d’α-convexité dans l’espace
de Hilbert (H 2 (]0, 1[, ∥ · ∥H 2 ) (elle-même résultant de la coercivité de a(·, ·)).
On admettra que le problème de minimisation admet une unique solution u qui est de classe C 1 sur ]0, 1[,
de classe C 4 sur chaque intervalle ]xi , xi+1 [, i = 1, . . . , n − 1, et dont la dérivée seconde est dans L2 (]0, 1[).
4. Écrire les conditions d’optimalité pour u.
Correction :
Le problème de minimisation est écrit sur l’espace tout entier. La condition d’optimalité s’écrit donc
J ′ (u) = 0, ce qui implique :
Z 1 n
X
u′′ (x)v ′′ (x)dx + (u(xi ) − yi )v(xi ) = 0
0 i=1

2
pour tout v ∈ C (]0, 1[).
5. En testant la condition d’optimalité avec des fonctions φ ∈ C ∞ à support compact dans ]xi , xi+1 [,
montrer que u est un polynôme de degré 3 par morceaux.
Correction :
On écrit la condition d’optimalité pour φ ∈ Cc∞ (]xi , xi+1 [) :
Z xi+1
u′′ (x)φ′′ (x)dx = 0.
xi

En intégrant deux fois par parties :

Z xi+1
u(4) (x)φ(x)dx = 0.
xi

(4)
Donc u (x) = 0 sur ]xi , xi+1 [, i.e. u = pi sur ]xi , xi+1 [ où pi est un polynôme de degré 3.

3
 6. En déduire que u est en fait de classe C 2 (]0, 1[) et écrire les conditions vérifiées par u aux points xi .
Correction :
Comme on a admis que u ∈ C 1 (]0, 1[), pi−1 (xi ) = pi (xi ), et p′i−1 (xi ) = p′i (xi ), i = 2, . . . , n − 1. En
intégrant deux fois par parties la condition d’optimalité, on a :
n−1 n
(3) (3)
X
X
p′′i (xi+1 )v ′ (xi+1 )−p′′i (xi )v ′ (xi ) − pi (xi+1 )v(xi+1 )−pi (xi )v(xi ) +


(u(xi )−yi )v(xi ) = 0.
i=1 i=1

En réorganisant les termes on obtient alors :

n−1
X
p′′i−1 (xi ) − p′′i (xi ) v ′ (xi ) + p′′n−1 (xn )v ′ (xn ) − p′′1 (x1 )v ′ (x1 )


i=2
n−1 n
(3) (3) (3) (3)
X
X
− pi−1 (xi ) − pi (xi ) v(xi ) − pn−1 (xn )v(xn ) + p1 (x1 )v(x1 ) + (u(xi ) − yi )v(xi ) = 0.
i=2 i=1

En choisissant v telle que v(xi ) = 0 et v ′ (xi ) est quelconque, on en déduit que p′′i (xi ) = p′′i−1 (xi ),
i = 2, . . . , n − 1, donc u est en fait de classe C 2 (]0, 1[). De plus u′′ (0) = u′′ (1) = 0.
En choisissant ensuite v quelconque, on trouve le saut sur la dérivée 3ème :
(3) (3) (3) (3)
p1 (x1 ) = y1 − u(x1 ), pi (xi ) − pi−1 (xi ) = yi − u(xi ), 2 ≤ i ≤ n − 1, pn−1 (xn ) = u(xn ) − yn .

Exercice 3 Relaxation de contraintes par pénalisation

Soit F une fonction réelle définie sur Rn , convexe, C 1 et infinie à l’infini. On s’intéresse au problème :

min F (u), (P )
u∈K

où K est le convexe défini par K = {u ∈ Rn , ⟨ai , u⟩ ≤ bi , i = 1, . . . , l} avec ai ∈ Rn et bi ∈ R.

1. On suppose que bi = 0 pour i ∈ {1, . . . , l} et que les vecteurs (a1 , . . . , al ) sont linéairement indé-
pendants.
(a) Montrer que le problème (P ) admet au moins une solution ū ∈ K.
Correction :
L’ensemble K est un ensemble fermé, non vide de Rn (car 0 ∈ K). De plus, par hypothèse
la fonction F est continue sur K et infinie à l’infini. Donc par le théorème d’existence en
dimension finie (Théorème 2.2.1) il existe au moins une solution ū ∈ K au problème (P ).
(b) Montrer que :
⟨F ′ (ū), ū⟩ = 0 et ⟨F ′ (ū), w⟩ ≥ 0, ∀w ∈ K.
Correction :
K étant convexe et F différentiable sur K, d’après l’inéquation d’Euler (Théorème 2.5.1), si
ū ∈ K est minimum de F sur K alors :

⟨F ′ (ū), w − ū⟩ ≥ 0, ∀w ∈ K.

D’après la définition de K, 0 ∈ K et 2ū ∈ K, on a donc :

⟨F ′ (ū), −ū⟩ ≥ 0 et ⟨F ′ (ū), ū⟩ ≥ 0.

On en conclut donc :
⟨F ′ (ū), ū⟩ = 0
et ainsi :
⟨F ′ (ū), w⟩ ≥ 0, ∀w ∈ K. (1)

4
 (c) En déduire qu’il existe λ1 , . . . , λl ≥ 0 tels que ū vérifie :
l
X
∇F (ū) + λi ai = 0
i=1

où les λi sont des réels positifs ou nuls.

Correction :
Notons A le sous-espace engendré par les (ai )1≤i≤l . Soit w ∈ A⊥ fixé, alors w ∈ K et −w ∈ K
et donc l’inégalité (1) donne :
(
⟨F ′ (ū), w⟩ ≥ 0
⇒ ⟨F ′ (ū), w⟩ = 0 ⇒ F ′ (ū) ∈ (A⊥ )⊥ = A.
⟨F ′ (ū), −w⟩ ≥ 0

Ainsi, il existe λ1 , . . . , λl ∈ R tels que :

l
X
F ′ (u) = − λi ai .
i=1

Il reste à montrer que les λi sont positifs ou nuls. Notons M la matrice symétrique dont
les coefficients sont donnés par Mi,j = ⟨ai , aj ⟩. Les vecteurs (a1 , . . . , al ) étant linéairement
indépendants, la matrice M est définie positive donc inversible. Soit q ∈ (R+ )l arbitraire.
Pl
Posons µq = M −1 q. Alors le vecteur wq = − j=1 µq,j aj est dans K puisque
l
X
⟨wq , ai ⟩ = − µq,j Mij = −qi ≤ 0.
j=1

L’inégalité (1) donne :

l
X l
X l
X
⟨F ′ (ū), wq ⟩ ≥ 0 ⇒ λi µq,j ⟨ai , aj ⟩ = (M µq )i λi = qi λi ≥ 0.
i,j=1 i=1 i=1

Le vecteur q ∈ (R+ )l étant arbitraire, cela entraîne λ ∈ (R+ )l .

On se propose maintenant de retrouver ce résultat dans un cadre plus général en approchant (P ) par le
problème sans contrainte :
minn Fε (u), (Pε )
u∈R
1
Pl
où ε > 0, Fε (u) = F (u)+ ε i=1 g(⟨ai , u⟩−bi ) et g est une fonction C 1 (R), croissante et telle que g(x) = 0
si x ≤ 0 et g(x) > 0 si x > 0.
2. Montrer que (Pε ) admet au moins une solution uε .
Correction :
La fonction F est continue et infinie à l’infini. La fonction g est continue et positive. Donc Fε est
continue et infinie à l’infini. Le théorème 2.2.1 (et le fait que Rn est évidemment fermé) entraîne
donc l’existence d’au moins un point de minimum pour le problème (Pε ).
3. On suppose que K n’est pas vide. Montrer qu’il existe M > 0 tel que ∥uε ∥ ≤ M pour tout ε > 0.
Correction :
Soit u0 ∈ K. On a Fε (u0 ) = F (u0 ) car Fε et F coincident sur K. Or par définition de uε , on
a Fε (uε ) ≤ Fε (u0 ). Donc Fε (uε ) ≤ F (u0 ) et comme F (v) ≤ Fε (v) pour tout v ∈ Rn on a donc
F (uε ) ≤ Fε (uε ) ≤ F (u0 ). Comme F est infinie à l’infini, cela implique que uε est bornée.
4. En déduire qu’il existe ū ∈ K solution du problème (P ).
Correction :
Soit (εn )n≥0 une suite décroissante et tendant vers 0. La suite (uεn )n≥0 étant bornée d’après la
question précédente, on peut en extraire une sous-suite, notée encore (uεn )n≥0 , convergeant dans
Rn . On note ū sa limite.
Pl
Les suites (Fεn (uεn )) et (F (uεn )) sont bornées, donc i=1 g(⟨ai , uεn ⟩ − bi ) = εn (Fεn (uεn ) − F (uεn ))
tend vers 0. Donc, par continuité, g(⟨ai , ū⟩ − bi ) = 0, pour i = 1, . . . , l. Donc ū ∈ K.
Enfin, en remarquant que F (uε ) ≤ Fε (uε ) ≤ Fε (v), ∀v ∈ Rn et Fε (v) = F (v), ∀v ∈ K, on a par
passage à la limite F (ū) ≤ F (v), ∀v ∈ K.

5
 5. Écrire la condition d’optimalité vérifiée par uε .
Correction :
La fonction Fε étant de classe C 1 et le problème (Pε ) étant posé sur un ouvert, la condition d’opti-
malité s’écrit :
l
1X ′
∇F (uε ) + g (⟨ai , uε ⟩ − bi )ai = 0.
ε i=1

6. En déduire qu’il existe λ1 , . . . , λl ≥ 0 tels que ū vérifie :

l
X
∇F (ū) + λi ai = 0
i=1

où les λi sont des réels positifs ou nuls.

Pl
Indication : On admettra que le cône C = { i=1 αi ai , pour αi ≥ 0, i = 1, . . . , l} est fermé.
Correction :
La fonction g étant croissante on a g ′ (⟨ai , uε ⟩ − bi )/ε ≥ 0 pour i = 1, . . . , l. Donc −∇F (uε ) ∈ C.
Par passage à la limite, C étant fermé, −∇F (ū) ∈ C. Autrement dit, il existe λ1 , . . . , λl ≥ 0 tels que
l
X
∇F (ū) + λi ai = 0.
i=1

Les λi sont les multiplicateurs de Lagrange associés à la contrainte.

Exercice 4 Problèmes de maximisation

Soit A ∈ Mn (R) une matrice symétrique définie positive et un vecteur b ∈ Rn non nul. On considère les
problèmes de maximisation suivants :

sup ⟨b, x⟩ et sup ⟨b, x⟩. (2)

⟨Ax,x⟩≤1 ⟨Ax,x⟩=1

1. Montrer que ces problèmes admettent au moins une solution.

Correction :
Posons J(x) = ⟨b, x⟩, alors −J (pour se ramener à un problème de minimisation) est continue. De
plus, les ensembles :

K = {x ∈ Rn : ⟨Ax, x⟩ ≤ 1} et e = {x ∈ Rn : ⟨Ax, x⟩ = 1}
K

sont fermés bornés non vide.

Puisque nous sommes en dimension finie, les problèmes (2) admettent au moins une solution.
2. Calculer la dérivée de la fonctionnelle à maximiser et en déduire que les deux problèmes sont
équivalents.
Correction :
On a J ′ (x) = b (car J(x + h) = J(x) + ⟨b, h⟩ et l’application h 7→ ⟨b, h⟩ est linéaire donc continue
en dimension finie).
Afin d’appliquer le Théorème 2.5.1 montrons que l’ensemble K est convexe. Pour cela, montrons
que l’application G(x) = ⟨Ax, x⟩ est convexe. A étant symétrique, on a :

G(x + h) = ⟨A(x + h), x + h⟩ = ⟨Ax, x⟩ + 2⟨Ax, h⟩ + ⟨Ah, h⟩.

Or |(Ah, h)| ≤ ∥A∥∥h∥2 , donc (Ah, h) = o(h) et l’application h 7→ 2⟨Ax, h⟩ est linéaire (donc
continue en dimension finie) donc G est dérivable et G′ (x) = 2Ax.
Pour tout x, y ∈ Rn , on peut alors écrire :

G(y) = G(x) + G′ (x)(y − x) + ⟨A(y − x), (y − x)⟩ ≥ G(x) + G′ (x)(y − x),

| {z }
≥0

6
 ce qui nous permet de conclure (cf Proposition 2.4.4) que G est convexe. Prenons maintenant
x, y ∈ K et t ∈ [0, 1], alors G étant convexe on a :

⟨A(tx + (1 − t)y), tx + (1 − t)y⟩ ≤ t ⟨Ax, x⟩ +(1 − t) ⟨Ay, y⟩ ≤ 1,

| {z } | {z }
≤1 ≤1

donc tx + (1 − t)y ∈ K et K est convexe.

Notons x̄ une solution du problème :
sup ⟨b, x⟩.
⟨Ax,x⟩≤1

Alors, d’après la Remarque 2.5.2 du polycopié, si x̄ est dans l’intérieur de K alors J ′ (x) = b = 0.
Or le vecteur b est non nul, donc J ′ (x) ne peut pas s’annuler et le maximum de J sur K est
forcément atteint sur le bord, ce qui prouve que les deux problèmes sont équivalents.
3. Calculer cette solution et montrer qu’elle est unique.
Correction :
Posons F (x) = ⟨Ax, x⟩ − 1 alors par un raisonnement similaire à celui donné dans la question
précédente pour G on montre que F est dérivable et F ′ (x) = 2Ax.
Appliquons alors le Théorème 2.5.6 au problème de maximisation sur K. e Les fonctions J et F sont
′
bien dérivables sur K et F (x) = 2Ax ̸= 0 pour tout x ∈ K. Il existe donc λ ∈ R tel que :
e e

1 −1
−J ′ (x̄) + λF ′ (x̄) = 0 ⇔ −b + 2λAx̄ = 0 ⇔ x̄ = A b.
2λ

Il reste à déterminer λ. On sait que x̄ ∈ K,

e donc :
 
1 1
⟨Ax̄, x̄⟩ = 1 ⇔ b, A−1 b = 1 ⇔ ⟨b, A−1 b⟩ = 4λ2 .
2λ 2λ

On obtient donc :
1p A−1 b
λ=± ⟨b, A−1 b⟩ et x̄ = ± p .
2 ⟨b, A−1 b⟩
Or la matrice A étant symétrique définie positive, la matrice A−1 l’est aussi et on a :
!
A−1 b b, A−1 b p
J p =p = ⟨b, A−1 b⟩ ≥ 0
−1
⟨b, A b⟩ −1
⟨b, A b⟩

et !
A−1 b b, A−1 b p
J −p = −p = − ⟨b, A−1 b⟩ ≤ 0.
⟨b, A−1 b⟩ −1
⟨b, A b⟩
−1 p
Ainsi, l’unique solution des problèmes (2) est donnée par x̄ = √ A b
et J(x̄) = ⟨b, A−1 b⟩.
⟨b,A−1 b⟩
4. On introduit un ordre partiel dans l’ensemble des matrices symétriques définies positives d’ordre n
en disant que A ≥ B si et seulement si ⟨Ax, x⟩ ≥ ⟨Bx, x⟩ pour tout x ∈ Rn .
Montrer que si A ≥ B, alors B −1 ≥ A−1 .
Correction :
Si A ≥ B, alors ⟨Ax, x⟩ ≥ ⟨Bx, x⟩ et donc :

{x ∈ Rn : ⟨Ax, x⟩ ≤ 1} ⊂ {x ∈ Rn : ⟨Bx, x⟩ ≤ 1}.

On a alors : p p
⟨b, A−1 b⟩ = sup ⟨b, x⟩ ≤ sup ⟨b, x⟩ = ⟨b, B −1 b⟩.
⟨Ax,x⟩≤1 ⟨Bx,x⟩≤1

Ce raisonnement étant valable pour tout vecteur b ∈ Rn non nul, on en conclut B −1 ≥ A−1 .