AnnalesÉcoles d'ingénieurs

X-ENS PSI 2022 — Maths

Convexité, points extrémaux, dualité et systèmes linéaires sous-déterminés · 8 pages

Le sujet établit l'existence et les propriétés de la projection sur un convexe fermé de $\mathbb{R}^d$ , puis la séparation stricte d'un convexe compact et d'un convexe fermé disjoints. Il étudie les points extrémaux (cas des polyèdres, existence pour un convexe compact, qui est l'enveloppe convexe de ses points extrémaux), les cônes polaires et le lemme de Farkas, d'où la dualité de la programmation linéaire. Il montre enfin qu'un système linéaire sous-déterminé $Mx = b$ de rang $k$ admet une solution de norme 1 minimale ayant au plus $k$ coordonnées non nulles.

Le sujet, partie par partie

Notations et Partie I — Projection et séparation p. 2–4

Ensembles convexes · Projection orthogonale et moindres carrés · Compacité · Continuité · Espaces préhilbertiens et euclidiens — projection sur un convexe fermé, caractérisation angulaire, séparation stricte, demi-espaces, fonction d'appui

Partie II — Points extrémaux p. 4–5

Ensembles convexes · Polytopes et géométrie combinatoire · Compacité · Applications linéaires et rang — point extrémal, enveloppe convexe, polyèdre, théorème de Krein-Milman, convexe compact, rang

Partie III — Cônes convexes et programmation linéaire p. 5–7

Ensembles convexes · Extrema et optimisation · Dualité · Calcul matriciel — cône polaire, cône bi-polaire, lemme de Farkas, programmation linéaire, dualité, relations d'exclusion

Partie IV — Systèmes linéaires sous-déterminés p. 7–8

Extrema et optimisation · Ensembles convexes · Espaces vectoriels normés · Applications linéaires et rang · Compacité — norme 1, norme infinie, système sous-déterminé, solution parcimonieuse, minimisation, points extrémaux

Dans l'édifice

Théorème de Hahn-Banach Espaces de Hilbert et théorème de projection Compacité Continuité Théorème des valeurs intermédiaires Théorème de Heine Théorème de représentation de Riesz Division euclidienne Applications linéaires Théorème du rang Applications différentiables Espace dual Matrices d'une application linéaire Espaces vectoriels normés et espaces de Banach Normes en dimension finie Applications linéaires continues et dual topologique