ECOLE POLYTECHNIQUE rire MP CONCOURS D'ADMISSION 2000 DEUXIEME COMPOSITION DE MATHEMATIQUES (Durée : 4 heures) utilisation des calculatrices n'est pas autorisée pour cette épreuve. On attachera la plus grande importance 4 la clarté, a la précision et & la concision de la rédaction. ee Ce probléme a pour objet étude de certains cénes dans des espaces euclidiens. On désigne par E l'espace euclidien R"(n > 1), par (.) son produit scalaire usuel, et par [| la norme associée. Pour toute partie X de E, on note X+ (resp. X+) l'ensemble des éléments x de E satisfaisant (x|y) = 0 (resp. (z|y) > 0) pour tout y de X. Une partie C de E sera appelée céne & faces s'il existe une famille finie d’éléments 4+ s6r(r > 0) do £ telle que C soit l'ensemble des combinaisons linéaires J ic; avec a Ais+++ :Ar 2 0. On supposera toujours les c; non nuls, et on dira qu’ils engendrent C. Enfin on appelle face de C toute partie de C de la forme Cn {w}+ avec w € C*. La premiére partie est indépendante des suivantes. Premiére partie 1. Verifier que tout sous-espace vectoricl non nul de E est un edne a faces. 2. Supposant n =r = 2, décrire (sans démonstration mais avec des figures) les ensembles C, C* et donner sous chaque figure la liste des faces de C suivant les diverses positions relatives de cy et c7 3. Supposant que n 3 et que (c1,2,¢3) est une base orthogonale de B, décrire sans demonstration C, C* et les faces de C.Deuxiéme partie On se propose, dans cette partie, de démontrer que tout cone & faces est fermé dans B- 4.a) Soit KC une partie compacte de B ne contenant pas 0. Montrer que l'ensemble des dlements de la forme Ar, ot A€ Ry et x € K,, est ferme dans E. b) Ce résultat subsiste-til si Yon suppose IX seulement fermé, ou si KX, compact, contient, 0 5. On considére maintenant un cOne & faces @ engendré par des éléments cy, a) Montrer que C est ferme lorsqu'il ne contient aucune droite vectorielle, [On pourra introduire l'ensemble K des éléments yo cj aver A; € Ry et oy =1) ai b) Soit V un sous-espace vectoriel de E (éventuellement réduit a 0) contenu dans C et distinct de C. On note P le projecteur orthogonal de E sur V+. Verifier que P(C) est un céne a faces contenu dans C. ) Supposant que P(C) contient une droite vectorielle, construire un sous-espace vectoriel de E contenu dans C et contenant strictement V. d) Montrer que C est fermé dans £. Troisiéme partie 6. On se propose ici de démontrer que tout céne A faces C vérifie (C+)* = C. a) Soit a un élément de B. Montrer que la fonction réelle définie sur C par e+ lle al atteint sa borne inférieure en un point unique de C. On le notera p(a). b) Déterminer le signe de (p(a) ale) lorsque ¢ € C, ainsi que la valeur de (p(a) — alp(a)).. ¢) Conclure. Quatriéme partie On soubaite maintenant démontrer que tout céne a faces est lintersection dune famille fine de demi-espaces fermés (on appelle demi-espace fermé tout sous-ensemble de E de la forme {a}* avec a € £,a #0).7, Danontrer Péquivalence d (a) le conditions suiva antes relatives A un cone & faces C : “onsespace veetoriel de H engendé par C est egal & Hs (9) Vintérieur de © est non vide, Re: On suppose dans cette question les conditions de la question 7, A faces C, satisfaites pour un cone 8) Démoutrer Véquivatence des conditions suivantes relatives a un élément a de C': (c°) © est un point frontidre de C; (8°) appartient a ime face de C distinete de C. b) Que subsisterait-il de ce résultat si l'on ne supposait pas satis question 7.7 faites les conditions de la c) Soit « un point de F 1% ‘appartenant pas AC, Construire une face F de C, distincte de C et ayant la propriété suivante + pour tout w € C¥ tel que F = CN {w}+, on a (al) <0. [On pourra considérer le segment de droite joignant « A un point zp de Vintérieur de cl. 9.a) Montrer que l'ensemble des faces d'un ene & faces est fini b) Montrer que tont cone A faces est intersection a! ‘une famille finie de demi-espaces fermés, 10. Déduire de ce qui préctde que, si C est un One a faces, il en est de meme de Ct, IEcole Polytechnique 2000 MP 2" épreny Partie 1 1. Soit F nn sons espace veetoriel non mul de Fet (1 tp) tne base de FF est Nensemble des combinaisons Tinéaires & coefficients positifs om nuls des vecteurs (uy. Up m J, done F est un eéne & faces, 2. Distingons quatte eas, selon Ia position respective dee et ey: Cas ties =an,a> 0. Cas 2: ¢1 et ep forment Cost lademi droite Rey C+ est un demi-plan, c aco C ext la droite Re}. CC ext In droite orthogo- c nuale & C passant par O. ic ot, les faces de C sont le veeteur nul et les deux demi-droites Re, ot Rey, «1 048, les soles fens de C sont lui-méme. et bien sir le vecten mil 3 (fe oe (ea Teel! Teall Cost alors le quadrant formé des veeteurs 2¢y + ee + 209 avec £0, y>Det 220. ae Dans les e Dans les ¢ fede F. ) tue ase oto Les fees de C sont les quarts de plan (> 0,y > 0.2 aque les demi-droites Bey, Rteg, R¥ey et Te vecteur nul. 0). (22 0,y=0.2 0), (2 1% 0, > 0), ainsi ie I 4 (a) Soit Ancu)aen tne suite convergente vers y, (Zn)aey étant une suite dans Ket (An)qery tne suite dans 2*. On veut montre que y appartient & L= (Xr JAE R* 2 EK}. Par compacité se K. on peut exttaie de (9), une suite (esq), Qui converge vers 2 € KO n'appar- tel 2 i existe mp tel que Yn > no. [Meinjzocai] <1 + ll tenant pas & K. 2 #0, donc il existe m tel que ¥n > ma. llzgea)l| > (rssntein)) Comverse vers y, dow Ainsi, Yn > max(m,ns 1+ lvl (4ia)), est donc une suite homnfe, on peut done en + Paoal S extraite une sous suite convergente (Aszei(a)), de limite A. Dis lors. (s; converge vers x par extraction, et (Ngrey(n)x(osiiay), converge vers Az. Par icité de fsulte que y= Az. e-siini)n mite i en 5(b) Deux contre exe jedans 1, done L est form’. ‘Toute suite convergente d’éltanenta de Za 6a it ples e = Sot = ((e.4) ER? J x > Oct 2y = 1p. K est ferme (comme sxraphe de la fonction 2+ © wu **) now bow nt que = {U)U f(x,y) © 2 fz > Det. > O} fe Done L = {(x.y) €R? {x > Det. y > 0} est distinet de L, done 1. n'eat pas feriné On wotitie aise Sot K = {([Link]?/2>0et2?+(y-1)? =I} le demi cercle de centre (0, 1) de ayo 1 de derni-phan 2 > 0. K est com pact (intersection dun eerele, compact, et d'nn demiplan fermné). On virific de méme sisément que = {0} U K {29 €R? Jz > Oct y>0} Done £ = {(x,y) @R? J 7 >t y >O} est distinct de 1, done 1 nest pas fe Soit aussi T= {0 MER / VME RHE DA = } T est. fermé borné dans 2. done est compact Soit eneore ¢ TO OR 6 est continue comme restriction &T Wu Area) oe Daves linéaire, Ainsi IC = (7) est compact dans E. ‘On suppose que C ne contient aucune droite vectorielle application Si 0 appartenait & KC, on pourrait écrire 0= J dies, avec les Ay > Ot D> A = 1. Alors par exernple pp 2 Ay serait. non nul, ce qui permettrait décrire —e, et C contiendrait la droite vectorielle Rey, ce qu ca impouribe Finalement, Keston compact ne contenant pas 0, done (Az [A> O et € K') ext ferme dapeés #2 p 2 ie r tout élément de C s’écrit sous la forme Ci, SOit Az, avec 4 Ai et ° I eC a mM y ot ii it les A, sont non tous nuls, sinon on prond 2 quelconque dans C’), de sorte que rex. Ainsi C= {Az / A> Oet.z € K} , et C est. done fermé. (b) On remarque qu'un edne & faces C' vérific clairement les deux propriétés suivantes : C+ CCC. et VAZ0, ACCC. On pose cj = P(cs) pour 1 A; / Vi 4s €B*) par double inclusion immédiate, ce qui prouve que P(C) est le cone & faces engendré par (e4,...%). Soit-s € [Link] peut éerite x = P(z}+yavee y € V (decomposition dans V4GV), d'oi P(z) = x + (~y} Or —y € V done ~y€C, d’ot P(z) EC + C d'od P(z) EC. Ainsi P(C) CC. (€) Soit 22 une droite incluse dans #(C). x est un vecteur non nul de P(C), done ilexiste y € C tel que Ply) = 2 y¢ V car z #0. Posons alors W = V+ By, W est un sous-espace vectoriel de E contenant strictement V (car y ¢ V) EC done {Ay | ¥> 0} CC. -z € P(C), donc il existe xf €C tel que P(y} On écrit y= 242, 7 = +2! avec et 2! éltments de V. ~[Link]¥ EC done ~yEC, dot {Ay / AZO} CC. [Link] ~ page 16Finalement By C et WCC. (4) Si Cne contient aucune droite vectorielle, C est fermé d’aprés 72. ~ Dans le cas contraie, soit V un sous-espace veetoril de B (non réduit & {0}). de d ces inclus ans (2. Soit Te projecteur orthogonal sur V contient aucune droite vectoriell et, Paprés 72, est un et la / on en déduit que NG ) eat formé dans B c 4. tonte application) + eV, pay tei or (lle est vraie pour tont ensern 1 que P (2) = P(y), done 3y € Cy, v] rep (een ilexiste ye C VCC, done s € C, dot 2 €C. ; Finalement, » est linéaire, done continue, et P (C) est fermé, done P~' (PP (G)) est fermé, done C est fermé dans E. Partie IIT 6. (a) Soit iC —+ Rj Gest continue (enr I-lipschitzienne), et A valeurs positives, done elle admet Sicé BY (a,b ~ all) alors ¢ (e) = lle ~ al > (0) inf jy OF COBY (2, [B= al) st ferme borné done compact et ¢ est continue sa borne inférieure snr cel ensennble est done aticinte, existe finalement 2 € C tel que d(2) = inf 6. ~ sunicité du minimum Supposons que inf = ¢ (e1) = ¢ (2) att e¢ C stant convexe (c'est enveloppe convexe des demi-droites Re), ite | 2 2fer — al]? +2 hoa — all? = llea ~ eal? +f2 Linégalce } (SE) > 6 (se tradi alors par 46(0" > lle al + 40 (a), si lez - ell? <0, et yent cy = ¢2. (b) Démontrons dabord le résultat suivant : Ye € C, (P(a)— ale ~ P(a)) >0 (E) Soit A €),1]:X2+ (1=2) P(a) €C. done Az + (1~A) P(e) —all2 IP (a) ~ al od IAC = Pa) +P (a) al? 2 ||P (a) ~ al Développons : A? le ~ P (a)|[+24 (2 — P(a) |P (a) — a) > 0. Simplifiant alors par A, et faisant tendre A vers 0*, on abtient le résultat annonet. € C, alors ¢+ P(a) € G, donc en reportant dans (B) : (P (a) ~ ale) > 0: en particulier pour (a) : (P (a) ~ alP (a) > 0. De méme, 0 € C, done en reportant dans (2) : (P (a) ~ al ~ P(a)) > 0. Finalement, (P (a) — a|P (a)) = 0. (6) ~ Soit x € GC. Par definition de C*, pour tout y € C*, (zy) > 0, ee qui — par définition de (c+)* — signiie précisiment que 2 € (C*)*. Ainsi Cc (C*)* ~ Soit « € (C#)* : alors Vy € C*, (aly) > 0, or P(a) € C, donc ¥y € C*, (P(a)|y) > 0. Drapnts 72, Veg G (P(a)~ ale) 2 0, done P(a)— ag CO, aod (Pa) ~ ala) > 0 Or [IP (a) ~ al? = (P (a) ~ alP (a) ~ (P (a) ~ —(P(a) — ala), d’oa (P (a) - ala) < 0. Finalement.(P (a) al |, Le. P (a) =a, ce qui signifie que a € C. Done (C+)* c C. [Link] - page 178 Partie IV a3 On suppose VeetC = B. W existe une base (01s... tn) de E constituée déléments de C. Soit la enorme SUD? associe A cette base Myst appartenant aC, {ra IMi > ‘} ca. Soit v= D> zum € £ tel que »( -Es) < Tr alors Vk, [24 —1| < 1, done Vk, 24 > 0, done ¥ € C. Finalement C contient la boule de centre Yo de rayon 1 pour la norme W., Les normes étant équivalentes : a dans R", te vectent Sy est intésinur A.C. - B20 = Soit intérieur & C. Ar > 0, B(2,r) CC. Soit (y,... eq) a base canonique de Ae) = det (z 4 te #4 tezy..., 24+ 4eq) est um polyndmecen de terme de plus haut degré €. 11 posséde dloue un nombre fii de racine, Won Penstemce de fy €]0, {lel que P (F9) #0, (F +ter,24tea,...,24teq) est donc une base de F constituée d’léments de C. (a) - 8’ >a! + appartient & la face GA {w}+, oft w EC. w #0 car cette face est distincte de C. (zlw) = 0, done VA <0, (2+ Awlu) = Alful? <0. Par conséquent, 2 + Aw ¢ C pour tout A <0, sone z n’appartient pas A Vintéieut de C. 2 est donc un point frontiére de C. alae Soit # € FrC. Soit $ la sphére unité de E. $M C+ est fermé borné donc compact (en effet, Ct = (]4=€2/ (zlu) > 0) eot une intersection de fermés, donc est fermé) wee Vapplication continue w ++ (zl) atteint done sa horneinfrieure sur $11 en un pont wp Soit a = (z|10). a > 0 car wy € C*. Supposons a > 0. Soit y un élément queleonque de F tel que ly ~ all < lors (se) ~ (oho) < Hee obo Seal loll $a Done Yu € CMS, (ute) > (zlw)- 2 > F. Par homogéntité, Ye EC, (ylte) > $ ell 2 0, ce qui prouve que y € (C*)*. Diaprés ln 22, y € C done C contient la boule de centze # de rayon $, ce qui est absurce puisque 2 est un point frontitre de C. Finalement, a = 0 d’oi existence de wy € C non nul tel que (z|wy) = 0. x appattient done a la face C0 {uc}, qui est distincte de C car d’aprés les conditions de Ia question ??, C n'est pas inclus dans le sous espace strict. {w)* (b) On suppose maintenant que F = VeotC est. un sous-espace vecloriel sirict de F. Ou uole Cp le cue & (c) faces C eonsidéré comme une partie de F, de sorte que Ci = {x € F / Yy €C, (zy) > 0} Si w € C*, on Perit w = wy + wn avec wy € F et wz € F. Ve €C, (elu) = (alu) dod ws € Cf, Woh CC OF + F*, eb réviproquement, don Ct = Cp + FE Une face de C s'écrit CA {w}+ = CN (Fn {w)*) = Cn (ty}+. Par conséquent, les faces de Cet de Gp sont les memes += est un point frontiére de Cp si et seulement si appar une fare de C distincte de C. ns C d’intérieur non vide, soit 29 un point intériur & C. {X€ [0.1] f Az-+(1—A)z0 € GC). 24 est intérieur & C, donc A contient un intervalle (0, A] avec A> 0.2 ¢ C done 1 ¢ A. Enifin © est fermé convexe, donc A est un segment dela forme (0, a] avec 0 0 car 20 € G, dome 0 = (1]21) = 0 (rnlz) + (1 ~ a) (1020). Ainsi (rl Si C est d'intériur vido, on se raméne au eas précédent grace & Ia question ?. 9. (a) Soit C le cone & faces engendré par eh. s¢, Soit F une face de C. Iw ¢€ C+, P=CN {Es IVied, vzo} On constate que Cy CF. ie [1.0] / (led) =0) et Co = }4. On pose J le) = Sod (ules), done ¥i € Inversement, sot 2 € Fs 2 = Sey avec lv A > 0, dot 0-= i Uy), As (whes) = 0. Bn particulier, Wig J. =O, d'oi 2 € Cy Finalement, F= Cy J ant une pattie de ensemble fini [1,1], le nombre de faces de C'est au plus égal au nombre de parties J de (1,7), soit 2°. posside done un nombre fini de faces, (U) Soieat Fi... Ry les faces de C distinctes de C. On éerit Fi = C7 (us), avec uy Ament won nul de Ct. On pose alors C= () (vi) Soit x ¢ C, alors d’aprés 2?, il existe une face F; = CA {w,}+ pour Inquelle (2]i) < 0, done x ¢ C" Soit 2 € Ci puisque uj € C*, (z|ui) 2 0, et ceci étant vrai pour tout i, = € C’ Finalement, C = €’. 10. € étant. un edne A faces, il s%crit sous la forme précédente : 7 = (] {ws}*, les uw; étant des vecteurs non sn nul. Démontronsle lemme suivant : Ay,... , Ax étant des parties de £, A:+---+Ax étant l'ensemble {21 +--+ Ze / 71 € ’ ators (5 ar} = Fat 4 1sigh En effe si AC Bon aclairement BY C At, don (STAI) C AP pour tout j, done (TAs)” ¢ ays si € [Af soit (eto 24) € An 9 Ay alone («) = S(eley2 0, done #€ (a) = Appliquons alors Ie lemme a Aj = B*w;, la demi-droite dirigée par wy. = SX Ai cot por dfntion un ee & face 1S Par conséquent, d'aprés la troisiéme partie, C* 1p tun ede & faces. [Link] - page 19