Année Universitaire 2019-2020

Université Cadi Ayyad Travaux dirigés d’optimisation

ENSA, Marrakech Respensable : Z. ANKHILI

Correction du TD 3

Exercice 1. Soit S un ensemble convexe de Rn et f une fonction convexe sur S.

(1) Montrer que si x∗ , y ∗ sont deux minima globaux de f sur S, alors ∀λ ∈ [0, 1], λx∗ + (1 −
λ)y ∗ est un minimum global de f sur S.
x∗ et y ∗ deux minima globaux de f sur S. i.e.
∀ x ∈ S, f (x∗ ) = f (y ∗ ) ≤ f (x)
Soit λ ∈ [0, 1]. On a S est convexe donc λx∗ + (1 − λ)y ∗ ∈ S. Par conséquent,
f (x∗ ) ≤ f (λx∗ + (1 − λ)y ∗ ) (x∗ est un minimum global)
∗ ∗
≤ λf (x ) + (1 − λ)f (y ) (f
 est convexe)
∗
≤ f (x ) f (x∗ ) = f (y ∗ )
D’où f (x∗ ) = f (λx∗ + (1 − λ)y ∗ ) ce qui implique que λx∗ + (1 − λ)y ∗ est un minimum global de
f sur S.
(2) Supposons maintenant que f est strictement convexe. Montrer que f admet au plus
un minimum global sur S.
Supposons que f admet deux minima globaux x∗ 6= y ∗ . Puisque f est strictement convexe, on a
1 1 1 1
f ( x∗ + y ∗ ) < f (x∗ ) + f (y ∗ ).
2 2 2 2
1 1 1 1
Or f (x∗ ) = f (y ∗ ) donc f ( x∗ + y ∗ ) < f (x∗ ) absurde car x∗ + y ∗ ∈ S et x∗ est un minimum
2 2 2 2
global de f sur S.
Noter que f peut ne pas avoir un minimum global : par exemple la fonction exponentielle est
strictement convexe mais il n’admet pas un minimum.
Exercice 2. On considère le problème suivant :
x2 + y 2

 min
s.à
(x − 1)3 − y 2 = 0


(1) Montrer que la contrainte est qualifiée en tout point sauf (1, 0).
La contrainte est qualifiée au point (x, y) si ∇h(x, y) est linéairement indépendant (Ici la contrainte
est saturée puisque c’est une contrainte d’égalité).
∇h(x, y) est linéairement indépendant ⇐⇒ λ∇h(x, y) = 0 =⇒ λ = 0
⇐⇒ ∇h(x, y) 6= 0
3(x − 1)2
 
On a ∇h(x, y) = , donc ∇h(x, y) = 0 si et seulement si x = 1 et y = 0. D’où la
−2y
contrainte est qualifiée en tout point sauf (1, 0).
(2) Montrer qu’aucun point ne satisfait les conditions nécessaires de KKT.
Soit (x∗ , y ∗ ) un point réalisable différent de (1, 0). Si (x∗ , y ∗ ) vérifie les conditions nécessaire de
KKT alors ∃ µ ∈ R tel que
∇f (x∗ , y ∗ ) + µ∇h(x∗ , y ∗ ) = 0

h(x∗ , y ∗ ) = 0
 2x∗ + 3µ(x∗ − 1)2 = 0 (1)


2y ∗ − 2µy ∗ = 0 (2)
 ∗
(x − 1)3 + y ∗2 = 0 (3)

1
TD3 Zakia ANKHILI

(2) ⇐⇒ 2(1 − µ)y ∗ = 0

⇐⇒ y ∗ = 0 où µ = 1
Si y = 0, (3) implique que x∗ = 1 et en remplaçant dans (1), on trouve 2 = 0 absurde.
∗

Si µ = 1, (1) implique que 2x∗ + 3(x∗ − 1)2 = 0. i.e. 3x∗2 − 4x∗ + 3 = 0. Or ∆0 = 4 − 9 < 0
donc l’équation n’admet pas de solutions réelles.
Par conséquent aucun point ne vérifie les conditions nécessaires de KKT.
(3) Quel est le point qui réalise le minimum ? conclure.
D’après la question 2), aucun point realisable (x, y) 6= (1, 0) ne vérifie les conditions nécessaires
de KKT. Reste à vérifier si (1,0) est une solution optimale du problème. Soit (x, y) un point
réalisable du problème. On a alors y 2 = (x − 1)3 ≥ 0 donc x ≥ 1. Par conséquent,
f (x, y) = x2 + y 2 ≥ 1 = f (1, 0)
i.e. (1,0) est le minimum global de f sur l’ensemble des contraintes S = {(x, y)/ y 2 = (x − 1)3 }.
Conclusion. Il ne faut pas négliger l’hypothèse de la qualification des contraintes. Si S ∗ est
l’ensemble des solutions optimales d’un problème d’optimisation alors S ∗ ⊂ S1 ∪ S2 où S1 est
l’ensemble des points vérifiant les conditions nécessaires de KKT et S2 est l’ensemble des points
où les contraintes ne sont pas qualifiées.
N.B.
• Si x∗ ∈ S1 alors les contraintes sont qualifiées en x∗ .
• Dans notre exemple, S1 = ∅ et S2 = {(1, 0)}.
Exercice 3. Soit le problème
f (x) = −x1 − x2 − x2 x3 − x1 x3

min
(P ) s.à
x1 + x2 + x3 − 3 = 0
(1) Montrer que la fonction f n’est p pas coercive.
Soit xn = (0, 1, n). On a kxn k = 1 + n2 −−−−−→ +∞, mais f (xn ) = −1 − n −−−−−→ −∞
n→+∞ n→+∞
donc f n’est pas coercive.
(2) La fonction f est-elle convexe ?
   
−1 − x3 0 0 −1
∇f (x) =  −1 − x3  et Hf (x) =  0 0 −1 
−x2 − x1 −1 −1 0
√
On a det(Hf (x) − λI3 ) = λ(2 − λ2 ) donc les valeurs propres de Hf (x) sont 0 et ± 2. Alors
Hf (x) n’est pas semi-définie positive. Par conséquent, f n’est pas convexe.
Autre méthode (utilisation des mineurs principaux :) Une matrice est semi-définie
positive si tous ses mineurs principaux sont positives.
• Les mineurs principaux d’ordre 1
∆11 = ∆21 = ∆31 = 0 (Les éléments diagonaux de Hf (x)).
• Les mineurs principaux d’ordre 2
0 −1 0 −1 0 0
∆12 = = −1 < 0 ∆22 = = −1 < 0 ∆32 = =0
1 0 −1− 0 0 0
• Le mineur pricipal d’ordre 3
∆3 = det(Hf (x)) = 0.
On peut s’arrêter à ∆12 . Puisque ∆12 < 0 alors Hf (x) n’est pas semi-définie positive.
Remarques :
• Une matrice est semi-définie négative si et seulement si ses mineurs principaux ont des signes
alternés tel que le signe des mineurs principaux d’ordre impair est négative.
La matrice Hf (x) n’est pas semi-définie négative puisque ∆12 < 0
• Une matrice est semi-défini négative si et seulement si toutes ses valeurs propres sont néga-
tives.
(3) Déterminer les points vérifiant les conditions nécessaires de KKT.
La contrainte est affine donc elle est qualifiée en tout point. Soit x un point réalisable.

2
TD3 Zakia ANKHILI

x vérifie les conditions nécessaire de KKT s’il existe µ ∈ R tel que (x, µ) est la solution du système

 
 −1 − x3 + µ = 0 (1)
∇f (x) + µ∇h(x) = 0 −1 − x3 + µ = 0 (1)

⇔
h(x) = 0 
 −x 1 − x2 + µ = 0 (2)
x1 + x2 + x3 − 3 = 0 (3)


(1) implique que x3 = µ − 1 et (2) implique x2 = µ − x1 . En remplaçant dans (3), on trouve

2µ − 4 = 0. Ce qui donne µ = 2 ∈ R (on a une contrainte d’égalité). Donc x3 = 1.
Par conséquent, les points vérifiant les conditions nécessaires de KKT sont (x1 , 2 − x1 , 1), x1 ∈ R.
(4) Montrer que pour tout x ∈ R3 vérifiant x1 + x2 + x3 − 3 = 0, on a f (x) = (x1 + x2 − 2)2 − 4.
Soit x un poinr réalisable de (P ). On a x3 = 3 − x1 − x2 . En remplaçant dans l’expression de f ,
f (x) = −(x1 + x2 ) − x3 (x1 + x2 )
= −(x1 + x2 )(1 + x3 )
= −(x1 + x2 )(4 − x1 − x2 )
= −4(x1 + x2 ) + (x1 + x2 )2
= (x1 + x2 − 2)2 − 4.
(5) En déduire les solutions optimales du problème (P ). On a les contraintes sont qualifiées
en tout point. Alors, si le problème (P ) admet une solution globale ou locale donc elle est parmi
les points vérifiant les conditions nécessaires de KKT (Ici S2 = ∅).
• On ne peut pas utiliser le théorème d’existence car f n’est pas coercive (Attention : f n’est
pas coercive =⇒ 6 f n’admet pas de minimum global.)
• f n’est pas convexe donc on ne peut pas utiliser le résultat de convexité : les conditions
nécessaires de KKT sont suffisantes.
• Il reste à utiliser la définition du minimum global pour vérifier si les points vérifiant les
conditions nécessaires de KKT (x∗ = (x∗1 , 2 − x∗1 , 1), x∗1 ∈ R) sont des minima globaux ou
pas. On a f (x∗ ) = −4. Soit x un point réalisable de (P ), d’après la question (4)
f (x) − f (x∗ ) = (x1 + x2 − 2)2 ≥ 0
Par conséquent les points x∗ = (x∗1 , 2 − x∗1 , 1), x∗1 ∈ R sont les minima globaux de f sur
l’ensemble S = {x ∈ R3 x1 + x2 + x3 − 3 = 0}.
N.B. f n’est pas coercive mais elle admet une infinité de minima globaux.
Exercice 4. Soit le problème

 max −(x − 4)2 − (y − 4)2
s.à

(P ) x+y ≤4

x + 3y ≤ 9


(1) Justifier l’existence et l’unicité de la solution du problème (P ).

Chercher la solution de (P ) revient à chercher la solution du problème :

 min (x − 4)2 + (y − 4)2
s.à

x+y ≤4

x + 3y ≤ 9


Posons f (x, y) = (x − 4)2 + (y − 4)2 , g1 (x, y) = x + y − 4 et g2 (x, y) = x + 3y − 9. L’ensemble des

contraintes est
S = {(x, y) ∈ R2 /g1 (x, y) ≤ 0, g2 (x, y) ≤ 0}
• S est un ensemble fermé. En effet, on a S = g1−1 (] − ∞, 0]) ∩ g2−1 (] − ∞, 0]). Or g1 et g2 sont
continues et ]−∞, 0] est fermé donc gi−1 (]−∞, 0]), i = 1, 2 est fermé comme image réciproque
d’un fermé par une fonction continue. S est l’intersection de deux ensembles fermés ce qui
implique qu’il est fermé.  
• S est non borné. En effet, la suite (xn , yn ) définie par (xn , yn ) = (n + 4, −n) ∈ S
n
(g1 (xn , yn ) = 0 et g2 (xn , yn ) = −2n − 5) mais k(xn , yn )k2 = (n + 4)2 + n2 −−−−−→ +∞
n→+∞
• f est continue.

3
TD3 Zakia ANKHILI

• f est coercive car f (x, y) = k(x − 4, y − 4)k2 et si k(x, y)k → +∞ alors k(x − 4, y − 4)k → +∞.
Par conséquent, lim f (x, y) = +∞
k(x,y)k→+∞
• f est strictement convexe (Hf (x, y) = 2I2 est définie positive ∀(x, y) ∈ R2 ) et l’ensemble des
contraintes S est convexe (g1 et g2 sont affines donc elles sont convexes).
Conclusion :
• f est continue et coercive sur un fermé non borné S alors elle admet au moins un minimum
global sur S.
• f est strictement convexe sur l’ensemble convexe S alors elle admet au plus un minimum
global sur S.
On déduit que f admet un minimum global unique noté (x∗ , y ∗ ) sur S.
(2) Appliquer le théorème de Kuhn-Tucker pour la détermination de cette solution.
Les contraintes sont affines donc elles sont qualifiées en tout point. Par conséquent (x∗ , y ∗ ) vérifie
les conditions nécessaires de KKT. i.e. il existe λ∗1 , λ∗2 ≥ 0 tel que (x∗ , y ∗ , λ∗1 , λ∗2 ) est solution du
système :

 2(x − 4) + λ1 + λ2 = 0 (1)

∇f (x, y) + λ1 ∇g1 (x, y) + λ2 ∇g2 (x, y) = 0

 2(y − 4) + λ1 + 3λ2 = 0 (2)

 

λ1 g1 (x, y) = 0

(KKT ) ⇐⇒ λ1 (x + y − 4) = 0 (3)
λ2 g2 (x, y) = 0
λ (x + 3y − 9) = 0 (4)
 
2
 
(x, y) ∈ S
 

(x, y) ∈ S


Les égalités (3) et (4) sont équivalentes à quatre cas:

• Cas 1 : λ1 = λ2 = 0
(1) et (2) ⇒ x = y = 4. Or (4,4) n’est pas réalisable (x + y > 4) donc (4,4) ne vérifie pas
les conditions nécessaires de KKT.
• Cas 2 : λ1 = 0 et x + 3y − 9 = 0
(1) et (2) ⇐⇒

2(x − 4) + λ2 = 0 (1)
2(y − 4) + 3λ2 = 0 (2)
On a λ2 = 2(4 − x). En remplaçant dans (2), on trouve −6x + 2y + 16 = 0. La solution du
système

−6x + 2y + 16 = 0
x + 3y − 9 = 0
33 19
est (x, y) = ( , ). Or x + y > 4 donc (x, y) 6∈ S. Alors, (x, y) ne vérifie pas les conditions
10 10
nécessaires de KKT.
• Cas 3 : λ2 = 0 et x + y − 4 = 0
Le système KKT est equivalent à :

 2(x − 4) + λ1 = 0 (1)
2(y − 4) + λ1 = 0 (2)
x+y−4=0 (3)


(1) et (2) impliquent que λ1 = −2(x − 4) = −2(y − 4) ce qui donne x = y.

D’autre part (3) implique x = y = 2. Le point (2,2) est réalisable, calculons alors λ1 . On a
λ1 = 2(4 − x) = 4 > 0. D’où le point (2,2) vérifie les conditions nécessaires de KKT.
• Cas 4 : x + 3y − 9 = 0 et x + y − 4 = 0
La solution du système

x + 3y − 9 = 0
x+y−4=0
3 5
est (x, y) = ( , ) qui est un point realisable. En remplaçant dans le système KKT, on trouve
2 2

λ1 + λ2 = 5
λ1 + 3λ2 = 3

4
TD3 Zakia ANKHILI

3 5
Ce qui donne (λ1 , λ2 ) = (6, −1). Or λ2 = −1 < 0 donc ( , ) n’est pas un point KKT (il ne
2 2
vérifie pas les conditions nécessaires de KKT).
Conclusion : Il existe une unique solution de système KKT et puisque on sait que (x∗ , y ∗ )
est un point KKT donc (x∗ , y ∗ ) = (2, 2).
N.B.
(a) On peut ne pas étudier le cas 4. Puisqu’on sait que le problème est convexe (f est
convexe et S convexe), les conditions nécessaires de KKT sont suffisantes. Et puisque
le problème admet une unique solution alors le système KKT admet une unique solution
(x∗ , y ∗ , λ∗1 , λ∗2 ). Par conséquent, si on trouve un point KKT, l’étude des cas suivants
est inutile.
(b) La valeur optimale est −f (x∗ , y ∗ ) = −8.

Exercice 5. On considère le problème


1 T
min x Ax − bT x


s.à 2
 x2 + x3 = 0

x1 ≥ 0
avec
   
2 −1 0 −3
A=  −1 2 −1  , b=  1 
0 −1 2 2

(1) Montrer l’existence d’une unique solution pour ce problème.

• L’ensemble S = {x ∈ R3 /x2 + x3 = 0 et x1 ≥ 0 est fermé non borné (même démonstration
que la première question de l’exercice 4).
• S est convexe car (x1 , x2 , x3 ) 7→ x2 + x3 est affine et (x1 , x2 , x3 ) 7→ −x1 est convexe ( car elle
est affine).
2 −1
• A est définie positive car ∆1 = 2 > 0, ∆2 = = 3 > 0 et ∆3 = det A = 4 > 0.
−1 2
Puisque f est une fonction quadratique et A est définie positive donc d’après le cours, f est
continue, coercive et strictement convexe sur le convexe S. Elle admet alors une unique solution
x∗ sur S.
(2) Calculer cette solution.
Les contraintes sont affines donc elles sont qualifiées en tout point. Alors x∗ est un point KKT.
Puisque le problème est convexe alors les conditions nécessaires de KKT sont suffisantes. Ils
existent alors λ∗ ≥ 0 et µ∗ ∈ R tels que (x∗ , λ∗ , µ∗ ) est l’unique solution du système


 ∇f (x) + λ∇g(x) + µ∇h(x) = 0
λg(x) = 0

(KKT )

 h(x) = 0
g(x) ≤ 0


1
où f (x) = xT Ax − bT x, h(x) = x2 + x3 et g(x) = −x1 . f est quadratique donc ∇f (x) = Ax − b.
2
Le système KKT est équivalent à

 2x1 − x2 + 3 − λ = 0
 (1)
−x + 2x − x − 1 + µ = 0 (2)

1 2 3



−x2 + 2x3 − 2 + µ = 0 (3)

(KKT )

 x 2 + x 3 = 0 (4)
−λx1 = 0 (5)




x1 ≥ 0


(5) ⇐⇒ λ = 0 où x = 0.

5
TD3 Zakia ANKHILI

• Si λ = 0. Ona


 2x1 − x2 + 3 = 0 (1)
 −x1 + 3x2 − 1 + µ = 0 (2)


(KKT ) ⇐⇒ −3x2 − 2 + µ = 0 (3)
x2 + x3 = 0 (4)




x1 ≥ 0


−19 −5 5 7
On trouve x1 = , x2 = x3 = et µ = . Or x1 < 0 donc (x, 0, µ) n’est pas une
11 11 11 11
solution du système KKT.
• Si x1 = 0, ona


 −x2 + 3 − λ = 0 (1)
3x2 − 1 + µ = 0 (2)

(KKT ) ⇐⇒

 −3x 2−2+µ=0 (3)
x2 + x3 = 0 (4)


3
(2)+(3) implique µ = .
2
−1 1
(2)-(3) implique x2 = et (4) implique x3 = .
6 6
19 −1 1 19 3
(1) implique λ = > 0. D’où (0, , , , ) est l’unique solution du système KKT. Par
6 6 6 6 2
−1 1
conséquent, x∗ = (0, , )
6 6
N.B. Si vous avez commencé par étudier le cas x1 = 0, déduisez le résultat sans étudier le cas λ = 0
puisque le système KKT admet une unique solution.
Exercice 6. Soit Rn muni de son produit scalaire usuel et de la norme euclidienne ||.|| associée. Etant
donné a ∈ Rn . On considère le problème d’optimisation suivant :

min fa (x)
s.à



(Pa ) 1
kxk2 ≤


 T 4
a x≤0
où
fa (x) = − ln(1 − kxk2 ) + aT x ∀x ∈ Rn tel que kxk < 1
(1) Vérifier que le problème (Pa ) admet une solution unique.
Soient
1
S = {x ∈ Rn / g1 (x) = kxk2 − ≤ 0 et g2 (x) = aT x ≤ 0},
4
ϕ : S → R+
∗ ψ : R +
∗ → R
2 et
x 7→ 1 − kxk x 7→ − ln x
i) Montrons que fa admet au moins un minimum global sur S.
– fa est continue.
– S est borné par construction
– S est fermé. En effet, On a S = g1−1 (] − ∞, 0]) ∩ g2−1 (] − ∞, 0]). puisque g1 et g2 sont
contiues et ] − ∞, 0]) est fermé donc S = gi−1 (] − ∞, 0]), i = 1, 2 est fermé. D’où S
fermé. (intersection de deux fermés)
fa est une fonction continue sur un fermé borné (compact), elle admet alors au moins un
minimum global sur S.
ii) Montrons que fa admet au plus un minimum global sur S.
– L’ensemble S est convexe. En effet, g1 est convexe car Hg1 (x) = 2In est définie positive
pour tout x ∈ Rn . g2 est affine donc convexe. Par conséquent, S est convexe.
– La fonction ϕ est strictement concave car Hϕ (x) = −2In est définie négative pour tout
x ∈ Rn .

6
TD3 Zakia ANKHILI

−1
– La fonction ψ est strictement décroissante et convexe car ψ 0 (x) = < 0 et ψ 00 (x) =
x
1
> 0 ∀x ∈ R+ ∗
x2
D’après l’exercice 6 de la série 1, ψ ◦ ϕ est strictement convexe sur S. On déduit que la
fonction fa est strictement convexe sur S comme somme d’une fonction strictement convexe
et une fonction affine. En effet, soient x1 , x2 ∈ S, x1 6= x2 et λ ∈]0, 1[. Puisque ψ ◦ ϕ est
strictement convexe alors

ψ ◦ ϕ(λx1 + (1 − λ)x2 ) < λψ ◦ ϕ(x1 ) + (1 − λ)ψ ◦ ϕ(x2 )

g2 est affine alors

g2 (λx1 + (1 − λ)x2 ) = λg2 (x1 ) + (1 − λ)g2 (x2 )

Or fa = ψ ◦ ϕ + g2 , donc

fa (λx1 + (1 − λ)x2 ) < λfa (x1 ) + (1 − λ)fa (x2 )

Par conséquent, f admet au plus un minimum global sur S.

i) et ii) impliquent que le problème (Pa ) admet une solution unique.
(2) Résoudre (Pa ) pour a = 0.

min f0 (x) = − ln(1 − kxk2 )

s.à

(P0 ) 1
 kxk2 ≤

4
• La contrainte est qualifiée en tout point. En effet,
n
1 X 2 1
g1 (x) = kxk2 − = xi −
4 4
i=1

donc
 
2x1
 .. 
∇g1 (x) =  .  = 2x
2xn
1 1
Soit x tel que kxk2 = , λ∇g1 (x) = 0 ⇒ λ = 0 (x 6= 0 car kxk2 = ) donc la contrainte est
4 4
qualifiée en tout point.
• La contrainte est qualifiée en tout point, alors d’après la première question, x∗ est l’unique
solution du problème (P0 ) si et seulement si x∗ est un point KKT. i.e. il existe λ∗ ≥ 0 tel
que (x∗ , λ∗ ) est solution du système


 ∇f0 (x) + λ∇g1 (x) = 0
λg1 (x) = 0

(KKT )

 g1 (x) ≤ 0
λ≥0


n
X
f0 (x) = − ln(1 − x2i ), alors
i=1
 2x1 
 1 − kx2 k 
 ..  2
∇f0 (x) = 
 .
=
 1 − kxk2 x
 2xn 
1 − kx2 k

7
TD3 Zakia ANKHILI

2 1
 

2k
x + 2λx = 0  2( + λ)x = 0 (1)
− kx − kxk2
 


 1 

 1
 1  1
λ(kxk2 − ) = 0 λ = 0 où kxk2 =
 
(KKT ) ⇐⇒ ⇐⇒ (2)
4 4
 1  1
kx2 k ≤ kxk2 ≤

 

 

 4 
 4
λ≥0 λ≥0
 

1 4 4
Supposons que kxk2 = , (1) implique 2( + λ)x = 0. Alors 2( + λ) = 0 (x 6= 0 car
4 3 3
2 1 4
kxk = ). Ce qui donne + λ = 0 contradiction avec λ ≥ 0.
4 3
Par conséquent, λ = 0 et alors x = 0 d’après l’égalité (1). D’où x∗ = 0 est l’unique solution
de (P0 ).
On suppose maintenant que a 6= 0.
(3) On désigne par x∗ la solution de (Pa ). Montrer que aT x∗ < 0.
• Montrons que les contraintes sont qualifiées en tout point. i.e. Montrons que ∇gi (x), i ∈ I
sont linéairement indépendants.
Si I = {1} (g1 (x) = 0 et g2 (x) < 0), ∇g1 (x) est linéairement indépendant d’après la première
question.
Si I = {2} (g1 (x) < 0 et g2 (x) = 0), ∇g2 (x) = a 6= 0 donc ∇g2 (x) est linéairement indépen-
dant.
Si I = {1, 2} (g1 (x) = 0 et g2 (x) = 0). Soit α, β ∈ R vérifiant α∇g1 (x) + β∇g2 (x) = 0.
Montrons que α = β = 0. En effet, on a 2αx + βa = 0, alors h2αx + βa, xi = 0. C’est
à dire 2αk(x)k2 + βha, xi = 0. Or aT x = 0 donc 2αk(x)k2 = 0. Par conséquent α = 0
1
(kxk2 = 6= 0). Par suite β = 0 (2αx + βa = 0 et a 6= 0).
4
• Puisque les contraintes sont qualifiées en tout point et le problème est convexe et admet
une unique solution optimale x∗ , alors il existe λ∗1 , λ∗2 ≥ 0 tels que (x∗ , λ∗1 , λ∗2 ) est l’unique
solution du système KKT
 2

2
x + a + 2λ1 x + λ2 a = 0 (1)
 1 − kxk
 
 ∇fa (x) + λ1 ∇g1 (x) + λ2 ∇g2 (x) = 0


  1
λ1 g1 (x) = 0 λ1 (kxk2 − ) = 0
 

 
 (2)


λ2 g2 (x) = 0


T
4
(KKT ) ⇐⇒ λ2 a x = 0 (3)
 g1 (x) ≤ 0  1
2
kxk ≤
 
 g2 (x) ≤ 0

 

 
 4
λ1 , λ 2 ≥ 0 T
 



 a x ≤ 0
λ1 , λ1 ≥ 0
(3) ⇐⇒ λ2 = 0 où aT x = 0.
2
Supposons que aT x = 0, (1) ⇒ h x + a + 2λ1 x + λ2 a, ai = 0.
1 − kxk2
Alors (1 + λ2 )kak2 = 0. Absurde car a 6= 0 et λ2 ≥ 0. Par conséquent, aT x∗ < 0.
1
(4) En distinguant selon que la contrainte kxk2 ≤ est active ou pas en x∗ , montrer que
4
 a p 4
 −

2
( 1 + kak2 − 1) si 0 < kak <
kak 3
x∗ = a 4
 −
 si kak ≥
2kak 3
Puisque aT x < 0 alors λ2 = 0.
 
2
(1) ⇐⇒ + 2λ1 x = −a
1 − kxk2
1 − kxk2 −1
donc x = − 2
a (remarquer que 2 + 2λ1 (1 − kxk2 ) 6= 0 car sinon λ1 =
2 + 2λ1 (1 − kxk ) 1 − kxk2
absurde car λ1 ≥ 0). Alors x = αa avec α ∈ R−.

8
TD3 Zakia ANKHILI

1
• Cas 1 : Si kxk2 < alors λ1 = 0. En remplaçant x par αa dans (1) on trouve
4
2α
a+a=0
1 − α2 kak2
i.e.
−kak2 α2 + 2α + 1 = 0
∆0 = 1 + kak2 > 0 donc l’équation admet deux solutions réelles
p p
−1 + 1 + kak2 −1 − 1 + kak2
α1 = − , α2 = −
kak2 kak2
p
1 − 1 + kak2 1
or α < 0 donc α = α1 . Par conséquent, x = a. Or kxk < donc
kak2 2
p
1 + kak2 − 1 1
< (kxk = −α1 kak car α1 < 0)
kak 2
donc
p kak
1 + kak2 < +1
2
Alors
kak2
1 + kak2 < + kak + 1
4
4
Ce qui implique que kak < .
3
1 1
2
• Cas 2 : Si kxk = , on a x = αa donc kxk2 = α2kak2 ce qui donne α2 = .
4 4kak2
−1 −1
Or α < 0 donc α = . Par conséquent, x = a Calculons maintenant λ1 . En
2kak 2kak
1
remplaçant dans l’équation (1), kxk2 par , on trouve
4
8
αa + a + 2λ1 αa = 0
3
puisque a 6= 0 donc
8
α + 1 + 2λ1 α = 0
3
3kak − 4 4
Par conséquent, λ1 = . Or λ1 ≥ 0 donc kak ≥
3 3
Exercice 7. On considère le problème (P ) suivant :
1 2
(
2
min x 1 + x + x1 x2 + x1
(P ) s.à 3 2
x1 + x2 − 1 ≤ 0
(1) Vérifier que pour tout µ ∈ R, la fonction x 7→ L(x, µ) est strictement convexe sur R2
où L est la fonction de Lagrange associé à (P )
1
Soit la fonction x 7→ L(x, µ) = x21 + x22 + x1 x2 + x1 + µ(x1 + x2 − 1). On a
3
! !
2x1 + x2 + µ + 1 2 1
∇x L(x, µ) 2 Hx L(x, µ) = 2
x1 + x2 + µ 1
3 3
4
Le hessien de x 7→ L(x, µ) est défini positif pour tout x ∈ R2 (∆1 = 2 > 0, ∆2 = − 1 > 0)
3
donc x 7→ L(x, µ) est strictement convexe sur R2 .

9
TD3 Zakia ANKHILI

(2) Déterminer explicitement le problème duale (D) de (P ). Le problème duale est défini par
(
max θ(µ) = inf L(x, µ)
(D) s.à x∈R2
µ≥0

2x1 + x2 = −µ − 1
(
Calculons θ. On a ∇x L(x, µ) = 0 ⇔ 2
x1 + x2 = −µ
3

⇔ x1 = µ − 2 et x2 = 3(1 − µ)

La fonction x 7→ L(x, µ) est strictement convexe sur R2 donc le point x∗ = (µ − 2, 3(1 − µ)) est
son minimum global sur R2 . Par conséquent, θ(µ) = L(x∗ , µ)

9
θ(µ) = (µ − 2)2 + (1 − µ)2 + 3(µ − 2)(1 − µ) + µ − 2 + µ(µ − 2 + 3 − 3µ − 1) = −µ2 − 1
3

(3) Résoudre le problème (D).

La résolution du problème (D) revient à trouver le maximum de la fonction réelle θ sur R+ .
Remarquons que la fonction réelle θ est décroissante sur R+ (θ0 (µ) = −2µ ≤ 0 pour tout µ ∈ R+ ).
Par conséquent, µ∗ = 0 est le maximum global de θ sur R+ .
(4) Utiliser les résultats précédents pour résoudre (P ).
1
• La fonction f définie par f (x) = x21 + x22 +x1 x2 +x1 est strictement convexe sur R2 .(Hf (x) =
3
Hx L(x, µ) qui est défini positif pour tout x)
• La fonction g définie par g(x) = x1 + x2 − 1 est affine donc convexe.
• il existe x̄ = (4, 0) tel que g(x̄) < 0
Alors, d’après le théorème de la dualité forte θ(µ∗ ) = f (x∗ ) où x∗ est la solution du problème
(P ). D’après la caractérisation du point selle (x∗ , µ∗) est un point selle. D’où x∗ est le minimum
globale de la fonction x 7→ L(x, µ∗ ). D’après la question 2), x∗1 = µ∗ − 2 et x∗2 = 3(1 − µ∗ ). i.e.
x∗ = (−2, 3) est la solution du problème (P) et on a f (x∗ ) = −1.

Exercice 8. Soient A une matrice de Rn × Rn symétrique définie positive, a, b ∈ Rn avec a 6= 0 et c ∈ R.

On considère le problème
1 T

 min x Ax − bT x
(P ) s.à 2
 aT x − c ≤ 0

Soit L la fonction de Lagrange associé à (P ) :

(1) Vérifier que la fonction x 7→ L(x, u) est strictement convexe sur Rn .
On a
1
L(x, µ) = xT Ax − bT x + µ(aT x − c)
2
donc
1
L(x, µ) = xT Ax + (−b + µa)T x − µc
2
x 7→ L(x, µ) est donc une fonction quadratique avec sa matrice hessienne est A qui est symétrique
définie positive. Alors elle est strictement convexe sur Rn
(2) Déterminer la fonction duale.
Soit µ ∈ R, on a θ(µ) = infn L(x, µ). Puisque x 7→ L(x, µ) est quadratique et A est symétrique
x∈R
définie positive, alors elle admet un unique minimum global x∗ sur Rn qui est solution du système

10
TD3 Zakia ANKHILI

linéaire Ax = b − µa. Or A est inversible (définie positive) donc x∗ = A−1 (b − µa).

θ(µ) = L(x∗ , µ)
1 −1
T
A (b − µa) A A−1 (b − µa) + (−b + µa)T A−1 (b − µa) − µc


=
2
1
= (b − µa)T A−1 (b − µa) − (b − µa)T A−1 (b − µa) − µc
2
1
= − (b − µa)T A−1 (b − µa) − µc
2
1 T −1
b A b − µaT A−1 b − µbT A−1 a + µ2 aT A−1 a − µc


= −
2
1 1
= − µ2 aT A−1 a + µ(aT A−1 b − c) − bT A−1 b
2 2
(3) Résoudre le problème duale (D) de (P ).

Le problème dual est défini par


max θ(µ)
(D) s.à
µ≥0
La résolution du problème duale revient à trouver les maxima globaux de la fonction réelle θ sur
R+ .

• Sur ]0, +∞[. On a θ0 (µ) = −µaT A−1 a + aT A−1 b − c et θ00 (µ) = −aT A−1 a. Or A est définie
positive et a 6= 0 donc aT A−1 a > 0 donc θ est strictement concave sur R (θ00 (µ) < 0 pour
aT A−1 b − c T −1
tout µ ∈ R). D’autre part, θ0 (µ) = 0 ⇔ µ = (a A a 6= 0). On doit étudier le
aT A−1 a
signe de µ.
aT A−1 b − c
– Si aT A−1 b − c > 0, alors µ∗ = ∈]0, +∞[ est un point critique de θ. Puisque
a∗T A−1 a
θ est strictement concave alors µ est le maximum global de θ.
– Si aT A−1 b − c ≤ 0, alors θ n’admet pas de point critique sur ]0, +∞[.
• Au point 0. On a θd0 (0) = aT A−1 b − c. D’après le théorème du cours concernant l’étude
des bornes d’intervalle [a, b] : Si 0 est un maximum local de θ alors θd0 (0) ≤ 0. Puisque θ
est concave alors 0 est un maximum global de θ si et seulement si θd0 (0) ≤ 0. (La condition
nécessaire est suffisante dans le cas concave)
– Si θd0 (0) = aT A−1 b − c ≤ 0 alors 0 est un maximum global de θ.
– Si θd0 (0) = aT A−1 b − c > 0 alors 0 est un minimum local de θ.
Conclusion: 
 aT A−1 b − c
∗
µ = T A−1 a
si aT A−1 b − c ≥ 0
a
 0 si aT A−1 b − c < 0
(4) Montrer que les problèmes (P ) et (D) ont la même valeur optimale.
1
• La fonction f définie par f (x) = xT Ax − bT x est strictement convexe sur Rn .(Hf (x) = A
2
qui est symétrique défini positif pour tout x)
• La fonction g définie par g(x) = aT x − c est affine donc convexe.
• il existe x̄ = tel que g(x̄) < 0
D’après le théorème de la dualité forte les problèmes (P ) et (D) ont la même valeur optimale.
Exercice 9. Soit a ∈ R+
∗ . On considère le problème d’optimisation suivant :
n

 X
 min f (x) = xi
(P ) s.à
2 i=1
 kxk ≤ a


11
TD3 Zakia ANKHILI

(1) Vérifier que pour tout µ > 0, la fonction x 7→ L(x, µ) est strictement convexe sur Rn
où L est la fonction de Lagrange associé à (P )
n
X
L(x, µ) = xi + µ(kxk2 − a)
i=1
On a  
1 + 2µx1
∇x L(x, µ) 
 .. 
et Hx L(x, µ) = 2µIn
. 
1 + 2µxn
Si µ > 0, Hx L(x, µ) est définie positive pour tout x ∈ Rn (ses valeurs propres égalent à 2µ > 0).
D’où le résultat.
(2) Montrer que la fonction duale est définie par :
( n
− − aµ si µ > 0
θ(µ) = 4µ
−∞ si µ ≤ 0
La fonction θ est définie par
θ(µ) = infn L(x, µ)
x∈R
∇x L(x, µ) = 0 ⇐⇒ 1 + 2µxi = 0 pour tout i = 1, ...n
−1
⇐⇒ xi = pour tout i = 1, ...n avec µ 6= 0
2µ
−1
 
 2µ 
• Si µ > 0, x → n

7 L(x, µ) est strictement convexe sur R donc le point x =  ∗ .. 
 est son
 . 
 −1 
2µ
unique minimum global sur Rn et don ce cas on a,
θ(µ) = L(x∗ , µ)
n
X −1 n
= + µ( 2 − a)
2µ 4µ
i=1
n
=− − aµ
4µ
• Si µ < 0 x 7→ L(x, µ) est concave sur Rn donc le point x∗ est est son unique maximum global
sur Rn et on a pour tout µ ≤ 0, lim L(x, µ) = −∞. D’où θ(µ) = −∞ si µ ≤ 0.
x→−∞
(3) Trouver la solution optimale et la valeur optimale du problème dual (D) de (P ). Le
problème dual est défini par 
max θ(µ)
(D) s.à
µ≥0
La résolution du problème duale revient à trouver les maxima globaux de la fonction réelle θ sur
R∗+ . √
0 n 0 an −n
On a θ (µ) = − a. Donc θ (µ) = 0 si et seulement si µ = . On a θ00 (µ) = < 0 pour
4µ2 2a √ 2µ 3
an
tout µ > 0 donc la fonction θ est concave sur R∗+ . Par conséquent, µ∗ = est le maximum
√ 2a
global de θ sur R∗+ et on a θ(µ∗ ) = − an.
  √
−1
 
− an
 2µ∗   n 
∗
 .   . 
(4) En déduire la solution optimale du problème (P ). Posons x =  ..  = 
   .. .
 −1   − an  √ 

2µ∗ √ n
On a kx k = a ≤ a donc x est un point réalisable de (P ). De plus f (x∗ ) = − an = θ(µ∗ ). Par
∗ 2 ∗

conséquent, x∗ est la solution du problème optimale de (P ).

12