Optimisation

Master 1 Statistique & Data Science, Ingénierie Mathématique, 2020-2021

Examen du mercredi 5 mai 2021

Corrigé

Exercice 1. (sur environ 9 points)

On considère la fonction f : R2 → R définie par

f (x1 , x2 ) = x21 + x2 .

1. Etude de f sur R2 : Répondre rigoureusement aux questions suivantes.

1.a) La fonction f est-elle convexe sur R2 ?
1.b) La fonction f est-elle strictement convexe sur R2 ?
1.c) La fonction f atteint-elle une valeur minimale sur R2 ?
On considère maintenant l’ensemble

U = {x = (x1 , x2 ) ∈ R2 , x21 + x22 ! 13 et x1 + x2 " −1}.

2. Propriétés de l’ensemble U :
2.a) Représenter graphiquement U et préciser les coordonnées des points d’intersection
qui apparaissent naturellement.
2.b) Montrer que U est un ensemble convexe et compact.
2.c) Introduire deux fonctions g1 et g2 pour décrire U comme un ensemble de contraintes
inégalités et vérifier que tous les points de U vérifient la qualification de contraintes
de Kuhn-Tucker (QCKT).
On cherche désormais à résoudre le problème d’optimisation sous contraintes :

Trouver x! tel que x! ∈ U et f (x! ) = min f (x) (P )

x∈U

3. Justifier que le problème (P ) admet au moins une solution.

4. Justifier que x ∈ U est solution de (P ) si et seulement si x vérifie les conditions de
Karush-Kuhn-Tucker (KKT) que l’on précisera.
5. Déterminer toutes les solutions de (P ) à l’aide des conditions KKT.
Solution de l’exercice 1.
1. Etude f sur R2 : f est quadratique sur R2 avec pour matrice A, vecteur b et constante c
! " ! "
2 0 0
A= , b= , c = 0.
0 0 −1

1.a) A est positive donc f est convexe sur R2 .

1.b) A n’est pas positive donc f n’est pas strictement convexe sur R2 .
1.c) Le système linéaire Ax = b n’admet pas de solution donc f n’admet pas de mini-
mum sur R2 et inf R2 f = −∞.

1
2. Propriétés de l’ensemble U :
2.a) U est l’intersection d’un disque avec un demi-plan.

(−3, 2)

(2, −3)

Pour les points d’intersection on résout le système

# 2
x1 + x22 = 13
x1 + x2 = −1

Par substituion, x2 = −1 − x1 et x21 + (−1 − x1 )2 = 13 soit x21 + x1 − 6 = 0.

Les racines de ce trinôme sont x1 = 2 et x1 = −3. Finalement les deux points
d’intersection sont (2, −3) et (−3, 2).
2.b) U est convexe en tant qu’intersection de deux convexes (un disque et un demi-plan).
U est compact car c’est l’intersection non vide d’un compact (disque) et d’un fermé
(demi-plan).
2.c) On pose g1 (x1 , x2 ) = x21 + x22 − 13 et g2 (x1 , x2 ) = −x1 − x2 − 1. Alors

U = {x = (x1 , x2 ) ∈ R2 , g1 (x1 , x2 ) ! 0 et g2 (x1 , x2 ) ! 0}.

g1 et g2 sont C 1 sur R2 . On a pour tout x ∈ R2 ,

! " ! "
2x1 −1
∇g1 (x1 , x2 ) = et ∇g2 (x1 , x2 ) = .
2x2 −1
Montrons tous les points de U vérifient QCKT. Soit x ∈ U . Discutons selon le
nombre de contraintes actives :
— Si aucune contrainte n’est active (g1 (x1 , x2 ) < 0 et g2 (x1 , x2 ) < 0) il n’y a rien
à vérifier.
— Si " 1 , x2 ) = 0 et g2 (x1 , x2 ) < 0, alors l’unique vecteur ∇g1 (x1 , x2 ) =
! g1 (x
2x1
forme bien une famille libre car x ∕= 0 sur le bord du disque.
2x2 ! "
−1
— Si g1 (x1 , x2 ) < 0 et g2 (x1 , x2 ) = 0 alors ∇g2 (x1 , x2 ) = forme une
−1
famille libre car il est non nul.

2
 — Si g1 (x1 , x2 ) = 0 et g2 (x1 , x2 ) = 0 alors d’après la question 2.a) on est soit sur
(2, −3) soit sur (−3, 2) et alors
#! " ! "$ #! " ! "$
4 −1 −6 −1
{∇g1 (x1 , x2 ), ∇g2 (x1 , x2 )} = , ou ,
−6 −1 4 −1

qui sont des familles libres de vecteurs.

Dans tous les cas x vérifie QCKT.
3. On minimise une fonction continue sur un compact, il y a au moins une solution.
4. Comme f est convexe de classe C 1 , g1 et g2 sont convexes de classe C 1 , on a le théorème
KKT cas convexe qui assure que x est solution si et seulement les conditions KKT sont
vérifiées, à savoir il existe µ1 , µ2 " 0 tels que

∇f (x) + µ1 ∇g1 (x) + µ2 ∇g2 (x) = 0 et µ1 g1 (x) = µ2 g2 (x) = 0.

On obtient ici le système

! " ! " ! " ! "
2x1 2x1 −1 0
+µ1 +µ2 = et µ1 (x21 +x22 −13) = µ2 (−x1 −x2 −1) = 0.
1 2x2 −1 0

5. Déterminons toutes les solutions de (P ) à l’aide des conditions KKT.

On résout le système ci-dessus en étudiant le nombre de contraintes actives.
— Si aucune contrainte n’est active, on cherche alors un point critique de f , il n’y a pas
de solution.
— Si g1 (x1 , x2 ) = 0 et g2 (x1 , x2 ) < 0, alors µ1 " 0 quelconque et µ2 = 0 et
% %
& 2x1 + 2µ1 x1 = 0 & x1 = 0
1 + 2µ1 x2 = 0 ⇔ 2µ1 x2 = −1 √
' '
x21 + x22 = 13 x2 = ± 13
√
Comme µ1 " √ 0 on en déduit x 2 < 0 . Mais alors le point (0, − 13) est tel que
g2 (x1 , x2 ) = 13 − 1 > 0 donc il n’appartient pas à U .
— Si g1 (x1 , x2 ) < 0 et g2 (x1 , x2 ) = 0 alors µ2 " 0 quelconque et µ1 = 0 et
% %
& 2x1 − µ2 = 0 & x1 = 12
1 − µ2 = 0 ⇔ µ2 = 1
' '
x1 + x2 = −1 x2 = − 32

On trouve donc une solution qui est ( 12 , − 32 ). On vérifie que ( 12 , − 32 ) ∈ U :

! "
1 3 5 √
g1 ,− = − 13 < 0.
2 2 2

— Si g1 (x1 , x2 ) = 0 et g2 (x1 , x2 ) = 0 alors d’après la question 2.a) on est soit sur (2, −3)
soit sur (−3, 2). On peut résoudre le système dans chaque cas pour voir qu’il y a des
problèmes de signe sur µ1 et µ2 . On peut aussi se contenter d’évaluer f sur ces deux
points et comparer avec la valeur pour ( 12 , − 32 ). On a

1 3 1 3 5
f( , − ) = − = − .
2 2 4 2 4

3
 Par ailleurs,
1 3
f (2, −3) = 4 − 2 = 1 > f ( , − )
2 2
1 3
f (−3, 2) = 9 + 2 = 11 > f ( , − )
2 2
donc ces deux points ne sont pas des solutions.
En conclusion le problème (P ) admet une unique solution qui est ( 12 , − 32 ).
Exercice 2. (sur environ 16 points)
Dans cet exercice on considère g : Rn → R une fonctionnelle quadratique
1
g(x) = 〈Ax, x〉 − 〈b, x〉 + c,
2
où A ∈ Mn (R) est une matrice carrée symétrique définie positive, b ∈ Rn et c ∈ R.

Partie I : Propriétés générales

On commence par redémontrer des résultats de cours.

1. Justifier que g est de classe C ∞ sur Rn et prouver que pour tout x ∈ Rn ,

∇g(x) = Ax − b et ∇2 g(x) = A.

2. Redémontrer rigoureusement que g admet un unique minimum global x! = A−1 b.

Partie II : Convergence de l’algorithme de gradient à pas fixe

Dans cette partie de l’exercice on étudie la convergence de l’algorithme de descente de

gradient à pas fixe appliqué à la fonctionnelle quadratique g . Pour une fonction quelconque
f : Rn → R, cet algorithme est décrit par le pseudo-code suivant :

Algorithme 1 : Algorithme de descente de gradient à pas fixe

Données : Un point initial x(0) ∈ Rn , un seuil de tolérance ε > 0, un pas fixe t > 0
Résultat : Un point x ∈ Rn proche de x!
Initialiser x :
x ← x(0) ;
k ← 0;
tant que ,∇f (x), > ε faire
1. Mettre à jour x avec le pas fixe t dans la direction de descente −∇f (x(k) ) :
x ← x(k+1) = x(k) − t∇f (x(k) ) ;
k ← k + 1;
fin
Dans la suite de cette partie (x(k) )k∈N désigne la suite de vecteurs obtenues en appliquant
l’Algorithme 1 à la fonction g avec un pas t > 0 et en partant de d’un point initial x(0) ∈ Rn .
3. Soit k ∈ N. Montrer que

x(k+1) − x! = (In − tA)(x(k) − x! ).

En déduire une expression de x(k) − x! en fonction de A, t, et x(0) − x! .

4
 4. Soit 0 < λ1 ! λ2 ! · · · ! λn les valeurs propres de A et u1 , u2 , . . . , un des vecteurs
propres associés formant une base orthonormée de Rn . En introduisant la décomposition
du vecteur x(0) − x! dans la base (u1 , u2 , . . . , un ), montrer que la suite (x(k) )k∈N converge
vers x! quelque soit la valeur de x(0) si et seulement si

∀i ∈ {1, . . . , n}, |1 − tλi | < 1.

5. Montrer que

∀i ∈ {1, . . . , n}, |1 − tλi | ! max(|1 − tλ1 |, |1 − tλn |).

6. En déduire l’intervalle des valeurs de t pour lesquelles l’Algorithme 1 converge et montrer

que
,x(k) − x! , ! max(|1 − tλ1 |, |1 − tλn |)k ,x(0) − x! ,.
7. Tracer l’allure des graphiques des fonctions t .→ |1 − tλ1 | et t .→ |1 − tλn |. Pour quelle
valeur de t le membre de droite de l’inégalité précédente tend-il le plus vite vers 0 ?

Partie III : Algorithme de gradient à pas fixe avec moment

On considère à nouveau une fonction f : Rn → R générique. L’algorithme de gradient à

pas fixe t > 0 avec moment β > 0 et point initial x(0) ∈ Rn consiste à construire la séquence
de vecteurs (x(k) )k∈N telle que

x(1) = x(0) − t∇f (x(0) ),

∀k " 1, x(k+1) = x(k) − t∇f (x(k) ) + β(x(k) − x(k−1) ).

En pratique l’algorithme est arrêté avec le même critère d’arrêt que l’Algorithme 1.
8. (sur 4 points) On suppose que les fonctions
function fx = f(x) et function gfx = gradf(x)
sont définies dans scilab. Ecrire une fonction scilab
function [Xk,FXk] = algo_moment(x0, eps, t, bet, f, gradf)
qui prend en entrées un point initial x(0) ∈ Rn , un seuil de tolérance ε > 0, et deux
paramètres t > 0 et β > 0, les fonctions pour évaluer f et ∇f . La fonction renvoie la
matrice Xk (de taille n par nombre d’itérations) contenant la liste des vecteurs x(k) donnée
par l’algorithme de gradient à pas fixe t > 0 avec moment β > 0 ainsi que la liste des
valeurs Fxk de la fonctionnelle f aux points x(k) . On veillera à ajouter une condition pour
limiter le nombre d’itérations à 10 000.
On considère de nouveau la fonction quadratique g(x) = 12 〈Ax, x〉 − 〈b, x〉 + c. Soit (x(k) )
la suite de vecteurs obtenue par l’algorithme de gradient à pas fixe t > 0 avec moment β > 0
appliqué à g . On introduit la suite de vecteurs
! (k+1) "
x
(k)
y = ∈ R2n
x(k)
! !"
x
et on pose également y =!
∈ R2n .
x!

5
 9. Montrer que la suite y (k) − y ! vérifie une équation de récurrence de la forme
y (k+1) − y ! = T (y (k) − y ! )
(bien préciser l’expression de T ).
10. Que faut-il faire pour établir la convergence de l’algorithme de gradient à pas fixe t > 0
avec moment β > 0 appliqué à g ? Peut-on faire le même raisonnement qu’à la ques-
tion 4 ?
Solution de l’exercice 2.
1. f est de classe C ∞ (Rn ) car polynomiale de degré 2. Pour tout x ∈ Rn ,
1
f (x + h) = f (x) + 〈Ax − b, h〉 + 〈Ah, h〉.
2
Par Cauchy-Swharz, 〈Ah, h〉 ! ,Ah,,h, ! ,A,,h, = oh→0 (,h,). Donc f est diffé-
2

rentiable en x et ∇f (x) = Ax − b. x .→ ∇f (x) = Ax − b est affine de matrice A, sa

différentielle est ∇2 f (x) = A.
2. Pour tout x ∈ Rn , ∇2 f (x) = A est définie positive, donc f est strictement convexe. Ainsi
f admet au plus un minimum global x! et il est caractérisé par l’équation ∇f (x) = 0. Or
comme A est inversible,
∇f (x) = 0 ⇔ Ax = b ⇔ x = A−1 b.
Et donc f admet un unique minimum global x! égal à A−1 b.
3. On peut (par exemple) partir du terme de droite.
(In − tA)(x(k) − x! ) = x(k) − t(Ax(k) − Ax! ) − x! .
Or Ax! = b, et donc Ax(k) − Ax! = Ax(k) − b = ∇f (x(k) ). Ainsi,
(In − tA)(x(k) − x! ) = x(k) − t∇f (x(k) ) − x! = x(k+1) − x! .
On peut aussi écrire les équations
x(k+1) = x(k) − t∇f (x(k) ) et x! = x! − t∇f (x! )
et les soustraire pour obtenir l’équation demandée. Par récurrence immédiate on obtient
x(k) − x! = (In − tA)k (x(0) − x! ).
4. Les vecteurs propres (u1 , u2 , . . . , un ) de A sont aussi des vecteurs propres de la matrice
In − tA dont les valeurs propres sont 1 − tλi . Si on note
n
(
(0) !
x −x = α i ui
i=1

la décomposition de x(0) − x! dans la base (u1 , u2 , . . . , un ), on a alors

) n * n n
( ( (
(k) ! k k
x − x = (In − tA) α i ui = αi (In − tA) ui = αi (1 − tλi )k ui .
i=1 i=1 i=1

Alors
+ x(k) −
, x! tend vers 0 quelque soit x(0) si et seulement si pour tout i la suite
(1 − tλi )k k∈N tend vers 0. On en déduit que x(k) − x! tend vers 0 quelque soit x(0)
si et seulement si
∀i ∈ {1, . . . , n}, |1 − tλi | < 1.

6
 5. Soit i ∈ {1, . . . , n}. On a λ1 ! λi ! λn et donc

1 − tλn ! 1 − tλi ! 1 − tλ1 .

Si 1 − tλi " 0, alors on en déduit que

0 ! 1 − tλi = |1 − tλi | ! 1 − tλ1 = |1 − tλ1 |.

Si 1 − tλi ! 0, alors on en déduit que

0 ! −(1 − tλi ) = |1 − tλi | ! −(1 − tλn ) = |1 − tλn |.

Dans les deux cas on a bien

|1 − tλi | ! max(|1 − tλ1 |, |1 − tλn |).

6. Finalement, il suffit que la condition |1 − tλi | < 1 soit vérifiée pour i = 1 et i = n. Or

2
|1 − tλ1 | < 1 ⇔ −1 < 1 − tλ1 < 1 ⇔ 0 < t <
λ1
et de même, |1 − tλn | < 1 équivaut à 0 < t < λ2n . Comme λ1 ! λn , t < λ2n implique
t < λ21 . Au final, l’algorithme converge pour t tel que t ∈]0, λ2n [.
On vient de montrer que ,In − tA,Mn (R) = max(|1 − tλ1 |, |1 − tλn |). Or on a

,x(k) − x! , = ,(In − tA)k (x(0) − x! ), ! ,In − tA,kMn (R) ,(x(0) − x! ),,

d’où l’inégalité annoncée.

7. En traçant le graphe des deux fonctions, on voit que la fonction

t .→ max(|1 − tλ1 |, |1 − tλn |)

est minimale lorsque les deux courbes se croisent, soit au point pour lequel

tλn − 1 = 1 − tλ1

ce qui donne t = 2
λ1 +λn
.
8. Par rapport à la descente de gradient standard, la seule difficulté consiste à introduire une
variable supplémentaire pour retenir la valeur xk−1 .

function [Xk,FXk] = algo_moment(x0, eps, t, bet, f, gradf)

// Initialisation
x = x0
k = 0
gfx = gradf(x)
sqngfx = gfx’*gfx
Xk = x
FXk = f(x)
// Premiere iteration
xk = x
x = xk-t*gfx

7
gfx = gradf(x)
sqngfx = gfx’*gfx
Xk = [Xk,x]
FXk = [FXk,f(x)]
k = k+1
xkm = xk // variable a l’iteration k-1
xk = x
// Iterations suivantes
while(sqngfx>eps^2 & k < 10000)
x = xk-t*gfx + bet*(xk-xkm)
gfx = gradf(x)
sqngfx = gfx’*gfx
Xk = [Xk,x]
FXk = [FXk,f(x)]
k = k+1
xkm = xk
xk = x
end
endfunction

9. On a, en utilisant la question 3,

x(k+2) − x! = x(k+1) − t∇f (x(k+1) ) + β(x(k+1) − x(k) ) − x!

= (In − tA)(x(k+1) − x! ) + β((x(k+1) − x! ) − (x(k) − x! ))
= ((1 + β)In − tA)(x(k+1) − x! ) − βIn (x(k) − x! ).

On en déduit que
! " ! "! "
(k+1) ! x(k+2) − x! (1 + β)In − tA −βIn x(k+1) − x!
y −y = = .
x(k+1) − x! In 0 x(k) − x!

10. Il faut montrer que T n tend vers 0, ce qui est équivalent à dire que la valeur propre de
module maximale (rayon spectral) est strictement inférieure à 1. Cette fois-ci la matrice
n’est pas symétrique et donc pas forcément diagonalisable. Il faudrait faire une étude
spécifique pour lier les valeurs propres de T à celles de A.