Chapitre III. Minimisation avec contraintes. Conditions de minimalité
** Exercice III.9. Dans le processus de minimisation d’une fonction f deux fois
différentiable sur R n , la « direction de Newton » à partir d’un point x k où
∇f (x k ) = 0 et ∇ 2 f (x k ) est définie positive est obtenue
– soit en minimisant d −→ →∇f (x k ) , d +
1
2
∇ 2 f (x k ) d, d
sur R n
– soit en minimisant d −→ →∇f (x k ) , d sous la contrainte
∇ 2 f (x k ) d, d
1.
Montrer que les directions obtenues comme solutions de ces deux problèmes
de minimisation sont les mêmes à une constante positive multiplicative près.
Solution : Le premier problème (sans contraintes) est celui de la minimisation
d’une fonction quadratique strictement convexe sur R n : sa solution est celle
de l’équation
∇f (x k ) + ∇
2 f (x k ) d = 0, soit d = −
∇
2 f (x k )
−1 ∇f (x k ) .
Dans le deuxième problème (avec contrainte) il s’agit de minimiser une
forme linéaire non nulle sur le convexe compact (elliptique) décrit par l’inégalité
∇ 2 f (x k ) d, d
1.
La solution d est donc nécessairement sur la frontière de l’ensemblecontrainte (frontière d’équation
∇ 2 f (x k ) d, d
= 1) et elle est caractérisée
par l’existence de μ 0 (le multiplicateur) tel que
∇f (x k ) + 2μ∇
2 f (x k ) d = 0.
Comme μ = 0 (car ∇f (x k ) = 0), il s’ensuit d = −
∇ 2 f (x k )
−1 ∇f (x k )
2μ
.
** Exercice III.10. Minimisation sur le simplexe-unité de R n
1 ◦ ) Soit Λ 3 := {(x 1 , x 2 , x 3 ) ∈ R 3 | x 1 + x 2 + x 3 = 1, x 1 0, x 2 0,
x 3 0}.
Dessiner Λ 3 et déterminer le cône tangent et le cône normal à Λ 3 en
(1/3, 1/3, 1/3) , (0, 1/2, 1/2) et (0, 0, 1) respectivement. (On ne demande pas
une démonstration ou un calcul détaillé mais une réponse au vu des définitions
et de la représentation graphique de Λ 3 .)
2 ◦ ) Soit Λ n le simplexe-unité de R n , c’est-à-dire
Λ n :=
x = (x 1 , . . . , x n ) ∈ R n | x i 0 pour tout i et
n
i=1
x i = 1
.
76
** Exercice III.9. Dans le processus de minimisation d’une fonction f deux fois
différentiable sur R n , la « direction de Newton » à partir d’un point x k où
∇f (x k ) = 0 et ∇ 2 f (x k ) est définie positive est obtenue
– soit en minimisant d −→ →∇f (x k ) , d +
1
2
∇ 2 f (x k ) d, d
sur R n
– soit en minimisant d −→ →∇f (x k ) , d sous la contrainte
∇ 2 f (x k ) d, d
1.
Montrer que les directions obtenues comme solutions de ces deux problèmes
de minimisation sont les mêmes à une constante positive multiplicative près.
Solution : Le premier problème (sans contraintes) est celui de la minimisation
d’une fonction quadratique strictement convexe sur R n : sa solution est celle
de l’équation
∇f (x k ) + ∇
2 f (x k ) d = 0, soit d = −
∇
2 f (x k )
−1 ∇f (x k ) .
Dans le deuxième problème (avec contrainte) il s’agit de minimiser une
forme linéaire non nulle sur le convexe compact (elliptique) décrit par l’inégalité
∇ 2 f (x k ) d, d
1.
La solution d est donc nécessairement sur la frontière de l’ensemblecontrainte (frontière d’équation
∇ 2 f (x k ) d, d
= 1) et elle est caractérisée
par l’existence de μ 0 (le multiplicateur) tel que
∇f (x k ) + 2μ∇
2 f (x k ) d = 0.
Comme μ = 0 (car ∇f (x k ) = 0), il s’ensuit d = −
∇ 2 f (x k )
−1 ∇f (x k )
2μ
.
** Exercice III.10. Minimisation sur le simplexe-unité de R n
1 ◦ ) Soit Λ 3 := {(x 1 , x 2 , x 3 ) ∈ R 3 | x 1 + x 2 + x 3 = 1, x 1 0, x 2 0,
x 3 0}.
Dessiner Λ 3 et déterminer le cône tangent et le cône normal à Λ 3 en
(1/3, 1/3, 1/3) , (0, 1/2, 1/2) et (0, 0, 1) respectivement. (On ne demande pas
une démonstration ou un calcul détaillé mais une réponse au vu des définitions
et de la représentation graphique de Λ 3 .)
2 ◦ ) Soit Λ n le simplexe-unité de R n , c’est-à-dire
Λ n :=
x = (x 1 , . . . , x n ) ∈ R n | x i 0 pour tout i et
n
i=1
x i = 1
.
76