1

UNIVERSITE Joseph KI-ZERBO Année 2019-2020

UFR ST
M1S2 INFO
TD DE RO

Exercice 1. On suppose J différentiable en tout point de K. Soit α ≥ 0, montrer que les propriétés
suivante sont équivalentes :
i) J est α-convexe sur K.
α
ii) ∀(u, v)2 ∈ K J(v) ≥ J(u)h∇J(u), v − ui + kv − uk2 .
2
ii) ∀(u, v)2 ∈ K h∇J(v) − ∇J(u), v − ui ≥ αkv − uk2 .

Exercice 2. Pour (x, y, z) 6= (0, 0, 0), on pose

1
f (x, y, z) = p .
x2 + y 2 + z 2

Les extrema évantuels de f par la méthode du gradient.

Exercice 3. Soient n, p ∈ N deux entiers non nuls. Soient A ∈ Mp,n (R) une matrice rectangulaire,
b ∈ Rp un vecteur. On définit la fonction f : Rn → R par
1
f (x) = kAx − bk2 .
2
Attention on utilisera la même notation pour la norme et le produit scalaire dans Rn et dans Rp , mais
les vecteurs ne sont a priori pas de la même taille !
1. Montrer que f est une fonctionnelle quadratique et préciser la matrice carrée A0 ∈ Mn (R), le
vecteur b ∈ Rn et la constante c ∈ R associés à f .
2. Donner l’expression du gradient ∇f (x) et de la matrice hessienne ∇2 f (x) de f en tout point
x ∈ Rn (on pourra se référer à un résultat du cours plutôt que de faire les calculs).
3. Montrer que f est convexe.
4. Montrer que f est strictement convexe si et seulement si ker(A) = {0}.
5. Soit x ∈ Rn tel que ∇f (x) 6= 0. Rappeler la définition d’une direction de descente d ∈ Rn au
point x et montrer que d ∈ Rn est une direction de descente si et seulement si

hAx − b, Adi < 0, en particulier Ad 6= 0.

6. Soit x ∈ Rn tel que ∇f (x) 6= 0 et d une direction de descente au point x. Montrer que le
problème d’optimisation
inf f (x + td).
t∈R

admet une unique solution donnée par

h∇f (x), di
t∗ = .
kAdk2

Exercice 4. On considère une fonction F convexe définie sur un espace de Hilbert X. On suppose que
∇F est L-Lipschitz, et que F admet un minimiseur.

UFR SEA / BURKINA FASO I. ZABSONRE ©2021

 2

1. Montrer que pour tout x, y ∈ X,

L
(1) F (x) + h∇F (x), x − yi + kx − yk2 ≥ F (y).
2
Montrer que f admet un minimum sur R.
2. On propose l’algorithme suivant : pour un point donné x, on appelle y = T (x) le minimiseur de
la fonction quadratique
L
y → F (x) + h∇F (x), x − yi + kx − yk2
2
qui majore F. x0 ∈ X étant donné on pose xn = T n (x0 ). Quel est cet algorithme ?
3. Montrer que si Φ est α-convexe et x∗ un minimiseur de Φ, alors pour tout x,
α
Φ(x) ≥ Φ(x∗ ) + kx − x∗ k2 ≥ F (y).
2
4. Montrer la formule suivante, vraie pour tous x, y ∈ X
L L
(2) F (y) + ky − xk2 ≥ F (T x) + ky − T xk2 .
2 2
On rappelle que F étant convexe, F (y) ≥ F (x)i∇F (x), x − yh. On utilisera le fait que T x est
minimiseur d’un problème L-convexe, et l’inégalité 1.
5. En prenant x = y = xn (et T x = xn+1 ) dans l’inégalité 2, vérifier que F (xn ) décroit. En prenant
y = x∗ , un minimiseur de F dans l’inégalité 2, et x = y = xn , T x = xn+1 , montrer que
2
(3) (F (xn+1 ) − F (x∗ )) ≤ kxn − x∗ k2 ≥ +kxn+1 − x∗ k2 .
L
kx0 − x∗ k2
En déduire que pour tout k ≥ 0, F (xk ) − F (x∗ ) ≤ . Que peut-on dire de ce type de
2k
convergence ?
6. On suppose maintenant que F est aussi α-convexe : que devient l’inégalité 3 ? En déduire la
convergence de xn vers x∗ , et la vitesse de convergence.
7. ”Gradient projeté” : on suppose que l’on s’intéresse maintenant au problème

min F (x).
x∈K

où K est un convexe de X sur lequel ”on sait projeter” (par exemple, X = RN et K = (R+ )N ).
Répondre à la question 2. (en rajoutant la contrainte x ∈ K dans les minimisations) et montrer
que l’inégalité 2 (question 4.) est encore vraie lorsque y ∈ K. Qu’en déduit-on ?

Exercice 5.
1. Soit n ∈ N∗ . On désigne par h; i le produit scalaire euclidien de Rn . Soit A une matrice symé-
trique définie positive, b ∈ Rn et c ∈ R. On considère le problème d’optimisation quadratique
1
inf J(x) avec J(x) = hAx, xiet et K = {x ∈ Rn : hx, bi = c}.
x∈K 2
Proposer une approche numérique de résolution que vous décrirez très précisément. On explici-
tera notamment l’étape de modélisation et l’algorithme retenu.

UFR SEA / BURKINA FASO I. ZABSONRE ©2021

 3

2. Soit k > 0. On définit sur R2 la fonction appelée Rosenbrock banana, par la relation

f (x, y) = (x − 1)2 + k(x2 − y)2 .

On souhaite minimiser f sur R2 à l’aide de la méthode du gradient à pas optimal à partir de

l’initialisation x0 = (0, 0).
(a) Décrire cet algorithme. Montrer qu’il existe un choix optimal de pas à la première itération
et qu’il appartient à ]0, 1[.
(b) De façon plus générale, comment feriez-vous pour déterminer numériquement le pas optimal
à chaque itération ?
(c) À votre avis, quel type de problème numérique rencontre cet algorithme lorsque k prend des
valeurs trop grandes ?

Exercice 6. Déterminer les extrema (locaux et globaux) des fonctions f suivantes sur leur domaine
de définition sous la contrainte g = 0.
1. f (x, y, z) = x − y + z, g(x, y, z) = x2 − y 2 + z 2 − 4
2. f (x, y) = xy, g(x, y) = x2 + y 2 − x − y.
3. f (x, y) = ln(x − y), g(x, y) = x2 + y 2 − 2.
x2 y2
4. f (x, y) = x2 + y 2 , g(x, y) = − .
4 16
5. f (x, y) = 2x + y, g(x, y) = x2 + xy − y 2 − 1.
1 1 1 1 1
6. f (x, y) = + , g(x, y) = 2 + 2 − .
x y x y 2
7. f (x, y) = x + y + (y − x) , g(x, y) = x2 + y 2 + 2y − 2x?6.
2 2 2

Exercice 7. On considère le problème suivant :

 Minimiser J(x, y) = x3 y


(P ) :
sous les contraintes x3 − y − 1 = 0.


1. Résoudre (P) en utilisant la méthode des multiplicateurs de Lagrange.

2. Retrouver le résultat en se ramenant à la minimisation sans contrainte d’une fonction d’une
variable réelle.

Exercice 8. On cherche à calculer la projection d’un point y ∈ R2 sur l’ensemble

C = {x ∈ R2 : x21 ≤ x2 }.

1. Rappeler l’énoncé du théorème de projection sur un convexe.

2. A quel ensemble géométrique correspond C ? Faire une représentation graphique de C.
3. Soit g : E → R une fonction, où E est un espace vectoriel, et Cg = {x ∈ E : g(x) ≤ 0}.
Montrer que si g est convexe alors Cg est convexe.
4. Utiliser le résultat précédent pour montrer que C est convexe.
5. Montrer que pour tout y ∈ R2 le problème de projection sur C admet une solution unique y ∗ et
écrire ce problème sous la forme d’un problème d’optimisation sous contrainte inégalité d’une
fonctionnelle J.

UFR SEA / BURKINA FASO I. ZABSONRE ©2021

 4

6. Appliquer la méthode des multiplicateurs de Lagrange au problème d’optimisation précédent, et

montrer que dans le cas non trivial on se ramène à une équation du troisième degré (on ne
cherchera pas à résoudre cette équation pour y quelconque).
7. Calculer y ∗ dans les cas suivants : y = (−1, 12 ), y = (3, 0), y = (0, 1). Sur le graphique de la
question 1, représenter le segment joignant y à y ∗ dans les trois cas.

Exercice 9.
1. Soit C un ensemble convexe fermé non vide de Rn , et ΠC l’application de projection sur C. Pour
τ ∈ Rn on note Cτ = C + τ = {x + τ, x ∈ C}. Déterminer l’expression de la projection ΠCτ (x)
de x ∈ Rn en fonction de ΠC et de τ .
2. On note D le disque fermé de centre (0, 0) et de rayon 1 dans R2 , et C le disque fermé de centre
(1, 0) et de rayon 1. Rappeler sans démonstration l’expression de la projection sur D, et déduire
de la question précédente l’expression de la projection sur C.
3. Montrer que le problème
 2 2
 Minimiser J(x, y) = ex +y − x + y
(P ) :
pour X = (x, y) ∈ C.


admet une solution unique.

4. Expliciter l’algorithme de gradient projeté pour la résolution de (P).
5. Montrer que J est elliptique (indication : montrer que les valeurs propres λ1 et λ2 de la matrice
2 2
M telle que HJ (x, y) = 2ex +y M sont telles que λ1 +λ2 ≥ 2 et λ1 +λ2 = λ1 λ2 +1, et en déduire
que λ1 ≥ 1 et λ2 ≥ 1, mais que ∇J n’est pas lipschitzienne (regarder par exemple ∇J(2x, 0) −
∇J(x, 0)). Pensez-vous malgré tout que l’algorithme de gradient projeté peut converger ?

Exercice 10. Soit λ ∈ R fixé. On considère le problème d’optimisation suivant dans

 Minimiser J(x, y) = x2 + y 2 − 2λy + λ2



(Pλ ) :
sous les contraintes y ≤ 2x2 et y ≥ x2 .


1. Montrer que le problème (Pλ ) admet une solution quel que soit λ.
2. Quels dont les points réguliers de C vis-à-vis des conditions de Karush-Kuhn- Tucker ?
3. Déterminer les points réguliers de C qui vérifient les conditions de Karush-Kuhn- Tucker pour
le problème (Pλ ).
4. En déduire les solutions de (Pλ ) en discutant en fonction du paramètre λ.
5. Interpréter géométriquement le problème et retrouver à la main les solutions sur la figure pour
les différents cas.

Exercice 11. Soit α ∈ R fixé. On considère le problème d’optimisation suivant dans

 Minimiser J(x, y) = x2 + (y − α)2



(Pα ) :
sous les contraintes y ≥ 0 et y ≤ x2 .


1. Montrer que le problème (Pα ) admet au moins une solution.

2. On note C l’ensemble des contraintes. Quels dont les points réguliers de C vis-à-vis des conditions
de Karush-Kuhn-Tucker ?

UFR SEA / BURKINA FASO I. ZABSONRE ©2021

 5

3. Ecrire les équations de Karush-Kuhn-Tucker pour le problème puis déterminer, en fonction de

la valeur de α, les points réguliers de C solutions de ces équations.
4. En déduire la ou les solutions de (Pα ) en discutant en fonction du paramètre α.
5. Interpréter géométriquement le résultat et faire une figure représentant l’ensemble C et les points
solutions dans les différents cas rencontrés.

Exercice 12. On cherche à résoudre le problème

 Minimiser J(x, y) = x2 + y 2 + z 2 sur K



(P ) :
avec K = {(x, y, z) ∈ R3 : x + y + z = 1 et x2 + y 2 ≤ 1}.


1. Montrer que le problème admet une unique solution.

2. Montrer que la contrainte est qualifiée en tout point.
3. Ecrire les conditions nécessaires d’optimalité du problème et en déduire la solution du problème
(P).

UFR SEA / BURKINA FASO I. ZABSONRE ©2021