OpenSup

Début de l’épreuve Pour d ∈ N∗ et x = (x1, . . . , xd) et y = (y1, . . . , yd) dans Rd, nous noterons : • x · y le produit scalaire usuel de x et y. x · y := d i=1 xiyi • ∥x∥ := √x · x, la norme euclidienne usuelle de x, • [x, y] := {λx + (1 − λ)y, λ ∈ [0, 1]} le segment joignant x à y. On rappelle qu’une partie A de Rd est convexe si pour tout (x, y) ∈ A2, on a [x, y] ⊂ A. Si A et B sont deux parties non vides de Rd, x ∈ Rd et λ ∈ R, nous noterons A + B := {a + b, a ∈ A, b ∈ B}, λA := {λa, a ∈ A} A − B := A + (−1)B, A − x := A − {x} nous noterons dim(A) la dimension de l’espace vectoriel engendré par A − a où a est un élément quelconque de A (cette définition étant indépendante du choix de a ∈ A). En particulier si x et y appartiennent à Rd et x ̸= y, on a dim({x}) = 0, et dim([x, y]) = 1. Pour M ∈ Mm×d(R), nous identifierons toujours M à l’application linéaire dont M est la matrice dans les bases canoniques de Rd et Rm et noterons donc Ker(M) := x ∈ Rd : Mx = 0 , Im(M) := Mx, x ∈ Rd enfin M T désignera la transposée de M. Pour tout k ∈ N∗, nous noterons Rk + l’ensemble des éléments de Rk dont les coordon- nées sont dans R+ et pour y1 et y2 dans Rk, nous écrirons y1 ⩾ y2 (ou y2 ⩽ y1) quand y1 − y2 ∈ Rk +. On rappelle enfin que toute suite bornée d’éléments de Rk possède une extraction qui converge. Partie I : Projection et séparation Projection Soit C une partie non vide, convexe et fermée de Rd et x ∈ Rd, considérons : inf y∈C ∥x − y∥2. (1) 1) Montrer que (1) possède une unique solution (c’est à dire qu’il existe un unique y ∈ C tel que ∥x − y∥2 ⩽ ∥x − z∥2 pour tout z ∈ C) que nous appellerons projection de x sur C et noterons projC(x). Montrer que x = projC(x) si et seulement si x ∈ C. 1 2) Soit y ∈ Rd montrer que y = projC(x) ⇐⇒ y ∈ C et (x − y) · (z − y) ⩽ 0, ∀z ∈ C. 3) Montrer que pour tout (x1, x2) ∈ Rd × Rd, on a (projC (x1) − projC (x2)) · (x1 − x2) ⩾ ∥projC (x1) − projC (x2)∥2 , et en déduire que projC est continue. 4) Déterminer explicitement projC dans les cas suivants : i) C = Rd +, ii)C = y ∈ Rd : ∥y∥ ⩽ 1 , iii) C = y ∈ Rd : d i=1 yi ⩽ 1 , iv)C = [−1, 1]d. Séparation Soit C et D deux parties convexes non vides de Rd telles que C est fermée et bornée, D est fermée, et C ∩ D = ∅. 5) Montrer que D − C est une partie convexe fermée de Rd ne contenant pas 0. 6) Montrer qu’il existe p ∈ Rd et ε > 0 tels que p · x ⩽ p · y − ε, ∀(x, y) ∈ C × D. (on dit que C et D peuvent être séparés strictement). 7) Soit C une partie convexe fermée non vide de Rd et soit σC : Rd → R ∪ {+∞} définie par : σC(p) := sup{p · x, x ∈ C} montrer que C = x ∈ Rd : p · x ⩽ σC(p), ∀p ∈ Rd (de sorte que C est une intersection de demi-espaces fermés). 8) Soit A une partie convexe non vide de Rd et x ∈ Rd\A, montrer qu’il existe p ∈ Rd\{0} tel que p · x ⩽ p · y, ∀y ∈ A. 2 Partie II : Points extrémaux Soit E une partie de Rd, on appelle enveloppe convexe de E et l’on note co(E) l’en- semble co(E) := I i=1 λixi, I ∈ N∗, λi ⩾ 0, I i=1 λi = 1, (x1, . . . , xI) ∈ EI . Soit A une partie convexe non vide de Rd, nous dirons que x ∈ A est un point extrémal de A si ∀(y, z, λ) ∈ A × A×]0, 1[, on a x = (1 − λ)y + λz ⇒ y = z. Nous noterons Ext(A) l’ensemble des points extrémaux de A. Cas particuliers 9) Soit A une partie convexe non vide de Rd. Soit I ∈ N∗, x1, . . . xI ∈ AI et (λ1, . . . , λI) ∈ RI + tels que I i=1 λi = 1, montrer que : • a) I i=1 λixi ∈ A, • b) si x := I i=1 λixi ∈ Ext(A) alors xi = x pour tout i ∈ {1, . . . , I} tel que λi > 0. 10) Soit E une partie de Rd montrer que co(E) est le plus petit convexe contenant E et que Ext(co(E)) ⊂ E. 11) Soit A = co(E) où E est la partie de R3 définie par E = {(0, 0, 1), (0, 0, −1)} ∪ {(1 + cos(θ), sin(θ), 0), θ ∈ [0, 2π]} montrer que Ext(A) est non vide et n’est pas fermée. 12) Soit k ∈ N∗, (p1, . . . , pk) ∈ Rd k et (b1, . . . , bk) ∈ Rk tels que A := x ∈ Rd : pi · x ⩽ bi, i = 1, . . . , k soit non vide. Montrer que A est convexe et fermée. Soit x ∈ A, soit I(x) := {i ∈ {1, . . . , k} : pi · x = bi}, montrer que x ∈ Ext(A) ⇐⇒ rang ({pi, i ∈ I(x)}) = d en déduire que Ext(A) est un ensemble fini (éventuellement vide) dont le cardinal est inférieur ou égal à 2k. 3 Cas d’un convexe fermé borné Dans les trois questions qui suivent, K est une partie non vide, convexe, fermée et bornée de Rd. 13) Soit p ∈ Rd, posons Kp := {x ∈ K : p · x ⩽ p · y, ∀y ∈ K}. Montrer que Kp est non vide, convexe et fermée et que Ext (Kp) ⊂ Ext(K). 14) Montrer que Ext(K) est non vide (on pourra se ramener au cas où 0 ∈ K et raisonner sur la dimension de K). 15) Montrer que K = co(Ext(K)). Partie III : Un résultat de dualité Cônes convexes On dit qu’une partie F de Rd est un cône si λF ⊂ F pour tout λ ∈ R+. Soit E une partie non vide de Rd, le cône polaire de E est défini par E+ := p ∈ Rd : p · x ⩾ 0, ∀x ∈ E et son cône bi-polaire par E++ = E+ + := ξ ∈ Rd : ξ · p ⩾ 0, ∀p ∈ E+ . 16) Montrer que E+ et E++sont des cônes convexes fermés et que E ⊂ E++. 17) Montrer que E = E++ si et seulement si E est un cône convexe fermé. 18) Soit ξ1, . . . , ξk, k éléments de Rd et F := k i=1 λiξi, (λ1, . . . , λk) ∈ Rk + montrer que F est un cône convexe fermé. Soit ξ ∈ Rd, montrer que l’équivalence entre : • ξ ∈ F, • ξ · x ⩾ 0 pour tout x ∈ Rd tel que ξi · x ⩾ 0, i = 1, . . . , k. 4 Programmation linéaire Soit M ∈ Mk×d(R), b = (b1, . . . , bk) ∈ Rk et p ∈ Rd. Posons α := inf p · x : x ∈ Rd, x ⩾ 0, Mx ⩽ b et β := sup b · q : q ∈ Rk, q ⩽ 0, M Tq ⩽ p (en adoptant la convention : inf ∅ = +∞ et sup ∅ = −∞). 19) Montrer que α ⩾ β. 20) On suppose qu’il existe ¯x = (¯x1, . . . , ¯xd) ∈ Rd tel que ¯x ⩾ 0, M ¯x ⩽ b et p · ¯x = α. En notant Mi le vecteur de Rd dont les coordonnées sont les coefficients de la i-ème ligne de M, posons : I := {i ∈ {1, . . . , k} : Mi · ¯x = bi} et J := {j ∈ {1, . . . , d} : ¯xj = 0} . • a) Montrer que p · z ⩾ 0 pour tout z ∈ Rd tel que zj ⩾ 0 pour tout j ∈ J et Mi · z ⩽ 0 pour tout i ∈ I. • b) Montrer qu’il existe ¯q ∈ Rk tel que : ¯q ⩽ 0, M T ¯q ⩽ p, ¯q · (M ¯x − b) = 0 et p − M T ¯q · ¯x = 0. • c) Montrer que b · ¯q = α = β. Partie IV : Systèmes linéaires sous-déterminés Pour tout x = (x1, . . . , xd) ∈ Rd, on pose ∥x∥1 := d i=1 |xi| , ∥x∥∞ := max {|xi| , i = 1, . . . , d} I+(x) := {i ∈ {1, . . . , d} : xi > 0} , I−(x) := {i ∈ {1, . . . , d} : xi < 0} 5 et I0(x) := {i ∈ {1, . . . , d} : xi = 0} . Soit M ∈ Mk×d(R) et supposons que rang(M) = k. Soit b ∈ Rk\{0}, l’objectif de cette partie est de trouver une solution du système linéaire Mx = b ayant au plus k coordonnées non nulles par une méthode de minimisation. Pour ce faire, on s’intéresse à : r := inf ∥x∥1, x ∈ Rd, Mx = b . 21) Montrer que pour tout x ∈ Rd, on a ∥x∥1 = max x · y, y ∈ Rd, ∥y∥∞ ⩽ 1 , et ∥x∥∞ = max x · y, y ∈ Rd, ∥y∥1 ⩽ 1 . 22) Notons C l’ensemble : C := x ∈ Rd : Mx = b, ∥x∥1 = r . Montrer que C est non vide, convexe, fermé et borné. 23) Fixons ¯x ∈ C. Montrer qu’il existe q ∈ K er(M)⊥\{0} tel que pour tout i ∈ {1, . . . , d}, on ait qi¯xi = ∥q∥∞ |¯xi| . 24) Soit K l’ensemble des y ∈ Rd tels que My = b, yi = 0 ∀i ∈ I0(¯x), qiyi ⩾ 0 ∀i ∈ {1, . . . d} Montrer que K est non vide et inclus dans C. 25) Montrer que si y ∈ Ext(K) alors h ∈ Ker(M) et I0(y) ⊂ I0(h) ⇒ h = 0. 26) En déduire que si y ∈ Ext(K) alors le cardinal de I+(y) ∪ I−(y) est inférieur ou égal à k. Fin du sujet. 6

UN CORRIGÉ du SUJET X-ENS 2022, MATH PSI 0. (Préliminaires). Si A est une partie non vide de IRd, si a et b sont deux points de A, alors les parties A − a et A − b engendrent le mˆeme sous-espace vectoriel de IRd. En effet, si x ∈ Vect(A − a), alors il existe k ∈ IN∗, des réels λ1, · · ·, λk, et des éléments x1, · · ·, xk de A tels que x = k i=1 λi(xi − a). On peut alors écrire x = k i=1 λi(xi − b) − k i=1 λi (a − b) , ce qui prouve que x ∈ Vect(A − b). L’inclusion inverse se prouve de la mˆeme fa¸con, on a donc Vect(A − a) = Vect(A − b) et je noterai par la suite VA ce s.e.v. de IRd, on pose alors dim(A) = dim(VA). La partie A est alors incluse dans le sous-espace affine a+VA, ou a est un point quelconque de A, et elle n’est incluse dans aucun sous-espace affine de dimension strictement inférieure. Remarque. Aucune notion affine ne figure au programme de la filière PCSI-PSI, alors que le thème abordé dans ce sujet me semble indissociable de ces notions. Je n’ai donc pas hésité à faire appel au vocabulaire de la géométrie affine dans ce corrigé déjà très long, et qui l’aurait été encore plus si j’avais dˆu faire de longues périphrases à chaque question ou intervenait naturellement un sous-espace affine. J’ajouterai que ce sujet très académique, ressemblant à un cours de préparation à l’agrégation (avec un certain nombre de maladresses, qui plus est), me semble totalement délirant pour la filière PSI, mˆeme au niveau X-ENS! Partie I. Projection et séparation Projection 1. • Soit m = d(x, C)2 = inf y∈C ∥x − y∥2. L’application f : IRd →IR y →∥x − y∥2 est continue, donc elle admet un minimum µ sur la partie fermée bornée non vide K = C ∩ B(x, √ m + 1). En effet, f est continue comme composée de y → ∥x − y∥ qui est 1-lipschitzienne sur IRd et de t → t2 qui est continue sur IR. Et K est fermé comme intersection de deux fermés. Comme f > m + 1 sur C \ K et que, par définition d’une borne inférieure, il existe y ∈ C tel que f(y) ≤ m + 1, on a donc m = inf y∈K f(y) = µ, d’ou l’existence d’au moins un y1 ∈ C tel que ∥x − y1∥2 = m. • Si on a aussi f(y2) = m avec y2 ∈ C, alors y = y1 + y2 2 ∈ C car C est convexe, et ∥x − y∥ = x − y1 + y2 2 = 1 2 (x − y1) + (x − y2) ≤ 1 2 ∥x − y1∥ + ∥x − y2∥ = √m = d(x, C) , et cette “inégalité triangulaire” est une égalité puisqu’on ne peut avoir ∥x−y∥ < d(x, C), ce qui n’est possible que si les vecteurs x − y1 et x − y2 sont positivement liés, ce qui entraˆıne leur égalité puisqu’ils sont de mˆeme norme √m, et par la suite y2 = y1. Il y a donc existence et unicité du point y0 ∈ C tel que ∥x−y0∥2 = min y∈C ∥x−y∥2 = d(x, C)2, on pose alors projC(x) = y0. • Si x ∈ C, il est clair que min y∈C ∥x − y∥2 = 0 = ∥x − x∥2 donc projC(x) = x. Inversement, si x = projC(x), par définition de ce projeté sur C, on a bien x ∈ C. 2. • Si y = projC(x), alors clairement y ∈ C. Si on se donne z ∈ C, alors ut := (1 − t)y + tz ∈ C pour tout t ∈ [0, 1] car C est convexe, donc ∥ut − x∥2 ≥ ∥y − x∥2 = d(x, C)2. Ainsi ∀t ∈ [0, 1] (1 − t)(y − x) + t(z − x) 2 ≥ ∥y − x∥2 . En développant, ∀t ∈ [0, 1] f(t) := t(t − 2) ∥y − x∥2 + 2t(1 − t) (y − x) · (z − x) + t2 ∥z − x∥2 ≥ 0 . Cette fonction f (c’est un trinˆome) est dérivable sur IR, nulle en 0, positive sur [0, 1], ce qui entraˆıne f ′(0) ≥ 0, soit (c’est aussi le coefficient de t dans le développement du trinˆome): −2 ∥y − x∥2 + 2 (y − x) · (z − x) ≥ 0 , ce que l’on factorise en 2 (y − x) · (z − x) − (y − x) ≥ 0 , ou encore (x − y) · (z − y) ≤ 0 , et cela prouve l’implication dans le sens direct. • Si y ∈ C vérifie ∀z ∈ C (x − y) · (z − y) ≥ 0, alors pour tout z ∈ C, on a ∥x − z∥2 = (x − y) + (y − z) 2 = ∥x − y∥2 + 2 (x − y) · (y − z) + ∥y − z∥2 ≥ ∥x − y∥2 puisque les deux derniers termes sont positifs. Donc ∥x − y∥2 = d(x, C)2 et on a bien y = projC(x). 3. • Posons y1 = projC(x1) et y2 = projC(x2), alors (y1 − y2) · (x1 − x2) − ∥y1 − y2∥2 = (y1 − y2) · (x1 − x2) − (y1 − y2) = (y1 − y2) · (x1 − y1) − (x2 − y2) = − (x2 − y2) · (y1 − y2) + (x1 − y1) · (y2 − y1) ≥ 0 car les deux termes dans le crochet sont négatifs en vertu de la question 2. ci-dessus, le premier car y2 = projC(x2) et y1 ∈ C, le second pour la mˆeme raison en intervertissant les indices. On a donc prouvé que projC(x1) − projC(x2) · (x1 − x2) ≥ projC(x1) − projC(x2) 2 . • De l’inégalité de Cauchy-Schwarz, on déduit alors que ∀(x1, x2) ∈ (IRd)2 projC(x1) − projC(x2) 2 ≤ projC(x1) − projC(x2) ∥x1 − x2∥ . En séparant les cas projC(x1) − projC(x2) = 0 ou ̸= 0, on obtient ∀(x1, x2) ∈ (IRd)2 projC(x1) − projC(x2) ≤ ∥x1 − x2∥ . L’application projC : IRd → IRd est alors 1-lipschitzienne, donc continue. 4. Je ne justifierai pas à chaque fois que les ensembles C considérés sont des convexes fermés non vides de IRd, c’est assez immédiat. i. Pour C = IRd + (orthant fermé), si x = (x1, · · · , xd) ∈ IRd, posons y = (x+ 1 , · · · , x+ d ) avec x+ i = max{0, xi} pour tout i. Alors y ∈ C et, pour tout z = (z1, · · · , zd) ∈ C, on a (x − y) · (z − y) = d i=1 (xi − x+ i )(zi − x+ i ) = i∈J xizi ≤ 0 en posant J = i ∈ [[1, d]] | xi < 0 . Donc y = projC(x) d’après 2. ii. Pour C = y ∈ IRd | ∥y∥ ≤ 1 (boule unité fermée), posons y = x si ∥x∥ ≤ 1 x ∥x∥ si ∥x∥ > 1. • Dans le cas ∥x∥ ≤ 1 (i.e. x ∈ C), il est clair que y = x = projC(x). • Dans le cas ∥x∥ > 1, on a ∥y∥ = 1 donc y ∈ C. Si on prend z ∈ C, i.e. ∥z∥ ≤ 1, alors y · (z − y) = y · z − ∥y∥2 = y · z − 1 ≤ 1 × ∥z∥ − 1 ≤ 0 en utilisant l’inégalité de Cauchy-Schwarz. Puis x = ∥x∥ y, donc (x − y) · (z − y) = ∥x∥ − 1 y · (z − y) ≤ 0 . De nouveau grˆace à Q2., on conclut que y = projC(x). Faire un dessin! iii. Pour C = y ∈ IRd d i=1 yi ≤ 1 (demi-espace fermé), alors C = {y ∈ IRd | u · y ≤ 1} avec u = (1, · · · , 1) ∈ IRd. • Si x ∈ C, il est clair que projC(x) = x. • Si x ̸∈ C, soit y le projeté orthogonal de x sur l’hyperplan affine H = {y ∈ IRd |u·y = 1}. Bien sˆur ces notions ne sont pas au programme PSI, mais elles permettent d’illustrer l’idée de la construction. On cherche un “point” y ∈ IRd tel que (1) : y ∈ H i.e. u · y = 1 (2) : ∃λ ∈ IR y − x = λu . Ces deux conditions entraˆınent λ = 1 d (1 − u · x), donc y = x + 1 − u · x d u est la seule solution de ce système. On a bien y ∈ C. Notons par ailleurs que λ < 0 puisque u · x > 1, donc si z ∈ C, i.e. si u · z ≤ 1, alors (x − y) · (z − y) = −λ u · (z − y) = −λ (u · z − u · y) = −λ (u · z − 1) ≤ 0 , ce qui permet d’affirmer que y = projC(x) toujours d’après la question 2. iv. Pour C = [−1, 1]d (hypercube plein), introduisons la fonction f : IR → [−1, 1] définie par f(x) = −1 si x ≤ −1 x si −1 ≤ x ≤ 1 1 si x ≥ 1 . Si x = (x1, · · · , xd) ∈ IRd, soit y = f(x1), · · · , f(xd) , montrons que projC(x) = y. Clairement y ∈ C et, si z = (z1, · · · , zd) ∈ C, i.e. si −1 ≤ zi ≤ 1 pour tout i, alors (x − y) · (z − y) = d i=1 xi − f(xi) zi − f(xi) et tous les termes de cette somme sont négatifs. En effet, - si xi ∈ [−1, 1], alors f(xi) = xi et le terme d’indice i est nul ; - si xi < −1, alors f(xi) = −1 puis xi − f(xi) < 0 et zi − f(xi) = zi + 1 ≥ 0 ; - si xi > 1, alors f(xi) = 1 puis xi − f(xi) > 0 et zi − f(xi) = zi − 1 ≤ 0. On a donc (x − y) · (z − y) ≤ 0 pour tout z ∈ C. De nouveau, on déduit que y = projC(x). Séparation 5. On a D − C = y − x ; (x, y) ∈ C × D . De C ∩ D = ∅, on déduit que 0 ̸∈ D − C. Soient z = y − x ∈ D − C, z′ = y′ − x′ ∈ D − C avec (x, y) ∈ C × D et (x′, y′) ∈ C × D, soit λ ∈ [0, 1], alors λz + (1 − λ)z′ = λ(y − x) + (1 − λ)(y′ − x′) = λy + (1 − λ)y′ − λx + (1 − λ)x′ ∈ D − C puisque C et D sont convexes. Soit (zn) une suite convergente d’éléments de D−C, avec zn = yn−xn ou xn ∈ C et yn ∈ D pour tout n. Soit z = lim n→+∞ zn. La suite (xn) est bornée, donc possède une extraction convergente, i.e. il existe une application ϕ : IN → IN strictement croissante telle que lim n→+∞ xϕ(n) = x. Comme C est fermé, x ∈ C. Puis yϕ(n) = zϕ(n) + xϕ(n) −→ n→+∞ z + x. Comme D est fermé, z + x ∈ D. Finalement, z = (z + x) − x ∈ D − C. L’ensemble D − C est donc fermé dans IRd. 6. Comme D − C est une partie non vide, convexe et fermée de IRd, on peut introduire p = projD−C(0). Alors p ̸= 0 puisque 0 ̸∈ D − C et, d’après Q2., ∀z ∈ D − C (0 − p) · (z − p) ≤ 0 , i.e. p · z ≥ ∥p∥2 . Posons alors ε = ∥p∥2 > 0, on a donc ∀(x, y) ∈ C × D p · y − p · x ≥ ε , i.e. p · x ≤ p · y − ε . 7. Soit C un convexe fermé non vide, posons C′ = y ∈ IRd | ∀p ∈ IRd p · y ≤ σC(p) . L’inclusion C ⊂ C′ est immédiate. Soit x ∈ IRd tel que x ̸∈ C, alors {x} est un convexe fermé non vide et borné, disjoint de C qui est un convexe fermé non vide, on peut donc le séparer strictement de C, i.e. il existe p ∈ IRd et ε > 0 tels que ∀y ∈ C p · x ≤ p · y − ε. On a donc (−p) · y ≤ (−p) · x − ε pour tout y ∈ C, donc σC(−p) = sup y∈C (−p) · y ≤ (−p) · x − ε < (−p) · x , donc x ̸∈ C′. Ceci montre l’autre inclusion C′ ⊂ C. Remarque. On peut “zapper” une partie des questions précédentes pour arriver ici à nos fins, par exemple il n’est pas vraiment utile de parler d’extraction d’une suite à valeurs dans le singleton {x}... Il suffit de dire que, si x ̸∈ C, alors y = projC(x) ̸= x et, en choisissant p = x−y, on montre facilement à l’aide de Q2. que σC(p) = p·y. En effet, pour tout z ∈ C, on a (x − y) · (z − y) ≤ 0 , i.e. p · (z − y) ≤ 0 , i.e. p · z ≤ p · y . On en déduit que p · y = max z∈C (p · z) = σC(p). Puis p · x − p · y = p · (x − y) = ∥p∥2 > 0 donc p · x > σC(p), et donc x ̸∈ C′. 8. Soit j’ai loupé quelque chose de “simple”, soit cette question me semble totalement hors de portée d’un étudiant de PSI, mˆeme pour le concours X-ENS! Lemme 1. (facile) Si A est un convexe non vide, alors son adhérence C = A est un convexe non vide et fermé. Preuve. Si x ∈ A, y ∈ A et λ ∈ [0, 1], alors il existe des suites (xn) et (yn) d’éléments de A convergeant vers x et y respectivement, donc λxn + (1 − λ)yn −→ n→+∞ λx + (1 − λ)y et, comme A est convexe, on a λxn + (1 − λ)yn ∈ A pour tout n ∈ IN, donc λx + (1 − λ)y ∈ A, ce qui prouve la convexité de A. Pour montrer que A est fermé (il n’est pas clairement écrit dans les programmes que ceci soit censé ˆetre connu), montrons que A = A. L’inclusion indirecte est immédiate puisque A ⊂ A. Pour l’autre inclusion, si x ∈ A et r > 0, alors il existe y ∈ A ∩ B x, r 2 , puis comme y est adhérent à A, il existe z ∈ A ∩ B y, r 2 . Par l’inégalité triangulaire, z ∈ B(x, r), donc A ∩ B(x, r) ̸= ∅. Toute boule centrée en x rencontre A, donc x ∈ A. Lemme 2. Si A est un convexe non vide de IRd, alors ◦ A = ◦ A. Preuve. Je renvoie le lecteur à l’annexe 1 en fin de ce document, s’inspirant d’idées trouvées sur Wikipédia... Soit alors x ∈ IRd \ A. Deux cas se présentent: • si x ̸∈ C = A, alors (c’est presque la remarque à la fin du corrigé de la question précédente), soit y = projC(x), alors y ∈ C et y ̸= x. En posant p = y − x, on a par Q2., ∀z ∈ C p · z − p · y = (y − x) · (z − y) = −(x − y) · (z − y) ≥ 0 , donc p · z ≥ p · y . Puis p · y − p · x = ∥p∥2 > 0 donc p · y > p · x, et par transitivité p · z ≥ p · x pour tout z ∈ C, donc a fortiori pour tout z ∈ A. • si x ∈ C = A, alors il existe une suite (xn) d’éléments de IRd \ C qui converge vers x. En effet, comme x ̸∈ A, alors a fortiori x ̸∈ ◦ A, donc par le lemme 2, x ̸∈ ◦ A, donc x ∈ IRd \ ◦ A = IRd \ A = IRd \ C . Alors pour tout n, on peut trouver pn ∈ IRd non nul tel que pn ·xn ≤ pn ·y pour tout y ∈ A. On peut supposer les vecteurs pn unitaires quitte à remplacer pn par pn ∥pn∥. La suite (pn) étant maintenant bornée, il en existe une sous-suite convergente (pϕ(n)) de limite p (vecteur unitaire lui aussi). Si on se donne y ∈ A, on a alors pϕ(n) · xϕ(n) ≤ pϕ(n) · y pour tout n et, en passant à la limite, on obtient p · x ≤ p · y, ce qu’il fallait démontrer. 8 bis. Je ne comprends pas bien les choix faits dans cette question 8. En effet, pour traiter la suite du sujet, il aurait suffi de la remplacer par la question suivante, moins difficile: “Montrer que, si C est un convexe fermé non vide de IRd et si x ∈ IRd appartient à la frontière de C, alors il existe un hyperplan d’appui passant par x, i.e. il existe p ∈ IRd\{0} tel que ∀y ∈ C p·x ≤ p·y.” Cela se traite avec les mˆemes méthodes, sans avoir besoin des lemmes 1 et 2. Partie II. Points extrémaux Cas particuliers 9.a. Par récurrence sur l’entier I: c’est évident pour I = 1, c’est la définition d’un convexe pour I = 2 et, si c’est vrai pour un I ≥ 2, si x = I+1 i=1 λixi avec les λi positifs de somme 1 et les xi dans A, alors: - si λI+1 = 1 (et les autres λi nuls), alors x ∈ A est évident ; - sinon, y = λ1x1 + · · · + λIxI λ1 + · · · + λI ∈ A par l’hypothèse de récurrence, puis x = (λ1 + · · · + λI) y + λI+1xI+1 ∈ A puisque λ1 + · · · + λI et λI+1 sont positifs de somme 1. b. Si x = I i=1 λixi ∈ Ext(A), si i ∈ [[1, I]] est tel que λi > 0, alors: - si λi = 1, les autres λj sont nuls et x = xi ; - sinon, posons y = j̸=i λjxj j̸=i λj , alors y ∈ A d’après a., et x = λixi +µy en posant µ = j̸=i λj, les réels λi et µ sont dans ]0, 1[ et ont pour somme 1, donc par la définition d’un point extrémal, on a xi = y, ce qui entraˆıne aussi xi = x. 10. • L’inclusion E ⊂ co(E) est immédiate. • Si x et y sont dans co(E), si α ∈ [0, 1], on écrit x = I i=1 λixi et y = J j=1 µjyj avec les xi et les yj dans E, les réels λi positifs de somme 1 et idem pour les µj, alors αx + (1 − α)y = I i=1 αλixi + J j=1 (1 − α)µjyj ∈ co(E) puisque les réels αλ1, · · ·, αλI, (1 − α)µ1, · · ·, (1 − α)µJ sont positifs de somme 1. Ceci prouve que l’ensemble co(E) est convexe. • Si C est un convexe contenant E, il résulte de 9.a. que tout élément de co(E) appartient à C. On conclut donc que co(E) est le plus petit convexe contenant E. • Soit x ∈ Ext co(E) . On a x ∈ co(E), donc x = I i=1 λixi avec les λi positifs de somme 1, et les xi dans E donc a fortiori dans co(E). Il existe au moins un indice i ∈ [[1, I]] pour lequel λi > 0, on a alors x = xi d’après 9.b., donc x ∈ E. Ainsi, Ext co(E) ⊂ E. Remarque 1. Si E = ∅, en convenant qu’alors co(E) = ∅, tout ceci reste vrai. Remarque 2. Cette inclusion est souvent stricte. Par exemple, si E est un carré plein de sommets A, B, C, D dans le plan, alors E est convexe donc co(E) = E, puis Ext co(E) = {A, B, C, D}. 11. • Le point (0, 0, 1) appartient à E, donc aussi à A = co(E) et c’est le seul point de A dont la cote est supérieure ou égale à 1, c’est donc un point extrémal de A, donc Ext(A) ̸= ∅. • Les points mθ = (1 + cos θ, sin θ, 0), avec θ ∈]0, 2π[, sont tous des points extrémaux de A, mais pas l’origine (0, 0, 0) qui est pourtant la limite de mθ lorsque θ → 0 puisque c’est le milieu du segment joignant (0, 0, 1) et (0, 0, −1), donc Ext(A) n’est pas fermé. Remarque. L’ensemble E est la réunion du cercle C de centre (1, 0, 0) et de rayon 1 dans le plan horizontal x0y, et des points N = (0, 0, 1) et S = (0, 0, −1). Notons D le disque fermé du plan xOy délimité par le cercle C. Alors A = co(E) est la réunion des segments [M, N] et des segments [M, S] avec M décrivant D. Enfin, Ext(A) = (0, 0, 1), (0, 0, −1) ∪ (1 + cos θ, sin θ, 0) ; θ ∈ [0, 2π] \ {π} = E \ (0, 0, 0) . Bien sˆur, tout ceci mériterait peut-ˆetre d’ˆetre justifié, argumenté... et agrémenté d’un joli dessin en 3D. 12. • Les formes linéaires x → pi · x étant continues sur IRd, l’ensemble A est fermé car c’est une intersection de k fermés. • Si x ∈ A et y ∈ A, si λ ∈ [0, 1], alors pour tout i, on a bi −pi ·x ≥ 0 et bi −pi ·y ≥ 0, donc bi − pi · λx + (1 − λ)y = λ(bi − p·x) + (1 − λ)(bi − pi · y) ≥ 0 , donc λx + (1 − λ)y ∈ A. L’ensemble A est donc convexe. ▷ Pour la suite, notons x un élément de A, soit Fx = Vect (pi)i∈I(x) et rx = dim(Fx). • Si x n’est pas extrémal, alors il existe y ∈ A et z ∈ A avec y ̸= z tels que x = y + z 2 . On a donc z − x = −(y − x) et y ̸= x. Pour tout i ∈ I(x), on a pi · x = bi, pi · y ≤ bi et pi · z ≤ bi. Donc pi · (y − x) ≤ 0 et pi · (z − x) = −pi · (y − x) ≤ 0, ce qui entraˆıne pi · (y − x) = 0. Le vecteur y − x est non nul et appartient à F ⊥ x , donc rx = dim(Fx) < d. • Si rx < d, il existe un vecteur non nul u dans F ⊥ x . On va en déduire l’existence d’un réel δ > 0 tel que [x − δu, x + δu] ⊂ A, ce qui montrera que x n’est pas extrémal dans A. En effet, - si i ∈ I(x), alors pi · u = 0 donc pour tout α réel, pi · (x + αu) = pi · x = bi ; - si i ∈ [[1, k]] \ I(x), on peut écrire pi · x = bi − εi avec εi > 0, donc si α est réel, pi · (x + αu) = bi − εi + α pi · u et cette expression reste majorée par bi pour |α| petit, disons pour |α| ≤ δi avec δi > 0. En prenant δ = min i∈[[1,k]]\I(x) δi, on a trouvé un δ > 0 tel que [x − δu, x + δu] ⊂ A. Bilan. On a prouvé l’équivalence x ̸∈ Ext(A) ⇐⇒ rx < d, ce qui équivaut à l’équivalence demandée. • L’application I : Ext(A) → P [[1, k]] x → I(x) est injective. En effet, si J est une partie donnée de [[1, k]], si x ∈ Ext(A) vérifie I(x) = J, alors la famille de vecteurs (pi)i∈J est de rang d, et on a pi · x = bi pour tout i ∈ J ce qui veut dire que les coordonnées de x dans IRd sont solutions d’un système linéaire de |J| équations à d inconnues, de rang d, et un tel système a au plus une solution. Donc J admet au plus un antécédent par l’application I. On en déduit que Ext(A) ≤ P [[1, k]] = 2k. Cas d’un convexe fermé borné 13. Si p = 0, alors K0 = K et tout est évident. Sinon, utilisons les notions de la question 7. Comme l’application x → p · x est continue sur le fermé borné K, elle y est bornée et atteint ses bornes, donc σK(p) = max x∈K (p · x) < +∞ . Donc Kp = x ∈ K | p · x = min y∈K(p · y) = x ∈ K | (−p) · x = σK(−p) est non vide, et si on choisit x0 ∈ Kp, alors Kp est l’intersection de l’hyperplan affine {x ∈ IRd | p · x = p · x0}, qui est fermé et convexe, et de l’ensemble K, lui aussi fermé et convexe. Donc Kp est fermé et convexe. Notons mp = min x∈K(p · x) = −σK(−p). Si x ∈ Ext(Kp), alors x ∈ Kp ⊂ K et, si x = (1 − λ)y + λz avec y ∈ K, z ∈ K et λ ∈ ]0, 1[, alors p · x = mp = (1 − λ) p · y + λ p · z. Les réels p · y et p · z appartiennent au convexe [mp, +∞[ de IR dont mp est clairement un point extrémal, il en résulte que p · y = p · z = mp donc y ∈ Kp et z ∈ Kp. Enfin, x étant extrémal dans Kp, on déduit y = z = x, ce qui montre que x est aussi extrémal dans K. On a donc l’inclusion Ext(Kp) ⊂ Ext(K). 13 bis. Pour préparer les questions 14. et 15., voici un lemme utilisant les notations du préliminaire (“question 0.”)... et un peu de géométrie affine! Lemme 3. Si K est un convexe fermé borné de dimension k > 0 de IRd, si p est un vecteur non nul de VK, alors dim(Kp) < k. Preuve. Soit a un point de K, on a alors K ⊂ a + VK. Pour tout réel C, l’ensemble HC = {x ∈ VK | p · x = C} est un hyperplan affine de VK donc est de dimension k − 1. Par ailleurs, Kp = {x ∈ K | p · x = mp} ⊂ {x ∈ a + VK | p · x = mp} = a + {y ∈ VK | p · y = mp − p · a} , donc Kp est inclus dans un ensemble de la forme a + HC qui est un sous-espace affine de IRd de dimension k − 1, donc dim(Kp) ≤ k − 1. 14. Raisonnons par récurrence forte sur k = dim(K) = dim(VK). Pour k = 0, alors K = {a} est un singleton et Ext(K) = {a} ̸= ∅. Soit k > 0, supposons Ext(L) ̸= ∅ pour tout convexe fermé borné L non vide de dimension strictement inférieure à k, soit K un convexe fermé borné de dimension k. D’après le lemme 3 ci-dessus et la question 13, si p est un vecteur non nul de VK, alors Kp est un convexe fermé borné non vide de dimension strictement inférieure à k, on peut donc lui appliquer l’hypothèse de récurrence et Ext(Kp) ̸= ∅. Enfin Ext(Kp) ⊂ Ext(K) d’après 13., donc Ext(K) ̸= ∅. 15. L’ensemble K est un convexe contenant Ext(K), il contient donc co Ext(K) d’après 10. Pour l’inclusion inverse, c’est de nouveau une récurrence forte sur la dimension k de K. On pourrait commencer par prouver que, pour toute partie E de IRd, co co(E) = co(E), mais passons plutˆot à la suite... Si dim(K) = 0, alors K est un singleton et c’est évident. Soit k > 0, supposons la propriété vraie pour tout convexe fermé borné non vide de dimension strictement inférieure à k, soit K un convexe fermé borné de dimension k dans IRd. Soit x ∈ K, soit K′ = K − x, alors K′ ⊂ VK avec VK s.e.v. de IRd de dimension k. On a maintenant 0 ∈ K′ et K′ est un convexe fermé borné de dimen- sion k dans VK (que l’on peut identifier à IRk). Si D est une droite vectorielle de VK (contenant donc 0), son intersection avec K′ est un convexe fermé borné de D, c’est donc un segment [A, B] contenant 0, les points extrémités A et B de ce segment étant sur la frontière de K′ (pour la topologie induite sur VK ≃ IRk). D’après la question 8 bis et en travaillant maintenant dans VK, il existe dans VK un hyperplan affine HA passant par A et tel que K′ soit inclus dans l’un des demi-espaces fermés délimités par cet hyperplan. On en déduit que A ∈ K′ p ou p est un certain vecteur non nul de VK. Comme dim(K′ p) < k d’après le lemme 3, l’hypothèse de récurrence s’applique et A ∈ co Ext(K′ p) . Or, par la question 13., Ext(K′ p) ⊂ Ext(K′), donc A ∈ co Ext(K′) . De mˆeme, B ∈ co Ext(K′) . Enfin, le point 0 appartient au segment [A, B], donc 0 ∈ co co Ext(K′) = co Ext(K′) . En translatant le tout du vecteur x, on obtient x ∈ co Ext(K) , ce que l’on voulait démontrer. On a ainsi prouvé le théorème de Krein-Milman (en se retreignant à la dimension finie). Partie III. Un résultat de dualité Cˆones convexes 16. L’ensemble E+ est clairement un cˆone. Par ailleurs, E+ = x∈E\{0} {p ∈ IRd | p · x ≥ 0} est une intersection de demi-espaces fermés, c’est donc une intersection de fermés convexes, et c’est encore un fermé convexe. Ce qui précède s’applique à E++ = (E+)+. Si x ∈ E, alors pour tout p ∈ E+, on a p · x ≥ 0, donc x ∈ E++. Ainsi, E ⊂ E++. 17. Si E = E++, alors E est un cˆone convexe fermé d’après la question précédente. Réciproquement, soit E un cˆone convexe fermé non vide ; d’après Q16., il suffit de montrer que E++ ⊂ E. Procédons par contraposition. Soit ξ ∈ IRd tel que ξ ̸∈ E. Pour montrer que ξ ̸∈ E++, il faut construire un vecteur p ∈ IRd tel que p ∈ E+ (i.e. tel que ∀x ∈ E p·x ≥ 0) mais tel que p·ξ < 0. Comme E est convexe fermé non vide, on peut considérer le point x0 = projE(ξ) et poser p = x0 − ξ. Comme ξ ̸∈ E, on a x0 ̸= ξ donc p ̸= 0. Comme x0 ∈ E et que E est un cˆone, on a λx0 ∈ E pour tout λ ≥ 0. De Q2., on déduit ∀λ ∈ IR+ (ξ − x0) · (λx0 − x0) ≤ 0 , soit ∀λ ∈ IR+ (1 − λ) p · x0 ≤ 0 , il en résulte que p · x0 = 0, puis que p · ξ = p · x0 + p · (ξ − x0) = −∥p∥2 < 0. Enfin, si x ∈ E, on a p · x = p · (x − x0) + p · x0 = −(ξ − x0) · (x − x0) ≥ 0 toujours d’après Q2. et car p · x0 = 0, donc p ∈ E+. Ceci prouve l’inclusion E++ ⊂ E et termine la démonstration de l’équivalence E = E++ ⇐⇒ E est un cˆone convexe fermé. 18. Le fait que F est un cˆone et qu’il est convexe sont des formalités. Le fait que F est fermé ne me semble pas du tout ˆetre une formalité, si je ne m’abuse c’est plus ou moins le théorème de Carathéodory (tout ceci est-il bien raisonnable en PSI ?), je renvoie le lecteur à l’annexe 2. On a donc F = F ++ d’après Q17. Or, il est facile de vérifier que F + = x ∈ IRd | ∀i ∈ [[1, k]] ξi · x ≥ 0 . Donc ξ ∈ F ⇐⇒ ξ ∈ F ++ = (F +)+, ce qui est exactement l’équivalence demandée. Programmation linéaire 19. Introduisons des notations: soient les ensembles A = x ∈ IRd | x ≥ 0 , Mx ≤ b et B = q ∈ IRk | q ≤ 0 , M T q ≤ p . Soient x ∈ A et q ∈ B. Alors, les coordonnées du vecteur x étant positives, de p ≥ M T q, on déduit p · x ≥ (M T q) · x. D’autre part, (M T q) · x = (M T q)T x = qT Mx = q · (Mx). Enfin, les coordonnées du vecteur q étant négatives, de Mx ≤ b, on déduit q · (Mx) ≥ q · b. Enchaˆınons tout cela: ∀x ∈ A ∀q ∈ B p · x ≥ (M T q) · x = q · (Mx) ≥ q · b = b · q . Donc inf x∈A(p · x) ≥ sup q∈B (b · q), soit α ≥ β. 20.a. Soit z ∈ IRd tel que zj ≥ 0 pour tout j ∈ J et Mi · z ≤ 0 pour tout i ∈ I. Pour ε > 0 assez petit, on a x + εz ∈ A (notation introduite dans le corrigé de la question précédente). En effet, pour tout j ∈ [[1, d]], (x + εz)j = xj + ε zj donc, - si j ∈ J, alors (x + εz)j = ε zj ≥ 0 de fa¸con évidente ; - si j ̸∈ J, alors xj > 0 donc xj + ε zj reste positif pour ε > 0 petit. On montre de mˆeme que, si ε > 0 est petit, alors Mi · (x + εz) ≤ bi pour tout i ∈ [[1, k]], en distinguant les cas i ∈ I et i ̸∈ I. Pour ε > 0 petit, on a donc x + εz ≥ 0 et M(x + εz) ≤ b, donc x + εz ∈ A, ce qui entraˆıne que p · (x + εz) ≥ α = p · x, donc p · z ≥ 0. b. Utilisons les questions 17. et 18. Soit (e1, · · · , ed) la base canonique de IRd. Notons F le cˆone engendré par les vecteurs ej (j ∈ J) et les vecteurs −Mi (i ∈ I), à savoir F = j∈J λjej − i∈I µiMi ; les λj et les µi positifs ou nuls . Alors F est un cˆone convexe fermé donc F = F ++. Or, on vient de prouver dans le a. ci-dessus que p ∈ F ++. Donc p ∈ F, autrement dit il existe des réels positifs λj (j ∈ J) et µi (i ∈ I) tels que p = j∈J λjej − i∈I µiMi. Soit maintenant q = (q1, · · · , qk) ∈ IRk, avec qi = −µi si i ∈ I 0 si i ∈ [[1, k]] \ I . On a clairement q ≤ 0. Notons (ε1, · · · , εk) la base canonique de IRk. Alors q = − i∈I µiεi, et M T q = − i∈I µi M T εi = − i∈I µiMi , donc p − M T q = j∈J λjej ≥ 0 donc M T q ≤ p. On vient de montrer que q ∈ B (notation introduite dans le corrigé de la question 19.). Ensuite, q · (Mx − b) = k i=1 qi (Mi · x − bi) = 0 car chaque terme de la somme est nul (distinguer les cas i ∈ I et i ̸∈ I). Enfin, (p − M T q) · x = j∈J λjej · x = j∈J λjxj = 0 puisque les xj sont nuls pour j ∈ J. c. De la relation q · (Mx − b) = 0, on tire, en utilisant aussi (p − M T q) · x = 0, b · q = q · b = q · (Mx) = qT Mx = (M T q)T x = (M T q) · x = p · x = α . On a noté ci-dessus que q ∈ B. Enfin, de Q19., on déduit que b · q = α ≥ β = sup q∈B (b · q). On a donc nécessairement b · q = max q∈B (b · q) = β. Partie IV. Systèmes linéaires sous-déterminés 21. • Si x = (x1, · · · , xd) ∈ IRd, et si y = (y1, · · · , yd) ∈ IRd vérifie ∥y∥∞ ≤ 1, alors x · y = d i=1 xiyi ≤ d i=1 xiyi ≤ d i=1 |xi| |yi| ≤ ∥y∥∞ d i=1 |xi| ≤ ∥x∥1 , donc ∥x∥1 est un majorant du premier ensemble considéré. Enfin, si on choisit y tel que yi = |xi| xi si xi ̸= 0 0 si xi = 0 , alors ∥y∥∞ ≤ 1 et x · y = i̸∈I0(x) |xi| = d i=1 |xi| = ∥x∥1. Ceci prouve que ∥x∥1 = max x · y ; y ∈ IRd , ∥y∥∞ ≤ 1 . • Si maintenant ∥y∥1 ≤ 1, alors x·y ≤ d i=1 |xi||yi| ≤ ∥x∥∞ d i=1 |yi| ≤ ∥x∥∞. Et, si i0 ∈ [[1, d]] est un indice tel que |xi0| = ∥x∥∞, en choisissant y = |xi0| xi0 ei0 (vecteur de la base canonique de IRd) (si le vecteur x est non nul!), on a ∥y∥1 = 1 et x · y = |xi0| = ∥x∥∞. Finalement, ∥x∥∞ = max x · y ; y ∈ IRd , ∥y∥1 ≤ 1 . 22. La matrice M ∈ Mk,d(IR) est supposée de rang k, donc l’application linéaire de IRd vers IRk qui lui est canoniquement associée est surjective, ainsi l’ensemble E = {x ∈ IRd | Mx = b} est non vide. Cet ensemble E est fermé car x → Mx est continue. L’ensemble C′ = x ∈ IRd | Mx = b , ∥x∥1 ≤ r + 1 est alors non vide par définition de r, il est fermé car c’est l’intersection de E avec une boule fermée, et il est évidemment borné. L’application continue x → ∥x∥1 admet donc un minimum sur C′ et min x∈C′ ∥x∥1 = min x∈E ∥x∥1 = inf x∈E ∥x∥1 = r , ce qui prouve que C est non vide (la borne inférieure r est atteinte). L’ensemble C = x ∈ IRd | Mx = b , ∥x∥1 = r est fermé puisque c’est l’intersection de deux fermés (l’ensemble E et une sphère), il est clairement borné. Soient x ∈ C, y ∈ C, λ ∈ [0, 1], posons z = λx + (1 − λ)y, alors clairement Mz = b, puis ∥z∥1 = λx + (1 − λ)y 1 ≤ λ∥x∥1 + (1 − λ)∥y∥1 = λr + (1 − λ)r = r , mais comme r = min z∈E ∥z∥1, cela entraˆıne ∥z∥1 = r, donc z ∈ C. L’ensemble C est donc convexe. 23. Hum! Y a-t-il un spécialiste d’analyse convexe dans l’avion ? Si oui, je pense qu’il résoudra cette question en deux minutes, en utilisant la question 21. et en s’inspirant probablement de la partie “programmation linéaire”, peut-ˆetre en parlant de “certificat dual” ou de ce genre de choses que j’avoue humblement ignorer malgré un très (trop) rapide survol de quelques articles sur le sujet. Je me contente donc modestement d’une solution très partielle que j’ai bidouillée dans le cas ou I0(x) = ∅. Si I0(x) = ∅, on n’a pas trop de choix, on doit prendre (à un facteur strictement positif près) le vecteur q tel que, pour tout i ∈ [[1, d]], on ait qi = sgn(xi) = |xi| xi . On a alors ∥q∥∞ = 1 et la relation qi xi = ∥q∥∞ |xi| est satisfaite pour tout i ∈ [[1, d]]. Notons que q · x = ∥x∥1 = r. Par ailleurs, si h ∈ Ker(M), alors pour tout t réel, on a M(x + th) = Mx = b, ce qui entraˆıne ∥x + th∥1 ≥ r. Or, ∥x + th∥1 = d i=1 |xi + thi| = d i=1 sgn(xi + thi) × (xi + thi) = d i=1 sgn(xi) × (xi + thi) pour |t| assez petit = q · (x + th) = r + t q · h . Pour que cette expression reste minorée par r lorsque le réel t décrit un intervalle [−δ, δ] avec δ > 0, il est nécessaire que q · h soit nul. On a donc montré ainsi que q ∈ (Ker M)⊥. 24. Pour traiter cette question et la suivante, choisissons q tel que ∥q∥∞ = 1, ce qui ne change rien. Dans ce cas, on a qi = sgn(xi) ∈ {−1, 1} pour tout i ∈ [[1, d]] \ I0(x), et q · x = r. On a facilement x ∈ K,donc K ̸= ∅. Si y ∈ K, alors My = b et ∥y∥1 = d i=1 |yi| = i∈[[1,d]]\I0(x) |yi| = i∈[[1,d]]\I0(x) sgn(yi) yi = q · y puisque, si yi est non nul, les réels qi et yi sont de mˆeme signe et qi = ±1 = sgn(yi). Enfin, ∥y∥1 = q · y = q · x + q · (y − x) = q · x = r puisque My = Mx = b donc y−x ∈ Ker(M). Donc y ∈ C, ce qui prouve l’inclusion K ⊂ C. Il est clair aussi que l’ensemble K est convexe. 25. Soit y ∈ Ext(K). Soit h ∈ Ker(M) tel que I0(y) ⊂ I0(h). Raisonnons par l’absurde en supposant que h ̸= 0, alors I0(h) ̸= [[1, d]]. Pour tout indice i ∈ [[1, d]] tel que i ̸∈ I0(h), on a a fortiori i ̸∈ I0(y) et, a fortiori encore puisque y ∈ K, i ̸∈ I0(x). Donc qi = sgn(xi) ∈ {−1, 1}. Comme qiyi ≥ 0 puisque y ∈ K, avec yi ̸= 0, on a encore qi(yi + thi) ≥ 0 pour t réel suffisamment proche de 0, disons si |t| ≤ δi avec δi > 0. Soit δ = min i∈[[1,d]]\I0(h) δi, alors δ > 0 et, pour t ∈ [−δ, δ], on a bien sˆur M(y + th) = My = b, on a yi + thi = 0 pour tout i ∈ I0(x), et enfin qi(yi + thi) ≥ 0 pour tout i ∈ [[1, d]]. Le segment [y − δh, y + δh] est inclus dans K, ce qui contredit l’hypothèse que y est un point extrémal du convexe K. 26. Il s’agit de montrer que I0(y) ≥ d − k. Notons alors l ce cardinal. Pour simplifier, sup- posons que I0(y) = [[1, l]], ce qui ne change rien au raisonnement qui suit. La question 25. nous dit qu’un vecteur de Ker(M) dont les l premières coordonnées sont nulles est nécessaire- ment le vecteur nul, ce qui se formalise en écrivant que Ker(M) ∩ Vect(el+1, · · · , ed) = {0}. Comme Ker(M)⊕Vect(el+1, · · · , ed) ⊂ IRd, on déduit que (d−k)+(d−l) ≤ d, soit l ≥ d−k, ce qu’il fallait démontrer. ANNEXE 1: DÉMONSTRATION du LEMME 2 Rappel de l’énoncé du lemme 2: Si A est un convexe de IRd, alors ◦ A = ◦ A. Pour le prouver, nous utiliserons trois “sous-lemmes”: Sous-lemme 2.1.: Si A est un convexe de IRd, si x ∈ ◦ A et y ∈ A, alors [x, y[⊂ A. Preuve. Le lecteur est invité à faire un dessin, à représenter des boules et imaginer des homothéties. Nous supposerons y ̸= x, sinon il n’y a rien à démontrer. Comme x ∈ ◦ A, il existe r > 0 tel que la boule B = B(x, r) soit incluse dans A. Soit alors z ∈ ]x, y[, i.e. z = tx + (1 − t)y avec t ∈ ]0, 1[. On a alors x = 1 t z + 1 − 1 t y, ce qui signifie que x = h(y), ou h est l’homothétie de centre z et de rapport −1 − t t . Posons r = t 1 − t r, alors la boule B′ = B(y, r′) vérifie h(B′) = B. Comme y ∈ A, cette boule B′ contient au moins un point y1 qui est dans A. Alors x1 = h(y1) ∈ B, donc x1 ∈ A. La relation x1 = h(y1) s’écrit aussi z = tx1 + (1 − t)y1, on a donc z ∈ [x1, y1] donc z ∈ A puisque A est un convexe contenant x1 et y1. On a bien montré que [x, y[⊂ A. Remarque. En modifiant un peu la preuve, on peut montrer avec les mˆemes hypothèses l’inclusion meilleure [x, y[⊂ ◦ A, c’est le “lemme d’intériorité” selon Wikipédia. Sous-lemme 2.2. Soit A un convexe de IRd. Alors ◦ A = ∅ ⇐⇒ dim(A) < d. Preuve. • Si dim(A) = k < d, alors A est inclus dans un sous-espace affine F de dimension k, or ◦ F = ∅ donc a fortiori ◦ A = ∅. • Si dim(A) = d, soit a ∈ A, il existe alors dans A−a une famille (e1, · · · , ed) de d vecteurs linéairement indépendants. Le convexe A contient alors toutes les “combinaisons convexes” λ0a + λ1(a + e1) + · · · + λd(a + ed) = a + d i=1 λiei ou les λi, 0 ≤ i ≤ d, sont des réels positifs de somme 1, et qui constituent un “simplexe” d’intérieur non vide. Donc a fortiori ◦ A ̸= ∅. Sous-lemme 2.3. Soit A un convexe de IRd. Alors ◦ A = ∅ ⇐⇒ ◦ A = ∅. Preuve. Comme A ⊂ A, alors ◦ A ⊂ ◦ A, l’implication indirecte est donc évidente. Si ◦ A = ∅, on déduit du sous-lemme 2.2. que dim(A) = k < d, donc A est contenu dans un sous-espace affine F de dimension k. Comme F est fermé dans IRd, on a aussi A ⊂ F (puisque A est le plus petit fermé contenant A). Donc dim(A) ≤ k, et on déduit de nouveau du sous-lemme 2.2. que ◦ A = ∅. Démonstration du lemme 2. L’inclusion ◦ A ⊂ ◦ A est immédiate. Pour l’inclusion inverse, deux cas se présentent: - si ◦ A = ∅, alors ◦ A = ∅ d’après le sous-lemme 2.3. d’ou l’égalité. - supposons maintenant ◦ A ̸= ∅, soit x ∈ ◦ A. Soit d’autre part un point v dans ◦ A. Comme x est intérieur à A, pour ε > 0 assez petit, le point u = x + ε(x − v) appartient à A. Par le lemme 2.1., on a [u, v[⊂ A. Or, x = 1 1 + εu + ε 1 + εv donc x ∈ [u, v[ et donc x ∈ A. On a donc obtenu l’inclusion ◦ A ⊂ A. Comme ◦ A est un ouvert et que ◦ A est le plus grand ouvert inclus dans A, on déduit enfin que ◦ A ⊂ ◦ A. ANNEXE 2: CARACTÈRE FERMÉ D’UN CˆONE FINIMENT ENGENDRÉ Si X = (x1, · · · , xk) est une famille finie de vecteurs de IRd, nous noterons C(X) le cˆone convexe engendré par X, à savoir C(X) = k i=1 λixi ; (λ1, · · · , λk) ∈ IRk + . L’objectif de cet annexe est de montrer le caractère fermé de C(X). • Notons d’abord que ceci est facile si X est libre. Notons en effet V = Vect(X), c’est un s.e.v. de IRd de dimension k dont X est une base. Si x = k i=1 λixi ∈ C(X), alors les λi sont déterminés de fa¸con unique, ce sont les coordonnées du vecteur x de V dans la base B. Le s.e.v. V étant fermé dans IRd, et la convergence d’une suite de vecteurs d’un e.v. de dimension finie pouvant s’étudier coordonnée par coordonnée, il est immédiat que toute suite convergente d’éléments de C(X) a sa limite dans C(X), donc C(X) est fermé. • Montrons maintenant que, si X est liée, alors pour tout vecteur x ∈ C(X), il existe une sous-famille stricte X ′ de X telle que x ∈ C(X ′). Preuve. Soit x = k i=1 λixi avec les λi positifs ou nuls. Si l’un au moins des λi est nul, c’est immédiat, il suffit de retirer de X le xi correspondant. Sinon, soient α1, · · ·, αk des réels non tous nuls tels que k i=1 αixi = 0. Quitte à remplacer tous les αi par leurs opposés, on peut supposer qu’au moins un des αi est strictement négatif. Posons I = i ∈ [[1, k]] | αi < 0 . Soit β = min i∈I λi −αi , alors β > 0, ce minimum est atteint pour un certain indice i0 ∈ I, on a alors λi0 + β αi0 = 0 et, pour tout i ∈ [[1, k]], on a λi + β αi ≥ 0. Enfin, x = k i=1 λixi = k i=1 λixi + β k i=1 αixi = k i=1 (λi + β αi)xi ∈ C(X ′) avec X ′ = (xi)i∈[[1,k]]\{i0} sous-famille stricte de X. • On déduit de cela que, si x ∈ C(X), alors il existe une famille libre X ′ extraite de X telle que x ∈ C(X ′). Il suffit en effet de considérer une sous-famille X ′ de cardinal minimal extraite de X telle que x ∈ C(X ′). On a donc C(X) = X ′⊂X , X ′ libre C(X ′), ainsi C(X) est une réunion finie de fermés, c’est une partie fermée de IRd.