Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

mardi 9 mai 2017 Licence de Mathématiques EXAMEN DE MATHÉMATIQUES LM239 - Optim

mardi 9 mai 2017 Licence de Mathématiques EXAMEN DE MATHÉMATIQUES LM239 - Optimisation linéaire et convexité (Y. PRIVAT) - Durée : 2 heures Consignes : les exercices sont tous indépendants et peuvent être traités dans n’importe quel ordre. Ils sont de difﬁculté croissante. Les documents, calculatrices et téléphones portables ne sont pas autorisés. ll est impor- tant d’apporter une grande attention au soin et à la presentation, justiﬁcation et rédaction des réponses. Il faut donc utiliser des phrases de liaison, des afﬁrmations et des conclusions. EXERCICE N°1 (vrai/faux - 4 points) Si les afﬁrmations suivantes sont vraies, les justiﬁer. Si elles sont fausses, fournir un contre-exemple. (A) Soit f : R2 →R, une fonction continue et coercive. Soit (x∗, y∗), un point tel que ∇f (x∗, y∗) = 0. Alors, (x∗, y∗) est un minimum local de f . (B) On considère la fonction J : Rn →R déﬁnie par J(x) = 1 2〈Ax,x〉−〈b,x〉avec A ∈Sn(R) et b ∈Rn. On suppose de plus que λ1(A) < 0, où λ1(A) est la plus petite valeur propre de A. Alors, le problème supx∈Rn J(x) a une solution. (C) Si un programme linéaire admet une solution de base réalisable, alors il possède nécessaire- ment une solution. (D) La solution d’un problème de moindres carrés s’écrivant infx∈Rn ∥Ax −b∥2 avec A ∈Mm,n(R), m > n et b ∈Rm peut ne pas être unique. EXERCICE N°2 (Optimisation linéaire - 10 points) On considère le programme linéaire max 6x1 +4x2 s.c.                  4x1 +5x2 ≤15 1 2x1 + x2 ≥1 4x1 + x2 ≤12 2x1 + x2 ≥2 x1,x2 ≥0. (P) 1. Mettre le programme linéaire sous forme canonique, puis sous forme standard. 2. Écrire le problème dual (D) du programme linéaire (P). 3. Résoudre graphiquement le programme linéaire (P). Soient xi, i = 3,4,5,6, les variables d’écart associées aux quatre premières contraintes du système d’inégalités ci-dessus. 4. Montrer que la solution de base ¯ x = ( ¯ x1,..., ¯ x6) déﬁnie par ¯ x1 = 2 et ¯ x2 = 0 est une solution de base réalisable. On précisera la base associée. Est-ce une solution de base optimale ? 5. Appliquer l’algorithme primal du simplexe en utilisant la forme tableau à partir de la base de la question précédente. 1 6. On cherche à appliquer l’algorithme primal du simplexe pour résoudre le programme linéaire (P) en utilisant un programme linéaire auxiliaire. Former ce problème auxiliaire et donner une première solution de base réalisable. Remarque : on ne demande pas de résoudre le problème auxiliaire. EXERCICE N°3 (Optimisation non-linéaire - 10 points) Soit n, un entier supérieur ou égal à 3. Dans tout l’exercice, on notera 〈·,·〉le produit scalaire euclidien de Rn. On considère un portefeuille d’actions composé de n actions à risque (a1,...,an). On note xi, la proportion de l’action ai dans le portefeuille. Le vecteur x = (x1,...,xn)⊤représente donc la composition du portefeuille. On introduit le vecteur u = (1,...,1)⊤∈Rn de sorte que x vériﬁe alors n X i=1 xi = 1 = 〈u,x〉Rn, et xi ≥0, i = 1,...,n. Le rendement de l’action ai est modélisé par une variable aléatoire Ri de moyenne ei = E(Ri). On introduit le vecteur de rendement moyen e = (e1,...,en)⊤dont les coordonnées sont telles que 0 < e1 < e2 < ... < en, puis la matrice de covariance A = (Ai,j)1≤i,j≤n déﬁnie par la relation Ai,j = E £ (Ri −E(Ri)) ¡ R j −E(R j) ¢¤ , (i, j) ∈{1,...,n}2. On admet que A est symétrique et semi-déﬁnie positive 1. On suppose de plus qu’ici, A est déﬁnie po- sitive. Le rendement du portefeuille est donné par ε(x) = 〈e,x〉Rn, tandis que le risque du portefeuille est donné par σ(x) = 1 2〈Ax,x〉. On dit qu’un portefeuille x est efﬁcient s’il assure un risque minimal σ(x) pour un rendement imposé ε. On déﬁnit alors l’ensemble C1(ε) = © x ∈Rn | 〈u,x〉= 1 et 〈e,x〉= ε ª , et, oubliant provisoirement la positivité des proportions xi, on cherche à résoudre le problème inf x∈C1(ε)σ(x) (P ) 1. Démontrer que l’ensemble C1(ε) est non vide. 2. Montrer que le problème (P ) possède une unique solution que l’on notera x∗. Soit x0, un élément quelconque de l’ensemble C1(ε). 3. On déﬁnit h∗= x∗−x0. Montrer que h∗résout un problème d’optimisation s’écrivant inf h∈H J(h), avec H = © h ∈Rn | 〈u,h〉= 0 et 〈e,h〉= 0 ª , dont on précisera la fonction coût J. 4. Calculer le gradient de J, ainsi que sa hessienne en tout point h ∈H . 5. En écrivant les conditions d’optimalité de ce problème, démontrer que ∇J(h∗) appartient à l’orthogonal 2 de l’espace vectoriel H . 6. En déduire qu’il existe deux réels λ et µ tels que ∇J(h∗) = λu +µe. 7. Montrer que le couple (λ,µ) est solution du système linéaire ½ 〈A−1u,u〉λ+〈A−1e,u〉µ = 1 〈A−1u,e〉λ+〈A−1e,e〉µ = ε. Ce système possède-t-il une unique solution ? Indication : pour cette dernière question, on pourra admettre que, puisque A ∈S ++ n (R), la fonction (Rn)2 ∋(x, y) 7→〈A−1x,x〉déﬁnit un produit scalaire sur Rn. 8. En déduire l’expression de h∗, puis commenter la démarche utilisée pour résoudre le problème initial. 1. cf. cours de Probabilités. 2. On rappelle que l’orthogonal d’un sous-espace vectoriel E de Rn est l’ensemble des vecteurs y ∈Rn tels que 〈y,z〉= 0 pour tout z ∈E. 2 uploads/s3/ lm339-exam-2017.pdf