Remerciez-le!

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

mercredi 3 juin 2020 Examen no 2 - Optimisation Master 1 - Math. Fondamentales,

mercredi 3 juin 2020 Examen no 2 - Optimisation Master 1 - Math. Fondamentales, CSMI - Durée : 2 heures Consignes : les documents et calculatrices sont autorisés. ll est important d’apporter une grande attention au soin et à la présentation, justiﬁcation et rédaction des réponses. Il faut donc utiliser des phrases de liaison, des afﬁrmations et des conclusions. EXERCICE No 1 (multiplicateurs de Lagrange - 5 points) On se place dans R2 muni d’une base orthonormée. Soit la droite D d’équation D = {(x, y) ∈R2 | ax + by + c = 0} avec (a, b) ̸= (0, 0). On demande de déterminer la distance du point de coordonnées (x0, y0) ∈R2 à D en utilisant le théorème des extrema liés. On étudiera au préalable l’existence de solutions pour ce problème et on prendra soin de justiﬁer chaque étape du raisonnement. EXERCICE No 2 (théorème de Kuhn-Tucker & algorithme d’Uzawa - 8 points) On considère le sous-ensemble de R2 déﬁni par C = {(x, y) ∈R2 | x2 + y2 = 1 et x −y2 ≥0}. 1. Soit f : R2 →R, une fonction continue, (α, β) ∈R2. Si l’on souhaite résoudre numériquement le problème inf (x,y)∈C f (|x −α|, |y −β|), à l’aide d’une méthode de type Uzawa, à quel type de difﬁculté est-on confronté? Proposer un algorithme permettant de palier ce problème. Indication : on pourra admettre qu’il existe des algorithmes permettant de minimiser une fonction de Rn dans R (sans contrainte donc) sans avoir à calculer de dérivée. Ces méthodes reposent juste sur l’évaluation de la fonction. On peut citer par exemple la méthode du recuit simulé ou encore la méthode du simplexe de Nelder-Mead. 2. On considère la fonction f : R2 →R déﬁnie par f (x, y) = |x −2| + |y −2|, Dessiner C puis résoudre le problème inf (x,y)∈C f (x, y). Indication : simpliﬁer l’écriture de f (x, y). On se posera notamment les questions de l’existence de solu- tions, qualiﬁcation des contraintes, etc. 1 EXERCICE No 3 (la méthode LASSO - 7 points) Dans tout l’énoncé, ⟨·, ·⟩Rn désignera le produit scalaire euclidien de Rn et ∥· ∥k la norme déﬁnie par ∥x∥k k = d ∑ j=1 |xj|k. On propose dans cet exercice d’étudier une méthode de régression linéaire pénalisée à l’aide d’une contrainte de parcimonie : la méthode LASSO 1. Soient λ > 0, (n, d) ∈(N∗)2, M ∈Mn,d(R) et y ∈Rn. On considère le problème inf (w,η)∈Rd×(R∗ +)d J(w, η) où J(w, η) = 1 2n∥y −Mw∥2 2 + λ 2 d ∑ j=1 w2 j ηj + λ 2 d ∑ j=1 ηj 1. Montrer que J est de classe C ∞sur Rd × (R∗ +)d puis calculer ∇J(w, η). 2. Soit x ∈R. Démontrer l’identité |x| = inf η>0 x2 2η + η 2 et en déduire que inf (w,η)∈Rd×(R∗ +)d J(w, η) = inf w∈Rd 1 2n∥y −Mw∥2 2 + λ∥w∥1. 3. Démontrer que le problème inf w∈Rd 1 2n∥y −Mw∥2 2 + λ∥w∥1 possède une solution w∗. À quelle condition (sufﬁsante) sur w∗la fonction J possède-t-elle un minimiseur (w∗, η∗) sur Rd × (R∗ +)d ? 4. Proposer un algorithme de minimisation permettant de résoudre le problème inf w∈Rd 1 2n∥y −Mw∥2 2 + λ∥w∥1. On détaillera très précisément chaque étape de l’algorithme et on ne demande pas d’en dé- montrer la convergence. 1. Least Absolute Shrinkage and Selection Operator 2 uploads/Philosophie/ m1-optim-exam2-2020-2.pdf