WikiPrépaLivrets

Téléchargements

Présentation du sujet

Difficulté moyenne
Optimisation convexe : caractérisation de la convexité, méthode de pénalisation et théorème de Karush-Kuhn-Tucker
Afficher ou masquer la section

Ce problème de mathématiques étudie la minimisation d'une fonction convexe sur un sous-ensemble convexe fermé de Rn. Il aborde successivement des caractérisations de la convexité, une méthode de pénalisation pour approcher un minimum sous contraintes, la démonstration du théorème de Karush-Kuhn-Tucker à partir du lemme de Farkas, puis l'algorithme d'Uzawa pour le problème dual.

  1. 1Partie I : préliminaires sur les fonctions convexesCaractérisations d'une fonction convexe, convexité forte, cône admissible et conditions nécessaires et suffisantes d'optimalité.
  2. 2Partie II : méthode de pénalisationConstruction d'une suite de fonctions pénalisées pour approcher le minimum d'une fonction sous contraintes convexes.
  3. 3Partie III : théorème de Karush-Kuhn-TuckerDémonstration du lemme de Farkas puis du théorème de Karush-Kuhn-Tucker, condition nécessaire d'optimalité sous contraintes.
  4. 4Partie IV : problème dual et algorithme d'UzawaÉtude du problème dual associé et de la méthode d'Uzawa pour approcher un minimiseur sous contraintes affines.

Difficulté moyenne. Le jury qualifie le problème de relativement long mais d'une difficulté abordable, avec des questions plus ardues dans les deux dernières parties ; la moyenne n'est que de 9,03/20 et aucune copie n'a résolu l'ensemble du sujet.

L'épreuve en chiffres

Moyenne 9,03 / 20 · écart-type 3,81 · où vous situez-vous ?
Afficher ou masquer la section
Moyenne
9,03/ 20
Écart-type
3,81
Durée
4 h
moyenne 9,0305101520
Deux tiers des copies environ (moyenne ± écart-type)

Votre note sur 20 à ce sujet, en conditions de concours.

Source : document officiel du concours, épreuve du 24 avril 2020. Notes publiées par le concours (après harmonisation le cas échéant). Courbe : estimation par une loi normale.

Ce qu'a observé le jury

6 erreurs relevées
Confusion sur une implication élémentaire · Existence et unicité du minimum mal traitées · Hypothèse de différentiabilité oubliée
Afficher ou masquer la section

Le sujet portait sur l'analyse convexe et l'optimisation sous contraintes, en quatre parties de difficulté croissante. Le jury regrette un manque de rigueur sur des raisonnements élémentaires et une maîtrise insuffisante de la topologie. Les deux premières parties ont été largement traitées, mais les parties III et IV, plus techniques, ont été abordées par peu de candidats.

Les erreurs les plus sanctionnées

  1. 1
    Confusion sur une implication élémentaireI-1.d)

    Dans la question I-1.d), certains candidats ont cru à tort à une équivalence entre deux inégalités.

    « Le jury a été étonné de constater que certains candidats semblent penser que »
  2. 2
    Existence et unicité du minimum mal traitéesI-5

    La question I-5 a posé des difficultés, notamment la preuve de la coercivité, et certains candidats ont appliqué le théorème du gradient nul sans vérifier que le domaine était ouvert.

    « La question I-5 a été en général mal traitée par les candidats, que ce soit pour la partie existence »
  3. 3
    Hypothèse de différentiabilité oubliéeII-3

    Pour la question II-3, la majorité des candidats n'a pas vu qu'il fallait établir la différentiabilité de fk avant d'appliquer le résultat de la question I-5.

  4. 4
    Convergence admise sans démonstrationII-5.a)

    Dans la question II-5.a), beaucoup de candidats ont admis la convergence d'une suite extraite sans la démontrer, ce qui a été sévèrement sanctionné.

    « ce qui a été sévèrement sanctionné »
  5. 5
    Piège sur l'exclusion mutuelle de deux assertionsIII-3

    La question III-3, pourtant simple, a vu de nombreux candidats se contenter de récapituler un résultat déjà obtenu sans montrer que les deux assertions s'excluaient mutuellement.

    « assez simple, a pourtant tendu un piège à de nombreux candidats »
  6. 6
    Partie IV quasiment non traitéePartie IV

    La dernière partie, sur le problème dual et l'algorithme d'Uzawa, n'a été abordée que par une petite fraction des candidats.

    « n'a été abordée que par 8% des candidats »

Ce qui a été bien réussi

  • La question I-1.a) a été en général bien traitée.
  • Les questions I-2 et I-3 ont été en général correctement traitées, sauf dans les copies les plus faibles.
  • Les questions II-1, II-2 et II-4 n'ont pas posé de difficulté particulière.
  • La question III-1.a) a été correctement traitée par un très grand nombre de candidats.
  • La question III-2.b) a été beaucoup mieux réussie, en particulier sa première partie.

Conseils du jury

  • Soigner la rigueur et la précision des justifications, y compris sur les questions les plus élémentaires.
  • Éviter les abréviations et mettre clairement en évidence les résultats obtenus.
  • Ne pas se cantonner aux questions les plus simples pour espérer une bonne note.
  • Vérifier les hypothèses d'un théorème avant de l'appliquer, par exemple le caractère ouvert du domaine pour l'annulation du gradient.
  • Ne pas admettre une convergence sans la démontrer explicitement.

Synthèse rédigée par WikiPrépa à partir du rapport officiel du jury (à télécharger en PDF). Les citations sont extraites du rapport.

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

L'énoncé complet, avec les formules et les figures, sans ouvrir le PDF.
Afficher ou masquer la section

ECOLES NORMALES SUPERIEURES

CONCOURS D'ADMISSION 2020

VENDREDI 24 AVRIL 2020-8h00-12h00 FILIERE MP - Epreuve n^∘9 MATHEMATIQUES C

(ULCR)

Durée : 4 heures

Le sujet comprend 6 pages numérotées de 1 à 6 .

L'objet de ce problème est la minimisation sur un sous-domaine K ⊂ ℝ^n d'une fonction f définie sur ℝ^n. Nous proposons plusieurs approches pour trouver des conditions nécessaires d'optimalité, et obtenir des approximations des minimiseurs de f dans des cas particuliers.
Les dépendances entre les parties du problème sont données par le schéma suivant :
I↗, II; ↘, III, →, IV

Notations et définitions

Pour tout entier k ∈ ℕ^⋆, on désignera le produit scalaire usuel sur ℝ^k par ⟨ ⋅, ⋅ ⟩, et la norme euclidienne sur ℝ^k par ‖ ⋅ ‖.
Dans tout le sujet, on se place sur ℝ^n, où n ∈ ℕ^⋆.
  • On dit qu'une fonction f : ℝ^n → ℝ est convexe si pour tous x, y ∈ ℝ^n et tout λ ∈ [0, 1],
f((1 − λ)x + λy) ⩽ (1 − λ)f(x) + λf(y)
  • On dit qu'une fonction f : ℝ^n → ℝ est coercive si lim_(‖x‖ → + ∞)f(x) = + ∞, autrement dit :
∀M > 0, ∃R > 0, ∀x ∈ ℝ^n, ‖x‖ > R ⇒ f(x) > M

I - Préliminaires

Fonctions convexes

I.1. On considère une fonction f : ℝ^n → ℝ.
a. Pour tous x, y ∈ ℝ^n, soit φ_(x, y) : ℝ → ℝ la fonction définie par φ_(x, y)(t) = f(x + t(y − x)) pour tout t ∈ ℝ. Montrer que f est convexe si et seulement si pour tous x, y ∈ ℝ^n, φ_(x, y) est convexe.
b. On suppose que f est différentiable sur ℝ^n. Montrer que pour tous x, y ∈ ℝ^n, la fonction φ_(x, y) est dérivable, et montrer que pour tout t ∈ ℝ, φ_(x, y)^′(t) = ⟨∇f(x + t(y − x)), y − x⟩.
c. En déduire que si f est différentiable sur ℝ^n, alors f est convexe si et seulement si pour tous x, y ∈ ℝ^n,
f(y) ⩾ f(x) + ⟨∇f(x), y − x⟩
d. Montrer que si f : ℝ^n → ℝ est différentiable sur ℝ^n, alors f est convexe si et seulement si pour tous x, y ∈ ℝ^n,
⟨∇f(y) − ∇f(x), y − x⟩ ⩾ 0
I.2. Soient f : ℝ^n → ℝ une fonction convexe et différentiable sur ℝ^n, et x^⋆ ∈ ℝ^n. Montrer que si ∇f(x^⋆) = 0 alors f admet un minimum global en x^⋆.
Définition. Soit α ∈ ℝ_+^⋆. On dit qu'une fonction f : ℝ^n → ℝ différentiable sur ℝ^n est α-convexe si pour tous x, y ∈ ℝ^n,
f(y) ⩾ f(x) + ⟨∇f(x), y − x⟩ + α/2‖y − x‖^2
I.3. On considère un réel α ∈ ℝ_+^⋆ et une fonction f : ℝ^n → ℝ différentiable sur ℝ^n.
a. On considère la fonction g_α : ℝ^n → ℝ définie par g_α(x) = f(x) − α/2‖x‖^2 pour tout x ∈ ℝ^n. Calculer ∇g_α(x) pour tout x ∈ ℝ^n, et montrer que f est α-convexe si et seulement g_α est convexe.
b. En déduire que f est α-convexe si et seulement si pour tous x, y ∈ ℝ^n,
⟨∇f(y) − ∇f(x), y − x⟩ ⩾ α‖y − x‖^2

Fonctions coercives

I.4. Soit f : ℝ^n → ℝ une fonction continue et coercive. Montrer que si K est un fermé non vide de ℝ^n, alors il existe x^⋆ ∈ K tel que f(x^⋆) = inf_(x ∈ K)f(x).
I.5. Soit f : ℝ^n → ℝ une fonction différentiable sur ℝ^n et α-convexe, où α ∈ ℝ_+^⋆. Montrer que si K est un convexe fermé non vide de ℝ^n, alors f admet un unique minimum sur K.

Projection sur un convexe fermé

I.6. Soient C un convexe fermé non vide de ℝ^n et x ∈ ℝ^n.
a. Montrer qu'il existe un unique point P_C(x) ∈ C tel que ‖P_C(x) − x‖ = inf_(y ∈ C)‖y − x‖.
b. Soit x¯ ∈ C. Montrer que x¯ = P_C(x) si et seulement si
⟨x − x¯, y − x¯⟩ ⩽ 0 pour tout y ∈ C
Indication : on pourra considérer la fonction ψ_y : t ∈ ℝ ↦ ‖x − (x¯ + t(y − x¯))‖^2, où y ∈ C.
c. En déduire que si x, y ∈ ℝ^n, alors ‖P_C(y) − P_C(x)‖ ⩽ ‖y − x‖.

Une première condition nécessaire d'optimalité

Soit K ⊂ ℝ^n. On dit qu'un vecteur h ∈ ℝ^n est K-admissible au point x ∈ K s'il existe
  • une suite (t_k)_(k ∈ ℕ) de réels strictement positifs vérifiant lim_(k → ∞)t_k = 0,
  • une suite (h_k)_(k ∈ ℕ) de vecteurs de ℝ^n vérifiant lim_(k → ∞)h_k = h,
    telles que pour tout k ∈ ℕ,
x + t_k h_k ∈ K.
On appelle cône K-admissible au point x ∈ K l'ensemble
A_K(x):={h ∈ ℝ^n, h est un vecteur K-admissible au point x}.
I.7. Décrire A_K(x) dans le cas où x est dans l'intérieur de K.
I.8. Montrer que si f : ℝ^n → ℝ est différentiable en x^⋆ ∈ K et admet un minimum local sur K en x^⋆, alors
∀h ∈ A_K(x^⋆), ⟨∇f(x^⋆), h⟩ ⩾ 0.
Qu'exprime ce résultat dans le cas particulier où x^⋆ est dans l'intérieur de K ?

II - Pénalisation

Dans le but d'approcher un minimum d'une fonction f sur K ⊂ ℝ^n, on cherche à se ramener à la minimisation d'une fonction sur ℝ^n tout entier. Pour ce faire, on propose d'ajouter à f un terme de "pénalisation", qui prend de grandes valeurs en dehors de K, et de minimiser la nouvelle fonction pénalisée sur ℝ^n tout entier. Cette partie a pour but de justifier cette approche dans un cas particulier.
Dans toute cette partie, on considère une fonction f : ℝ^n → ℝ différentiable sur ℝ^n et α-convexe, où α ∈ ℝ_+^⋆. On pose
K = {x ∈ ℝ^n, g_1(x) ⩽ 0, …, g_p(x) ⩽ 0}
où p ∈ ℕ^⋆ et g_1, …, g_p sont des fonctions convexes de ℝ^n dans ℝ, différentiables sur ℝ^n. On suppose de plus que l'ensemble K est non vide.
II.1. Montrer qu'il existe un unique élément x^⋆ ∈ K tel que f(x^⋆) = inf_(x ∈ K)f(x).
Pour tout k ∈ ℕ, on introduit la fonction f_k : ℝ^n → ℝ définie par
f_k(x) = f(x) + kΨ(x) pour tout x ∈ ℝ^n
où Ψ : ℝ^n → ℝ est la fonction définie par Ψ(x) = ∑_(i = 1)^p max(0, g_i(x))^2 pour tout x ∈ ℝ^n.
II.2. Pour tout x ∈ ℝ^n, calculer lim_(k → ∞)f_k(x).
II.3. Montrer que pour tout k ∈ ℕ, il existe un unique x_k ∈ ℝ^n tel que f_k(x_k) = inf_(x ∈ ℝ^n)f_k(x). Indication : on pourra commencer par montrer que si g : ℝ^n → ℝ est une fonction convexe, et h : ℝ → ℝ est une fonction convexe croissante, alors h ∘ g est convexe.
II.4. Montrer que pour tout k ∈ ℕ, f(x_k) ⩽ f(x^⋆).
II.5. On considère une sous-suite (x_(φ(k)))_(k ∈ ℕ) de (x_k)_(k ∈ ℕ) qui converge vers x¯ ∈ ℝ^n.
a. Montrer que x¯ ∈ K.
b. En déduire que x¯ = x^⋆.
II.6. En déduire que la suite (x_k)_(k ∈ ℕ) converge vers x^⋆.
II.7. Montrer que la suite (f_k(x_k))_(k ∈ ℕ) converge vers f(x^⋆).

III - Théorème de Karush-Kuhn-Tucker

Le but de cette partie est d'établir une condition nécessaire d'optimalité dans le cas où le domaine K est décrit par des contraintes de type inégalité.

Lemme de Farkas

Soient m ∈ ℕ^⋆ et (u_1, …, u_m) une famille de vecteurs de ℝ^n. On note
C = {∑_(i = 1)^m μ_i u_i, μ_i ⩾ 0∀i ∈ [ [1, m] ]}.
On cherche à démontrer le résultat suivant.
Lemme 1. Si v ∈ ℝ^n, alors une et une seule des deux assertions suivantes est vérifiée :
(i) v ∈ C,
(ii) il existe w ∈ ℝ^n tel que ⟨v, w⟩ < 0 et ⟨u_i, w⟩ ⩾ 0 pour tout i ∈ [ [1, m] ].
III.1. Le but de cette question est de montrer que C est un convexe fermé de ℝ^n.
a. Montrer que C est convexe.
b. Montrer que si (u_1, …, u_m) est une famille libre, alors C est fermé.
c. Pour tout I ⊂ [ [1, m] ], on pose C_I = {∑_(i ∈ I)μ_i u_i, μ_i ⩾ 0∀i ∈ I}. Montrer que
C = ⋃_I C_I
où l'union est prise sur les ensembles I ⊂ [ [1, m] ] tels que (u_i)_(i ∈ I) est une famille libre. En déduire que C est fermé.
III.2. On considère un vecteur v ∈ ℝ^n∖C.
a. Montrer que ⟨P_C(v), P_C(v) − v⟩ = 0.
b. On pose w = P_C(v) − v. Montrer que ⟨v, w⟩ < 0 et ⟨u_i, w⟩ ⩾ 0 pour tout i ∈ [ [1, m] ].
III.3. Conclure la preuve du lemme 1.

Condition nécessaire D'optimalité

Soit p ∈ ℕ^⋆. Dans toute la suite de cette partie, on suppose que f, g_1, …, g_p sont des fonctions de ℝ^n dans ℝ différentiables sur ℝ^n, et que
K = {x ∈ ℝ^n, g_1(x) ⩽ 0, …, g_p(x) ⩽ 0}
est non vide. Pour tout x ∈ K, on note
I_x = {i ∈ [ [1, p] ], g_i(x) = 0}.
III.4. Montrer que pour tout x ∈ K,
A_K(x) ⊂ {h ∈ ℝ^n, ∀i ∈ I_x, ⟨∇g_i(x), h⟩ ⩽ 0}.
III.5. On considère x^⋆ ∈ K et on fait l'hypothèse suivante :
il existe v ∈ ℝ^n tel que pour tout i ∈ I_(x^⋆), ⟨∇g_i(x^⋆), v⟩ < 0.
Montrer que A_K(x^⋆) = {h ∈ ℝ^n, ∀i ∈ I_(x^⋆), ⟨∇g_i(x^⋆), h⟩ ⩽ 0}.
III.6. Montrer que si x^⋆ ∈ K est tel que (∇g_i(x^⋆))_(i ∈ I_(x^⋆)) forme une famille libre, alors l'hypothèse (H) est vérifiée.
III.7. On suppose que f atteint en x^⋆ ∈ K un minimum local sur K, et que l'hypothèse (H) est vérifiée. Montrer qu'il existe des réels positifs μ_1^⋆, …, μ_p^⋆ tels que
{∇f(x^⋆) + ∑_(i = 1)^p μ_i^⋆∇g_i(x^⋆) = 0; μ_i^⋆g_i(x^⋆) = 0 pour tout i ∈ [ [1, p] ].
III.8. On suppose dans cette question que les fonctions f, g_1, …, g_p sont convexes. Soient x^⋆ ∈ K et μ_1^⋆, …, μ_p^⋆ ∈ ℝ_+tels que (1) soit vérifié. Montrer que f admet en x^⋆ un minimum global sur K.

IV - Étude DU PROBLÈME DUAL

Le but de cette partie est d'aborder la minimisation d'une fonction f sur un sous-domaine K de ℝ^n en considérant le problème "dual" associé. Dans un cas particulier, on propose une approche basée sur l'étude du problème dual pour obtenir une approximation du minimum de f sur K.
Soit p ∈ [ [1, n] ]. On suppose dans toute cette partie que f, g_1, …, g_p sont des fonctions de ℝ^n dans ℝ différentiables. On fait l'hypothèse supplémentaire que f est α-convexe pour un certain α ∈ ℝ_+^⋆, et que les fonctions g_1, …, g_p sont convexes. On suppose par ailleurs que
K = {x ∈ ℝ^n, g_1(x) ⩽ 0, …, g_p(x) ⩽ 0}
est non vide. Dans toute la suite, on note g(x) = (g_1(x); ⋮; g_p(x)) pour tout x ∈ ℝ^n.
On introduit la fonction L : ℝ^n × ℝ_+^p → ℝ définie par
L(x, μ) = f(x) + ∑_(i = 1)^p μ_i g_i(x)
pour tout x ∈ ℝ^n et tout μ = (μ_1, …, μ_p) ∈ ℝ_+^p. On s'intéresse au problème : trouver x^⋆ ∈ K tel que
f(x^⋆) = inf_(x ∈ K)f(x)
IV.1. Montrer que inf_(x ∈ K)f(x) = inf_(x ∈ ℝ^n)sup_(μ ∈ ℝ_+^p)L(x, μ).
IV.2. Montrer que pour tout μ ∈ ℝ_+^p, il existe un unique x_μ ∈ ℝ^n vérifiant L(x_μ, μ) = inf_(x ∈ ℝ^n)L(x, μ).
Pour tout μ ∈ ℝ_+^p, on note G(μ):=inf_(x ∈ ℝ^n)L(x, μ) = L(x_μ, μ). On va s'intéresser au problème dit dual : trouver μ^⋆ ∈ ℝ_+^p tel que
G(μ^⋆) = sup_(μ ∈ ℝ_+^p)G(μ) = sup_(μ ∈ ℝ_+^p)inf_(x ∈ ℝ^n)L(x, μ)
On dit que (x¯, μ¯) ∈ ℝ^n × ℝ_+^p est un point selle de L si
L(x¯, μ¯) = inf_(x ∈ ℝ^n)L(x, μ¯) et L(x¯, μ¯) = sup_(μ ∈ ℝ_+^p)L(x¯, μ)
IV.3. On suppose dans cette question que (x¯, μ¯) ∈ ℝ^n × ℝ_+^p est un point selle de L.
a. Montrer que x¯ est solution de (P).
b. Montrer que μ¯ est solution de ( Q ).
c. Montrer que inf_(x ∈ ℝ^n)sup_(μ ∈ ℝ_+^p)L(x, μ) = sup_(μ ∈ ℝ_+^p)inf_(x ∈ ℝ^n)L(x, μ).
IV.4. On considère x^⋆ ∈ K une solution de (P) satisfaisant l'hypothèse (H). Soit μ^⋆ = (μ_1^⋆, …, μ_p^⋆) comme dans la question III.7. Montrer que μ^⋆ est solution de (Q).
IV.5. On suppose dans toute cette question que la fonction μ ∈ ℝ_+^p ↦ x_μ est continue. On considère une solution μ¯ ∈ ℝ_+^p de (Q).
a. Soient μ ∈ ℝ_+^p et ξ ∈ ℝ^p tels que μ + ξ ∈ ℝ_+^p. Montrer que pour tout t ∈ [0, 1], μ + tξ ∈ ℝ_+^p, et
lim_(t → 0; t > 0)(G(μ + tξ) − G(μ))/t = ⟨g(x_μ), ξ⟩
En déduire que pour tout μ ∈ ℝ_+^p, ⟨g(x_(μ¯)), μ − μ¯⟩ ⩽ 0.
b. Montrer que x_(μ¯) est solution de (P).
IV.6. (Théorème d'Uzawa). Soient A ∈ M_(p, n)(ℝ) une matrice de rang p et b ∈ ℝ^p. On suppose que la fonction g est de la forme
g : x ↦ Ax + b.
a. Montrer que pour tout μ ∈ ℝ_+^p, ∇f(x_μ) = − ^t Aμ, et en déduire que la fonction μ ↦ x_μ est continue sur ℝ_+^p.
b. Montrer que ( P ) admet une unique solution x^⋆ ∈ K, et que ( Q ) admet une unique solution μ^⋆ ∈ ℝ_+^p.
Soit ρ > 0. On définit la suite (μ^k)_(k ∈ ℕ) par récurrence de la manière suivante :
  • on fixe μ^0 ∈ ℝ_+^p,
  • pour tout k ∈ ℕ, on pose μ^(k + 1) = P_(ℝ_+^p)(μ^k + ρg(x_(μ^k))),
    où P_(ℝ_+^p) : ℝ^p → ℝ_+^p désigne la projection sur le convexe fermé ℝ_+^p de ℝ^p.
    c. Montrer que μ^⋆ = P_(ℝ_+^p)(μ^⋆ + ρg(x_(μ^⋆))).
On suppose désormais que ‖Ax‖ ⩽ √(α/ρ)‖x‖ pour tout x ∈ ℝ^n.
d. Montrer que la suite (x_(μ^k))_(k ∈ ℕ) converge vers x^⋆.
e. Montrer que la suite (μ^k)_(k ∈ ℕ) converge vers μ^⋆.

Questions fréquentes

4 questions
Sur quels chapitres porte le sujet de mathématiques C de la banque inter-ENS MP 2020 ?
Afficher ou masquer la section

Sur quels chapitres porte le sujet de mathématiques C de la banque inter-ENS MP 2020 ?

Le sujet porte sur les fonctions convexes, l'optimisation sous contraintes, le lemme de Farkas, le théorème de Karush-Kuhn-Tucker et l'algorithme d'Uzawa.

Quelles erreurs le jury a-t-il le plus relevées sur ce sujet de maths C inter-ENS MP 2020 ?

Le jury signale un manque de rigueur sur des raisonnements élémentaires, une topologie souvent mal maîtrisée et des convergences admises sans démonstration.

Le sujet de mathématiques C inter-ENS MP 2020 est-il difficile ?

Le jury le juge relativement long mais globalement abordable, avec des questions plus ardues dans les parties III et IV ; la moyenne obtenue est de 9,03/20.

Quelle est la moyenne à l'épreuve de mathématiques C de la banque inter-ENS MP 2020 ?

La moyenne est de 9,03/20, avec un écart-type de 3,81 et des notes allant de 0 à 20.

Pas de description pour le moment