´ Paris 1 Universite
Optimisation, M. Gourdel
Examen (3 heures)
Exercice 1 On consid`ere le probl`eme d’optimisation suivant : max 3x1 x2 − x32 s.c. x1 ≥ 0 x2 ≥ 0 (P) x1 − 2x2 = 5 2x1 + 5x2 ≥ 20 1. Montrer que le probl`eme poss`ede une solution. 2. R´esoudre le probl`eme.
Exercice 2 Soit A ∈ Mn (IR) une matrice sym´etrique d´efinie positive, on souhaite montrer la propri´et´e : hA−1 v, vihAu, ui ≥ (hu, vi)2 min hAu, ui s.c. u ∈ IRn Soit v un vecteur non nul, on consid`ere le probl`eme (Pv ) hv, ui = 1 pour tout u, v de IRn ,
(1)
1. Montrer que si pour tout v non nul, val(Pv ) = (hA−1 v, vi)−1 , alors la propri´et´e (1) est satisfaite. 2. Le vecteur v ´etant fix´e, on consid`ere u une solution de (Pv ). a) Montrer l’existence d’un multiplicateur et ´ecrire le syst`eme des conditions de KKT. b) R´esoudre le syst`eme. c) En d´eduire l’existence d’une solution, et calculer la valeur de (Pv ). 3. Conclure quand ` a la propri´et´e (1). 4. Soit A et B deux matrices sym´etriques d´efinies positive. a) montrer que A + B est une matrice sym´etrique d´efinie positive. b) En d´eduire que l’ensemble X des matrices sym´etriques d´efinies positive est un ensemble convexe. 5. On fixe d´ esormais un vecteur v. On d´efinit ϕ de X dans IR, par ϕ(A) = (hA−1 v, vi)−1 . a) Montrer que ϕ est positivement homog`ene de degr´e 1, et que ϕ(A + B) ≥ ϕ(A) + ϕ(B). b) En d´eduire que ϕ est concave sur X. 1
Exercice 3 On consid`ere dans
IR2 ,
l’ensemble A =
(x, y) ∈
IR2
y ≥ x(x + 1) y ≥ −x(−x + 1)
1. Dessiner A. 2. Montrer que l’on peut interpr´eter A comme l’´epigraphe d’une fonction convexe. 3. On rappelle que puisque 0 ∈ A, le cˆ one tangent `a A en 0 est d´efini par TA (0) = {λa | a ∈ A, λ ≥ 0} D´eterminer graphiquement TA (0) puis analytiquement.
Exercice 4
On d´efinit la fonction ϕ : IR → IR, par la formule ϕ(t) = 1.
(t − 5)2 si t ≥ 5; 0 si t ≤ 5.
a) Montrer que ϕ est de classe C 1 sur IR. b) Montrer que ϕ est convexe sur sur IR. c) La fonction ϕ est-elle de classe C 2 sur IR ?
2. Soit f une fonction strictement convexe de IR2 dans IR. On d´efinit le probl`eme d’optimisation suivant : min f (x, y) s.c. ϕ(3x2 + 2y 2 ) ≤ 0, (P) x ∈ IR, y ∈ IR. a) Montrer que ce probl`eme est un probl`eme convexe qui ne v´erifie pas la condition de Slater. b) Montrer que les points (1, 0), (−1, 0), (0, 1) sont r´ealisables, en d´eduire que le domaine de (P) est d’int´erieur non vide. 3. On d´efinit pour n > 0, un probl`eme approch´e de la fa¸con suivante : min f (x, y) s.c. ϕ(3x2 + 2y 2 ) ≤ 1/n, (Pn ) x ∈ IR, y ∈ IR. a) Montrer pour tout n > 0, ce probl`eme est un probl`eme convexe qui v´erifie la condition de Slater. b) Montrer que val(P) ≥ val(Pn ) 4. On suppose que pour tout n > 0, il existe une solution (xn , y n ) de (Pn ), et que cette suite poss`ede une valeur d’adh´erence x. a) Montrer que (x, y) est un point r´ealisable de (P). b) Montrer que (x, y) est un point optimal de (P).
2