Scribd Logo
Importer

Bienvenue sur Scribd !

  • 67 vues

    M1 Optim Exam2 2020 2

    Transféré par

    jamal kamal
    Cet examen contient trois exercices portant sur l'optimisation sous contraintes. Le premier exercice demande de déterminer la distance d'un point à une droite en utilisant les multiplicateurs de Lagrange. Le deuxième exercice traite du théorème de Kuhn-Tucker et de l'algorithme d'Uzawa pour résoudre un problème d'optimisation sur un ensemble défini par des contraintes. Le troisième exercice présente la méthode LASSO pour la régression linéaire pénalisée.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd

    M1 Optim Exam2 2020 2

    Transféré par

    jamal kamal
    67 vues2 pages
    Cet examen contient trois exercices portant sur l'optimisation sous contraintes. Le premier exercice demande de déterminer la distance d'un point à une droite en utilisant les multiplicateurs de Lagrange. Le deuxième exercice traite du théorème de Kuhn-Tucker et de l'algorithme d'Uzawa pour résoudre un problème d'optimisation sur un ensemble défini par des contraintes. Le troisième exercice présente la méthode LASSO pour la régression linéaire pénalisée.

    Titre original

    M1_Optim_exam2_2020_2

    Copyright

    © © All Rights Reserved

    Formats disponibles

    PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Cet examen contient trois exercices portant sur l'optimisation sous contraintes. Le premier exercice demande de déterminer la distance d'un point à une droite en utilisant les multiplicateurs de Lagrange. Le deuxième exercice traite du théorème de Kuhn-Tucker et de l'algorithme d'Uzawa pour résoudre un problème d'optimisation sur un ensemble défini par des contraintes. Le troisième exercice présente la méthode LASSO pour la régression linéaire pénalisée.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    67 vues2 pages

    M1 Optim Exam2 2020 2

    Transféré par

    jamal kamal
    Cet examen contient trois exercices portant sur l'optimisation sous contraintes. Le premier exercice demande de déterminer la distance d'un point à une droite en utilisant les multiplicateurs de Lagrange. Le deuxième exercice traite du théorème de Kuhn-Tucker et de l'algorithme d'Uzawa pour résoudre un problème d'optimisation sur un ensemble défini par des contraintes. Le troisième exercice présente la méthode LASSO pour la régression linéaire pénalisée.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    Vous êtes sur la page 1sur 2

    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, justification et rédaction des réponses. Il faut donc utiliser des phrases de liaison, des
    affirmations 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) 6= (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 justifier 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éfini 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 f (| x − α|, |y − β|),
    ( x,y)∈C

    à l’aide d’une méthode de type Uzawa, à quel type de difficulté 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éfinie par

    f ( x, y) = | x − 2| + |y − 2|,

    Dessiner C puis résoudre le problème

    inf f ( x, y).
    ( x,y)∈C

    Indication : simplifier l’écriture de f ( x, y). On se posera notamment les questions de l’existence de solu-
    tions, qualification des contraintes, etc.

    1
    EXERCICE No 3 (la méthode LASSO - 7 points)
    Dans tout l’énoncé, h·, ·iRn désignera le produit scalaire euclidien de Rn et k · kk la norme définie par

    d
    k x kkk = ∑ | x j |k .
    j =1

    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

    1 λ d w2j λ d
    inf
    (w,η )∈Rd ×(R∗+ )d
    J (w, η ) où J (w, η ) =
    2n
    ky − Mwk22 +
    2 ∑ ηj
    +
    2 ∑ ηj
    j =1 j =1

    1. Montrer que J est de classe C ∞ sur Rd × (R∗+ )d puis calculer ∇ J (w, η ).


    2. Soit x ∈ R. Démontrer l’identité
    x2 η
    | x | = inf +
    η >0 2η 2
    et en déduire que

    1
    inf J (w, η ) = inf ky − Mwk22 + λkwk1 .
    (w,η )∈Rd ×(R∗+ )d w ∈Rd 2n

    3. Démontrer que le problème


    1
    inf ky − Mwk22 + λkwk1
    w ∈Rd 2n
    possède une solution w∗ . À quelle condition (suffisante) 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

    1
    inf ky − Mwk22 + λkwk1 .
    w ∈Rd 2n

    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

    Vous aimerez peut-être aussi