2024-2025 APM 43035 EP

École polytechnique Optimisation et Contrôle

PC5 : Contraintes et algorithmes - Correction

Exercice 1 Minimisation par relaxation

On considère le problème minu∈K J(u), où la fonctionnelle J est C 1 , strictement convexe dans Rp , infinie
à l’infini et on considère le pavé
K = Πpi=1 ]ai , bi [ ⊂ Rp .
où ai , bi ∈ R ∪ {+∞} ∪ {−∞} tels que ai < bi . Noter que si K est borné, on a K = Πpi=1 [ai , bi ]. On pose
u = (u1 , .., up ). On s’intéresse à une méthode itérative de la forme u0 ∈ K, et un+1 = T (un ) où T est une
application de K dans K. On dit que l’algorithme est de relaxation si l’application T vérifie la propriété
suivante : pour tout u ∈ K, v = T (u) vérifie

J(v1 , ..., vi−1 , vi , ui+1 , . . . , up ) ≤ J(v1 , . . . , vi−1 , w, ui+1 , . . . , up ), ∀i ∈ {1, . . . , p}, ∀w ∈ ]ai , bi [. (1)

Par construction on a J(v) = J(T (u)) ≤ J(u), et la méthode itérative ci-dessus satisfait donc J(un+1 ) ≤
J(un ).

Question 1. Montrer que l’application T est définie de manière univoque par (1).
Correction : Pour u ∈ K, on définit (vi )1≤i≤p par la procédure suivante. Le réel v1 est défini comme
étant le minimiseur de la fonction

w 7−→ R1 (w) = J(w, u2 , . . . , up )

sur ]a1 , b1 [. La fonction J étant strictement convexe, infinie à l’infini, il en est de même pour R1 . Donc
v1 est défini de manière unique. Supposant v1 , . . . , vi−1 connus, on définit ensuite le réel vi comme étant
le minimiseur de la fonction

w 7−→ Ri (w) = J(v1 , . . . , vi−1 , w, ui+1 , . . . , up ) (2)

sur ]ai , bi [. Comme R1 , la fonction Ri est strictement convexe, infinie à l’infini. Donc vi est défini de
manière unique. Le vecteur v ainsi construit appartient à K et vérifie les conditions de la définition (1).
Si un autre élément ṽ vérifie les même conditions, on établit sans difficulté que ṽ = v. L’application T
est donc bien définie par (1).

Question 2. Donner une condition nécessaire et suffisante pour qu’un élément v ∈ K soit tel que
v = T (u).
Correction : Un élément v de K vérifie v = T (u) si et seulement si pour tout i, vi est solution du
problème de minimisation (2). Comme la fonction Ri est dérivable et convexe, vi minimise Ri sur le
convexe fermé non vide ]ai , bi [ si et seulement si

⟨Ri′ (vi ), wi − vi ⟩ ≥ 0

pour tout i, c’est à dire

∂J
(v1 , . . . , vi , ui+1 , . . . , up )(wi − vi ) ≥ 0, (3)
∂xi
pour tout indice i et tout wi ∈ ]ai , bi [.

Question 3. Montrer que l’application T est continue.

Indication : on rappelle le lemme suivant : soit (xn )n∈N une suite d’éléments d’un espace vectoriel V .
Soit x ∈ V tel que de toute suite extraite de (xn )n∈N , on peut extraire une nouvelle sous-suite convergeant
vers x. Alors la suite (xn )n∈N converge vers x.

1
Correction : Soit (uk )k∈N une suite d’éléments de K convergeant vers un élément u ∈ K. On veut
montrer que la suite (T (uk ))k∈N converge vers T (u) et pour cela on utilise le lemme ci-dessus. La suite
(uk )k∈N étant convergente, elle est bornée et la suite (J(uk ))k∈N est également bornée. Comme J(T (uk )) ≤
J(uk ), la suite (J(T (uk )))k∈N est bornée. Comme J est infinie à l’infini, la suite (T (uk ))k∈N est également
bornée. Considérons une sous-suite de T (uk ). Comme (T (uk ))k∈N est bornée, on peut extraire une sous-
suite (T (unk ))k∈N convergente. On note v la limite de (T (unk ))k∈N . Pour tout w ∈ K, et pour tout indice
i, on a d’après la définition de T
∂J
(T (unk )1 , . . . , T (unk )i , uni+1
k
, . . . , unp k )(wi − T (unk )i ) ≥ 0.
∂xi
Par passage à la limite, on en déduit que
∂J
(v1 , . . . , vi , ui+1 , . . . , up )(wi − vi ) ≥ 0
∂xi

et que v = T (u). Comme la limite de la sous-suite (T (unk ))k∈N est indépendante de la sous-suite choisie,
le lemme permet de conclure que la suite (T (uk ))k∈N converge vers v = T (u). En conclusion, l’application
T est donc continue.
Preuve du lemme (par l’absurde). On fait l’hypothèse que de toute suite extraite de (xn )n∈N , on peut
extraire une nouvelle sous-suite convergeant vers x, et on suppose que (xn )n∈N ne converge pas vers x.
Dans ce cas, il existe ε > 0 tel que pour tout N , il existe n > N tel que |xn − x| ≥ ε. On en déduit qu’il
existe une sous-suite (xnk )k∈N de (xn )n∈N telle que pour tout ε,

|x − xnk | ≥ ε.

Mais alors aucune sous-suite de (xnk ))k∈N ne saurait converger vers x, ce qui contredit l’hypothèse. Donc
(xn )n∈N converge vers x.

Question 4. Montrer que si J(u) = J(T (u)), alors u = T (u) et u est le minimiseur de J sur K.
Correction : Soit u tel que J(u) = J(T (u)). Posons v = T (u). D’après la définition de T , on a

J(v1 , . . . , vp ) ≤ J(v1 , . . . , vp−1 , up )

···
≤ J(v1 , u2 , . . . , up )
≤ J(u).

Par hypothèse, J(u) = J(v). Ainsi, toute les inégalités précédentes sont des égalités et u vérifie le système
(1), d’où T (u) = u. D’après (3),
∂J
(u)(wi − ui ) ≥ 0,
∂xi
ou encore ⟨J ′ (u), w − u⟩ ≥ 0 pour tout w ∈ K. L’élément u de K minimise donc J.

Question 5. Montrer que l’algorithme défini par (1) converge vers le minimiseur de J sur K.
Correction : La suite (J(un )) est décroissante minorée donc convergente. On note J0 sa limite. De plus,
comme (J(un )) est bornée et que J est infinie à l’infini, (un ) est une suite bornée. De toute sous-suite de
(un ), on peut extraite une sous-suite (unk ) convergeant vers un élément v ∈ K. De plus,

J0 = lim J(unk ) = J(v) et J0 = lim J(T (unk )) = J(T (v)),

k k

où on a utilisé ici la continuité de l’application T . On a donc J(v) = J(T (v)). D’après la question
précédente, v = T (v) est le minimiseur u de J sur K. D’après le lemme rappelé ci-dessus, on en déduit
que toute la suite est convergente.

Question 6. On prend K = R2 et J(x1 , x2 ) = 21 (x21 + x22 ) + |x1 − x2 | − (x1 + x2 ). Que vaut le minimum ?
[Indication : on pourra effectuer le changement de variable X = x1 + x2 et Y = x1 − x2 ]. Appliquer
l’algorithme précédent pour u0 = (0, 0). Commenter.

2
Correction : On a
X2 + Y 2
J(x1 , x2 ) = + |Y | − X.
4
Le minimum de J est nécessairement atteint pour Y = 0. On en déduit facilement que le minimum est
atteint en (X, Y ) = (2, 0). En revenant à l’expression en termes de x1 et x2 , on en déduit que le minimum
de J est atteint pour x1 = x2 = 1 et min J = J(1, 1) = −1.
Il est aisé de constater que T (0, 0) = (0, 0). En effet, en notant v = T (0, 0), la première composante de
v s’obtient en minimisant J(v1 , 0) = 21 v12 + |v1 | − v1 dont le minimiseur est v1 = 0. Puis la deuxième
composante de v s’obtient en minimisant J(v1 , v2 ) = J(0, v2 ) = 21 v22 + |v2 | − v2 dont le minimiseur est
à nouveau v2 = 0. On a donc T (0, 0) = v = (0, 0). En conclusion, l’algorithme ne converge pas vers le
minimiseur de J. Évidemment, J ne vérifie pas les conditions imposées en début d’énoncé. En particulier,
J n’est pas dérivable.

Question 7. On prend K = Rp et J(u) = 12 (u, Au) − (b, u) où A est une matrice symétrique définie
positive. Déduire de la méthode de relaxation un algorithme pour résoudre Au = b.
Correction : Comme A est symétrique, J ′ (u) = Au − b. Et comme on minimise sur Rp tout entier, les
inéquations d’Euler (3) définissant un+1 en fonction de un deviennent des équations d’Euler :
k
X p
X
aki un+1
i + aki uni = bk ,
i=1 i=k+1

soit encore sous forme vectorielle

M un+1 − N un = b,
où A = D − E − F , M = D − E, N = F , D est la diagonale de la matrice A, −E sa partie triangulaire
inférieure et −F sa partie triangulaire supérieure. Cet algorithme est connu sous le nom d’algorithme de
Gauss–Seidel.

Exercice 2
n n
Pn J une fonction convexe et dérivable sur R et α > 0. Pour v = (v1 , . . . , vn ) ∈ R , on note ∥v∥1 =
Soit
i=1 |vi |, où |·| désigne la valeur absolue, et f (v) = J(v)+α∥v∥1 , avec α > 0. On s’intéresse au problème :

inf f (v). (4)

v∈Rn

Question 1. On aimerait utiliser une méthode de gradient pour résoudre (4). Quelle difficulté cela
pose-t-il ?
Correction : La difficulté vient de la non dérivabilité de v 7→ ∥v∥1 .

Question 2. Pour (x, y) ∈ Rn × Rn , on définit g(x, y) = J(x − y) + α1 · (x + y), où 1 est le vecteur de Rn
dont toutes les composantes valent 1 et · désigne le produit scalaire euclidien. On définit K = {(x, y) ∈
Rn × Rn , xi ≥ 0, yi ≥ 0, i = 1, . . . , n}, où xi et yi désignent respectivement les composantes de x et de y.
On considère le problème
inf g(x, y). (5)
(x,y)∈K

Ecrire le lagrangien associé à (5). Vérifier qu’on peut appliquer le théorème de Kuhn et Tucker, et écrire
les conditions d’optimalité.
Correction : Le lagrangien associé à (5) est donné par :

L(x, y, λ, µ) = g(x, y) − λ · x − µ · y = J(x − y) + α1 · (x + y) − λ · x − µ · y,

où x ∈ Rn , y ∈ Rn , λ ∈ Rn+ et µ ∈ Rn+ . La fonction g est convexe et dérivable (composition d’une fonction
convexe dérivable et d’une fonction affine), les fonctions définissant les contraintes sont évidemment
dérivables et convexes. Les contraintes sont qualifiées en tout point (x, y) car elles sont affines. Le théorème
de Kuhn et Tucker s’applique donc. Si (x, y) est solution de (5), il existe λ ∈ Rn+ et µ ∈ Rn+ tels que
(x, y, λ, µ) est un point selle du lagrangien.

3
On a :
∂g ∂J ∂g ∂J
(x, y) = (x − y) + α, (x, y) = − (x − y) + α
∂xi ∂vi ∂yi ∂vi
Les conditions d’optimalité s’écrivent donc, pour i = 1, . . . , n :
 ∂J
 (x − y) + α − λi = 0,
∂vi






 ∂J

− (x − y) + α − µi = 0,
 ∂vi





 xi ≥ 0, λi ≥ 0, xi λi = 0,


yi ≥ 0, µi ≥ 0, yi µi = 0.

Question 3. Soient z = (z1 , . . . , zn ) ∈ Rn et t = (t1 , . . . , tn ) ∈ Rn . Si (z, t) est solution de (5), montrer

que zi ti = 0, pour i = 1, . . . , n.
Correction : Soit (z, t) solution de (5). D’après les conditions d’optimalité, on a :

λi + µi = 2α, i = 1, . . . , n.

Comme α > 0, λi et µi ne peuvent pas être tous les deux nuls. Or, si zi ̸= 0 alors λi = 0, donc µi ̸= 0.
Mais comme ti µi = 0, cela implique que ti = 0. On montre de même que si ti ̸= 0 alors zi = 0. On en
déduit que zi ti = 0, ∀i = 1, . . . , n.

Question 4. Si (z, t) ∈ R2n est solution de (5), montrer que u = z − t est solution de (4).
Correction : Soit (z, t) solution de (5). On pose u = z − t. Comme zi ≥ 0, ti ≥ 0, zi ti = 0, ∀i = 1, . . . , n,
on a 1 · (z + t) = ∥u∥1 . Donc :
g(z, t) = J(u) + α∥u∥1 = f (u).
Soit v ∈ Rn , on pose x = v+ et y = v− , les parties positive et négative de v. Ainsi x − y = v et
1 · (x + y) = ∥v∥1 . Par définition de (z, t), on a g(z, t) ≤ g(x, y). Or g(x, y) = J(v) + α∥v∥1 = f (v). On a
donc bien f (u) ≤ f (v), ∀v ∈ Rn .

Question 5. Proposer un algorithme pour résoudre (5) et commenter.

Correction : Le problème (5) a un inconvénient évident : sa taille est le double de celle de (4). En
revanche, il a l’avantage de ne faire intervenir que des fonctions dérivables. On peut donc par exemple
utiliser une méthode de gradient avec projection (les contraintes étant très faciles à prendre en compte),
ou un algorithme d’Uzawa (maximisation de l’énergie duale par une méthode de gradient).

Exercice 3 Algorithme d’Arrow-Hurwicz

On considère une matrice A symétrique définie positive d’ordre n et un vecteur b ∈ Rn . On introduit la
fonctionnelle quadratique J : Rn → R telle que, pour tout v ∈ Rn , J(v) = 21 Av · v − b · v. On considère une
matrice rectangulaire C d’ordre m × n et un vecteur d ∈ Rm . On suppose que m < n et que la matrice
C est de rang maximal. Le problème de minimisation de J dans K = {v ∈ Rn ; Cv = d} admet une et
une seule solution u ∈ Rn et il existe un et un seul vecteur λ ∈ Rm tel que le couple (u, λ) ∈ Rn × Rm
soit solution du système linéaire

Au + C t λ = b, (6a)
Cu = d, (6b)

où C t désigne la matrice transposée de C. L’objectif de cet exercice est d’étudier la convergence de
l’algorithme d’approximation suivant : on se donne (u0 , λ0 ) ∈ Rn × Rm , ainsi que deux paramètres
positifs ρ1 , ρ2 , et pour tout k ≥ 0, (uk , λk ) étant connu, on détermine (uk+1 , λk+1 ) par

uk+1 = uk − ρ1 (Auk − b + C t λk ), (7a)

k+1 k k+1
λ = λ + ρ1 ρ2 (Cu − d). (7b)

4
Question 1. Comparer cet algorithme à celui d’Uzawa.
Correction : L’algorithme d’Arrow-Hurwicz est comme celui d’Uzawa un algorithme de point-selle,
c’est-à-dire cherchant un minimum pour u et un maximum pour λ par des itérations de méthodes de
gradient. Dans l’algorithme d’Uzawa, à chaque itération de gradient sur λ, on résout un problème de
minimisation (sans contrainte) sur u, alors que dans l’algorithme d’Arrow-Hurwicz, on ne fait qu’une
itération de gradient sur u.

Question 2. Montrer l’identité suivante (I désigne la matrice identité de Rn ) :

∥λk+1 − λ∥2 = ∥λk − λ∥2 + ρ21 ρ22 ∥C(uk+1 − u)∥2

− 2ρ2 (uk+1 − u) · uk+1 − u − (I − ρ1 A)(uk − u) .

(Indication : observer que λk+1 − λ = (λk − λ) + ρ1 ρ2 C(uk+1 − u).)

Correction : L’indication se montre en utilisant les équations (7a) et (7b) :

uk+1 = uk − ρ1 (Auk − b + C t λk ),
λk+1 = λk + ρ1 ρ2 (Cuk+1 − d)

et le fait que Cu = d. On élève chaque membre de l’égalité ainsi obtenue au carré, et pour le double
produit, on constate que

ρ1 ρ2 C(uk+1 − u) · (λk − λ) = ρ1 ρ2 (uk+1 − u) · C t (λk − λ)

= −ρ2 (uk+1 − u) · uk+1 − u − (I − ρ1 A)(uk − u) ,

où on utilise ρ1 C t λ = ρ1 (b − Au) et ρ1 C t λk = uk − uk+1 − ρ1 (Auk − b) de par (7a).

Question 3. On peut montrer que pour ρ1 > 0 suffisamment petit, on a β := ∥I − ρ1 A∥ < 1. Par la
suite, la valeur de ρ1 est fixée à une telle valeur. Montrer que pour ρ2 > 0 suffisamment petit, il existe
une constante γ > 0, indépendante de k, telle que
 
k+1 2 1 k 2 k 2 1 k+1 2 k+1 2
γ∥u − u∥ ≤ ∥λ − λ∥ + β∥u − u∥ − ∥λ − λ∥ + β∥u − u∥ . (8)
ρ2 ρ2

(Indication : observer que ρ12 ∥λk −λ∥2 − ρ12 ∥λk+1 −λ∥2 ≥ 2∥uk+1 −u∥2 −ρ21 ρ2 ∥C(uk+1 −u)∥2 −2β∥uk+1 −
u∥∥uk − u∥.) En déduire, pour un tel choix de ρ2 , que limk→∞ uk = u.
Correction : L’indication se montre en divisant l’identité obtenue à la question 1 par ρ2 , en développant
le dernier terme du membre de droite et en majorant la norme de la matrice (I − ρ1 A) par β. On utilise
ensuite la fait que
−2β∥uk+1 − u∥∥uk − u∥ ≥ −β∥uk+1 − u∥2 − β∥uk − u∥2 ,
et ∥C(uk+1 − u)∥2 ≤ ∥C∥2 ∥uk+1 − u∥2 . En combinant ces relations, on obtient l’inégalité (8) :
 
1 1 k+1
γ∥uk+1 − u∥2 ≤ ∥λk − λ∥2 + β∥uk − u∥2 − ∥λ − λ∥2 + β∥uk+1 − u∥2 ,
ρ2 ρ2

avec γ = 2 − 2β − ρ21 ρ2 ∥C∥2 et on choisit ρ2 suffisamment petit pour que γ > 0 (ce qui est possible car
β < 1). En sommant l’inégalité (8) pour k allant de 0 à (l − 1), et en constatant que le second membre
télescope, il vient
l−1
X 1 l 1
γ ∥uk+1 − u∥2 + ∥λ − λ∥2 + β∥ul − u∥2 ≤ ∥λ0 − λ∥2 + β∥u0 − u∥2 ,
ρ2 ρ2
k=0

pour tout l ≥ 1. On conclut en faisant tendre l → ∞ que la série au membre de gauche converge, si bien
que ∥uk − u∥ tend vers zéro.

Question 4. Vérifier que la matrice CC t est inversible, puis montrer que

λk = (CC t )−1 C ρ−1 k k+1

) + b − Auk .


1 (u − u

5
Que peut-on dire de la convergence de la suite λk ?
Correction : Si v ∈ Ker(CC t ), on a 0 = v · CC t v = ∥C t v∥2 . On en déduit que v = 0 car C t est injective
(puisque C est de rang maximal). Donc, CC t est bien inversible. D’après (7a), on a

C t λk = ρ−1 k
1 (u − u
k+1
) + b − Auk .

En multipliant à gauche par C puis par (CC t )−1 , on obtient l’expression demandée pour λk . Enfin,
comme uk → u, le membre de droite de cette expression converge vers (CC t )−1 C(b − Au) = λ grâce
à (6a) et (6b) :

Au + C t λ = b,
Cu = d,

ainsi, la suite λk converge vers λ.

Exercice 4 Dualité et introduction au contrôle

On considère un système dont l’état u est représenté par un vecteur u ∈ Rn , solution du système

Au = f + v, (9)

où A est une matrice symétrique réelle, définie positive, f ∈ Rn est une donnée et v ∈ Rn est un contrôle.
On cherche à ajuster le contrôle v de sorte à obtenir un état cible u0 ∈ Rn . On définit la fonction
j : Rn → R par
j(w) = |w − u0 |2 . (10)
Pour tout contrôle v ∈ Rn , on introduit la fonction coût

Jc (v) = j(u(v)),

où u(v) est la solution de l’équation (9).

Question 1. Montrer que la fonction v 7→ u(v) est dérivable. Calculer la dérivée de Jc .

Correction : On a u(v) = A−1 (f + v). Ainsi, l’application qui à v associe u(v) est linéaire et

⟨u′ (v), w⟩ = A−1 w.

Enfin, Jc′ (v) = j ′ (u(v)) · u′ (v). Or j ′ (w) = 2(w − u0 ), ainsi,

⟨Jc′ (v), w⟩ = 2(u(v) − u0 ) · A−1 w.

Question 2. En pratique, la taille du problème empêche de calculer directement l’inverse de A. On

peut en revanche résoudre des systèmes du type Ax = b. Afin de minimiser Jc , on souhaite utiliser une
méthode de type gradient (par exemple le gradient à pas fixe). Montrer que le calcul de la dérivée de
Jc en v ne nécessite que la résolution de deux systèmes linéaires. On notera p la solution du nouveau
système introduit, appelé système adjoint. On appelle p l’état adjoint.
Correction : Il suffit de remarquer que, A étant symétrique, Jc′ (v) = 2A−1 (u(v) − u0 ). Le calcul de la
dérivée de J nécessite donc la résolution de deux systèmes linéaires : l’un pour le calcul de u(v), l’autre
pour le calcul de p = 2A−1 (u(v) − u0 ).

Question 3. On présente ici une méthode générale permettant de déterminer directement le système
vérifié par l’état adjoint p. Pour tout (u, v) ∈ Rn × Rn , on pose

J(u, v) = j(u)

Le problème de minimisation de Jc est équivalent au problème de minimisation de J(u, v) sous la

contrainte Au = f + v. Introduire le lagrangien L(u, v, p) associé à ce problème.

6
Correction : Le lagrangien associé au système est

L(u, v, p) = j(u) − (Au − f − v).p

Question 4. Calculer la dérivée de L par rapport à u et v.

Correction :
∂L
⟨ , w⟩ = ⟨j ′ (u), w⟩ − Aw.p
∂u
∂L
⟨ , w⟩ = w.p.
∂v

Question 5. En remarquant que pour tout v ∈ Rn ,

Jc (v) = L(u(v), v, p),

Exprimer Jc′ en fonction des dérivées partielles de L par rapport à u et v et de u(v) par rapport à v.
Correction :
Pour tout p, on a
Jc (v) = L(u(v), v, p).
En dérivant cette expression, on obtient
∂L ∂L
Jc′ (v) = (u(v), v, p).u′ (v) + (u(v), v, p).
∂u ∂v

Question 6. Montrer qu’on peut choisir astucieusement p de telle sorte qu’il ne soit pas nécessaire de
calculer la dérivée de u(v) par rapport à v pour obtenir Jc′ .
Correction :
Il suffit de choisir p tel que
∂L
(u(v), v, p) = 0,
∂u
c’est à dire
⟨j ′ (u(v)), w⟩ = Aw.p = Ap.w
pour tout w ∈ Rn , soit encore
p = 2A−1 (u(v) − u0 ).
On retrouve l’expression de Jc′ précédente.