Maths C

# 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

L’utilisation des calculatrices n’est pas autorisée pour cette épreuve

Le sujet comprend 6 pages num´erot´ees de 1 `a 6.

? ? ?

L’objet de ce probl`eme est la minimisation sur un sous-domaine K ⇢Rn d’une fonction f d´efinie sur Rn. Nous proposons plusieurs approches pour trouver des conditions n´ecessaires d’optimalit´e, et obtenir des approximations des minimiseurs de f dans des cas particuliers.

Les d´ependances entre les parties du probl`eme sont donn´ees par le sch´ema suivant :

II

I %

&

III ! IV

Notations et d´efinitions

Pour tout entier k 2 N?, on d´esignera le produit scalaire usuel sur Rk par h·, ·i, et la norme euclidienne sur Rk par k · k.

Dans tout le sujet, on se place sur Rn, o`u n 2 N?.

– On dit qu’une fonction f : Rn ! R est convexe si pour tous x, y 2 Rn et tout λ 2 [0, 1],

f((1 −λ)x + λy) 6 (1 −λ)f(x) + λf(y).

– On dit qu’une fonction f : Rn ! R est coercive si lim kxk!+1 f(x) = +1, autrement dit :

8M > 0, 9R > 0, 8x 2 Rn, kxk > R ) f(x) > M.

I - Pr´eliminaires

Fonctions convexes

I.1. On consid`ere une fonction f : Rn ! R.

a. Pour tous x, y 2 Rn, soit 'x,y : R ! R la fonction d´efinie par 'x,y(t) = f(x + t(y −x)) pour

tout t 2 R. Montrer que f est convexe si et seulement si pour tous x, y 2 Rn, 'x,y est convexe.

b. On suppose que f est di↵´erentiable sur Rn. Montrer que pour tous x, y 2 Rn, la fonction 'x,y

est d´erivable, et montrer que pour tout t 2 R, '0

x,y(t) = hrf(x + t(y −x)), y −xi.

c. En d´eduire que si f est di↵´erentiable sur Rn, alors f est convexe si et seulement si pour tous

x, y 2 Rn,

f(y) > f(x) + hrf(x), y −xi.

d. Montrer que si f : Rn ! R est di↵´erentiable sur Rn, alors f est convexe si et seulement si

pour tous x, y 2 Rn,

hrf(y) −rf(x), y −xi > 0.

I.2. Soient f : Rn ! R une fonction convexe et di↵´erentiable sur Rn, et x? 2 Rn. Montrer que si rf(x?) = 0 alors f admet un minimum global en x?.

+. On dit qu’une fonction f : Rn ! R di↵´erentiable sur Rn est ↵-convexe si pour tous x, y 2 Rn,

D´efinition. Soit ↵2 R?

f(y) > f(x) + hrf(x), y −xi + ↵

2 ky −xk2.

+ et une fonction f : Rn ! R di↵´erentiable sur Rn.

I.3. On consid`ere un r´eel ↵2 R?

2 kxk2 pour tout x 2 Rn. Calculer rg↵(x) pour tout x 2 Rn, et montrer que f est ↵-convexe si et seulement g↵est convexe. b. En d´eduire que f est ↵-convexe si et seulement si pour tous x, y 2 Rn,

a. On consid`ere la fonction g↵: Rn ! R d´efinie par g↵(x) = f(x) −↵

hrf(y) −rf(x), y −xi > ↵ky −xk2.

Fonctions coercives

I.4. Soit f : Rn ! R une fonction continue et coercive. Montrer que si K est un ferm´e non vide de Rn, alors il existe x? 2 K tel que f(x?) = inf

x2K f(x).

I.5. Soit f : Rn ! R une fonction di↵´erentiable sur Rn et ↵-convexe, o`u ↵2 R?

+. Montrer que si K est un convexe ferm´e non vide de Rn, alors f admet un unique minimum sur K.

Projection sur un convexe ferm´e

I.6. Soient C un convexe ferm´e non vide de Rn et x 2 Rn.

a. Montrer qu’il existe un unique point PC(x) 2 C tel que kPC(x) −xk = inf

y2C ky −xk.

b. Soit ¯x 2 C. Montrer que ¯x = PC(x) si et seulement si

hx −¯x, y −¯xi 6 0 pour tout y 2 C.

Indication : on pourra consid´erer la fonction y : t 2 R 7! kx −(¯x + t(y −¯x))k2, o`u y 2 C. c. En d´eduire que si x, y 2 Rn, alors kPC(y) −PC(x)k 6 ky −xk.

Une premi`ere condition n´ecessaire d’optimalit´e

Soit K ⇢Rn. On dit qu’un vecteur h 2 Rn est K-admissible au point x 2 K s’il existe

– une suite (tk)k2N de r´eels strictement positifs v´erifiant lim

k!1 tk = 0,

– une suite (hk)k2N de vecteurs de Rn v´erifiant lim

k!1 hk = h,

telles que pour tout k 2 N,

x + tkhk 2 K.

On appelle cˆone K-admissible au point x 2 K l’ensemble

AK(x) := {h 2 Rn, h est un vecteur K-admissible au point x}.

I.7. D´ecrire AK(x) dans le cas o`u x est dans l’int´erieur de K.

I.8. Montrer que si f : Rn ! R est di↵´erentiable en x? 2 K et admet un minimum local sur K en x?, alors

8h 2 AK(x?), hrf(x?), hi > 0.

Qu’exprime ce r´esultat dans le cas particulier o`u x? est dans l’int´erieur de K ?

II - P´enalisation

Dans le but d’approcher un minimum d’une fonction f sur K ⇢Rn, on cherche `a se ramener `a la minimisation d’une fonction sur Rn tout entier. Pour ce faire, on propose d’ajouter `a f un terme de “p´enalisation”, qui prend de grandes valeurs en dehors de K, et de minimiser la nouvelle fonction p´enalis´ee sur Rn tout entier. Cette partie a pour but de justifier cette approche dans un cas particulier.

Dans toute cette partie, on consid`ere une fonction f : Rn ! R di↵´erentiable sur Rn et ↵-convexe, o`u ↵2 R?

+. On pose

K = {x 2 Rn, g1(x) 6 0, . . . , gp(x) 6 0},

o`u p 2 N? et g1, . . . , gp sont des fonctions convexes de Rn dans R, di↵´erentiables sur Rn. On suppose de plus que l’ensemble K est non vide.

II.1. Montrer qu’il existe un unique ´el´ement x? 2 K tel que f(x?) = inf

x2K f(x).

Pour tout k 2 N, on introduit la fonction fk : Rn ! R d´efinie par

fk(x) = f(x) + k (x) pour tout x 2 Rn,

p X

o`u : Rn ! R est la fonction d´efinie par (x) =

max(0, gi(x))2 pour tout x 2 Rn.

i=1

II.2. Pour tout x 2 Rn, calculer lim

k!1 fk(x).

II.3. Montrer que pour tout k 2 N, il existe un unique xk 2 Rn tel que fk(xk) = inf

x2Rn fk(x).

Indication : on pourra commencer par montrer que si g : Rn ! R est une fonction convexe, et h : R ! R est une fonction convexe croissante, alors h ◦g est convexe.

II.4. Montrer que pour tout k 2 N, f(xk) 6 f(x?).

II.5. On consid`ere une sous-suite (x'(k))k2N de (xk)k2N qui converge vers ¯x 2 Rn.

a. Montrer que ¯x 2 K.

b. En d´eduire que ¯x = x?.

II.6. En d´eduire que la suite (xk)k2N converge vers x?.

II.7. Montrer que la suite (fk(xk))k2N converge vers f(x?).

III - Th´eor`eme de Karush-Kuhn-Tucker

Le but de cette partie est d’´etablir une condition n´ecessaire d’optimalit´e dans le cas o`u le domaine K est d´ecrit par des contraintes de type in´egalit´e.

Lemme de Farkas

Soient m 2 N? et (u1, . . . , um) une famille de vecteurs de Rn. On note

( m X

)

µiui, µi > 0 8i 2 J1, mK

C =

.

i=1

On cherche `a d´emontrer le r´esultat suivant.

Lemme 1. Si v 2 Rn, alors une et une seule des deux assertions suivantes est v´erifi´ee :

(i) v 2 C,

(ii) il existe w 2 Rn tel que hv, wi < 0 et hui, wi > 0 pour tout i 2 J1, mK.

III.1. Le but de cette question est de montrer que C est un convexe ferm´e de Rn.

a. Montrer que C est convexe.

b. Montrer que si (u1, . . . , um) est une famille libre, alors C est ferm´e.

$ P

i2I µiui, µi > 0 8i 2 I

c. Pour tout I ⇢J1, mK, on pose CI =

. Montrer que

[

C =

CI,

I

o`u l’union est prise sur les ensembles I ⇢J1, mK tels que (ui)i2I est une famille libre. En d´eduire que C est ferm´e.

III.2. On consid`ere un vecteur v 2 Rn \ C.

a. Montrer que hPC(v), PC(v) −vi = 0.

b. On pose w = PC(v) −v. Montrer que hv, wi < 0 et hui, wi > 0 pour tout i 2 J1, mK.

III.3. Conclure la preuve du lemme 1.

Condition n´ecessaire d’optimalit´e

Soit p 2 N?. Dans toute la suite de cette partie, on suppose que f, g1, . . . , gp sont des fonctions de Rn dans R di↵´erentiables sur Rn, et que

K = {x 2 Rn, g1(x) 6 0, . . . , gp(x) 6 0}

est non vide. Pour tout x 2 K, on note

Ix = {i 2 J1, pK, gi(x) = 0}.

III.4. Montrer que pour tout x 2 K,

AK(x) ⇢{h 2 Rn, 8i 2 Ix, hrgi(x), hi 6 0}.

III.5. On consid`ere x? 2 K et on fait l’hypoth`ese suivante :

il existe v 2 Rn tel que pour tout i 2 Ix?, hrgi(x?), vi < 0. (H)

Montrer que AK(x?) = {h 2 Rn, 8i 2 Ix?, hrgi(x?), hi 6 0}.

III.6. Montrer que si x? 2 K est tel que (rgi(x?))i2Ix? forme une famille libre, alors l’hypoth`ese (H) est v´erifi´ee.

III.7. On suppose que f atteint en x? 2 K un minimum local sur K, et que l’hypoth`ese (H) est v´erifi´ee. Montrer qu’il existe des r´eels positifs µ?

1, . . . , µ? p tels que 8 > <

p X

rf(x?) +

µ?

i rgi(x?) = 0,

(1)

i=1

> :

µ?

i gi(x?) = 0 pour tout i 2 J1, pK.

III.8. On suppose dans cette question que les fonctions f, g1, . . . , gp sont convexes. Soient x? 2 K et µ?

1, . . . , µ? p 2 R+ tels que (1) soit v´erifi´e. Montrer que f admet en x? un minimum global sur K.

IV - ´Etude du probl`eme dual

Le but de cette partie est d’aborder la minimisation d’une fonction f sur un sous-domaine K de Rn en consid´erant le probl`eme “dual” associ´e. Dans un cas particulier, on propose une approche bas´ee sur l’´etude du probl`eme dual pour obtenir une approximation du minimum de f sur K.

Soit p 2 J1, nK. On suppose dans toute cette partie que f, g1, . . . , gp sont des fonctions de Rn dans R di↵´erentiables. On fait l’hypoth`ese suppl´ementaire que f est ↵-convexe pour un certain ↵2 R?

+, et que les fonctions g1, . . . , gp sont convexes. On suppose par ailleurs que

K = {x 2 Rn, g1(x) 6 0, . . . , gp(x) 6 0}

g1(x)

B B B B B B @

C C C C C C A

... gp(x)

pour tout x 2 Rn.

est non vide. Dans toute la suite, on note g(x) =

On introduit la fonction L : Rn ⇥Rp

+ ! R d´efinie par

p X

L(x, µ) = f(x) +

µigi(x),

i=1

pour tout x 2 Rn et tout µ = (µ1, . . . , µp) 2 Rp

+. On s’int´eresse au probl`eme : trouver x? 2 K tel que

f(x?) = inf

x2K f(x). (P)

L(x, µ).

IV.1. Montrer que inf

x2K f(x) = inf

x2Rn sup

µ2Rp

+

+, il existe un unique xµ 2 Rn v´erifiant L(xµ, µ) = inf

IV.2. Montrer que pour tout µ 2 Rp

x2Rn L(x, µ).

Pour tout µ 2 Rp

+, on note G(µ) := infx2Rn L(x, µ) = L(xµ, µ). On va s’int´eresser au probl`eme dit dual : trouver µ? 2 Rp

+ tel que

G(µ?) = sup µ2Rp

inf x2Rn L(x, µ). (Q)

G(µ) = sup µ2Rp

+

+

On dit que (¯x, ¯µ) 2 Rn ⇥Rp

+ est un point selle de L si

L(¯x, ¯µ) = inf

x2Rn L(x, ¯µ) et L(¯x, ¯µ) = sup

L(¯x, µ),

µ2Rp

+

IV.3. On suppose dans cette question que (¯x, ¯µ) 2 Rn ⇥Rp

+ 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

x2Rn sup

L(x, µ) = sup µ2Rp

inf x2Rn L(x, µ).

µ2Rp

+

+

IV.4. On consid`ere x? 2 K une solution de (P) satisfaisant l’hypoth`ese (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 µ 2 Rp

+ 7! xµ est continue. On consid`ere une solution ¯µ 2 Rp

+ de (Q).

+ et ⇠2 Rp tels que µ + ⇠2 Rp

a. Soient µ 2 Rp

+. Montrer que pour tout t 2 [0, 1], µ + t⇠2 Rp

+, et

G(µ + t⇠) −G(µ)

lim

t = hg(xµ), ⇠i.

t!0

t>0

En d´eduire que pour tout µ 2 Rp

+, hg(x¯µ), µ −¯µi 6 0.

b. Montrer que x¯µ est solution de (P).

IV.6. (Th´eor`eme d’Uzawa). Soient A 2 Mp,n(R) une matrice de rang p et b 2 Rp. On suppose que la fonction g est de la forme

g : x 7! Ax + b.

a. Montrer que pour tout µ 2 Rp

+, rf(xµ) = −tAµ, et en d´eduire que la fonction µ 7! xµ est continue sur Rp

+.

b. Montrer que (P) admet une unique solution x? 2 K, et que (Q) admet une unique solution

µ? 2 Rp

+.

Soit ⇢> 0. On d´efinit la suite (µk)k2N par r´ecurrence de la mani`ere suivante :

– on fixe µ0 2 Rp

+, – pour tout k 2 N, on pose µk+1 = PRp

+(µk + ⇢g(xµk)),

+ : Rp ! Rp

+ d´esigne la projection sur le convexe ferm´e Rp

+ de Rp.

o`u PRp

c. Montrer que µ? = PRp

+(µ? + ⇢g(xµ?)).

q

On suppose d´esormais que kAxk 6

↵

⇢kxk pour tout x 2 Rn.

d. Montrer que la suite (xµk)k2N converge vers x?.

e. Montrer que la suite (µk)k2N converge vers µ?.

? ? ?

Fin du sujet.