\documentclass[11pt]{article}

% Packages

% Packages langues et encodage
\usepackage[frenchb]{babel}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{csquotes}

% Packages maths
\usepackage{amsfonts}
\usepackage{mathtools}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage[g]{esvect}
\usepackage[mathscr]{eucal}
\usepackage{stmaryrd}
\usepackage[all]{xy}

% Packages mise en page
\usepackage{fancyhdr}
\usepackage[top=3cm, left=3cm, right=3cm, bottom=2cm]{geometry}
\usepackage[pdftex,pdfborder={0 0 0}]{hyperref}

% Packages graphiques
\usepackage{pgf,tikz}
\usetikzlibrary{arrows}

% Packages autres
\usepackage{color}
\usepackage{enumerate}
\usepackage{multicol}
\usepackage{pdfpages}
\usepackage{soul}


% Definition des environnements
\theoremstyle{plain}
	\newtheorem*{thm}{Théorème}
	\newtheorem*{cor}{Corollaire}
	\newtheorem*{lem}{Lemme}
	\newtheorem*{prop}{Proposition}

\theoremstyle{definition}
	\newtheorem*{dfn}{Définition}
	\newtheorem*{ntn}{Notation}
	\newtheorem*{dfns}{Définitions}
	\newtheorem*{ntns}{Notations}
	\newtheorem*{rem}{Remarque}
	\newtheorem*{rems}{Remarques}
	\newtheorem*{ex}{Exemple}
	\newtheorem*{cex}{Contre-exemple}
	\newtheorem*{exs}{Exemples}
	\newtheorem*{cexs}{Contre-exemples}
	\newtheorem{exo}{Exercice}


% Definiition des commandes
\newcommand{\B}{\mathbb{B}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\E}{\mathcal{E}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\K}{\mathbb{K}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\T}{\mathbb{T}}
\newcommand{\Z}{\mathbb{Z}}

\renewcommand{\H}{\mathbb{H}}
\renewcommand{\P}{\mathbb{P}}
\renewcommand{\S}{\mathbb{S}}

\newcommand{\acts}{\curvearrowright}
\newcommand{\dx}{\dmesure\!}
\newcommand{\deron}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\derond}[2]{\frac{\partial^2 #1}{\partial #2 ^2}}
\newcommand{\deronc}[3]{\frac{\partial^2 #1}{\partial #2 \partial #3}}
\newcommand{\grad}{\vv{\gradient}}
\newcommand{\lint}{\llbracket}
\newcommand{\rint}{\rrbracket}
\newcommand{\leqclosed}{\trianglelefteqslant}
\newcommand{\mvert}{\mathrel{}\middle|\mathrel{}}
\newcommand{\norm}[1]{\left\lvert #1 \right\rvert}
\newcommand{\Norm}[1]{\left\lVert #1 \right\rVert}
\newcommand{\prsc}[2]{\left\langle #1\,, #2 \right\rangle}

\renewcommand{\bar}{\overline}
\renewcommand{\epsilon}{\varepsilon}
\renewcommand{\geq}{\geqslant}
\renewcommand{\leq}{\leqslant}
\renewcommand{\tilde}{\widetilde}
\renewcommand{\triangleleft}{\vartriangleleft}

\renewcommand{\FrenchLabelItem}{\textbullet}


% Definition des operateurs
\DeclareMathOperator{\aff}{Aff}
\DeclareMathOperator{\aut}{Aut}
\DeclareMathOperator{\bij}{Bij}
\DeclareMathOperator{\car}{car}
\DeclareMathOperator{\conv}{Conv}
\DeclareMathOperator{\dmesure}{d}
\DeclareMathOperator{\End}{End}
\DeclareMathOperator{\fix}{Fix}
\DeclareMathOperator{\id}{id}
\DeclareMathOperator{\Id}{Id}
\DeclareMathOperator{\im}{Im}
\DeclareMathOperator{\isom}{Isom}
\DeclareMathOperator{\rk}{rg}
\DeclareMathOperator{\stab}{Stab}
\DeclareMathOperator{\Sim}{Sim}
\DeclareMathOperator{\tr}{Tr}
\DeclareMathOperator{\vect}{Vect}

\setlength{\parindent}{0pt}
\setlength{\parskip}{5pt}
\setlength{\headsep}{10pt}
\setlength{\headheight}{16pt}

\renewcommand{\headrulewidth}{0.5pt}
\renewcommand{\footrulewidth}{0pt}

\begin{document}

\thispagestyle{fancy}
\lhead{Préparation à l'agrégation 2017 -- 2018}
\rhead{ENS de Lyon}
\begin{center}
\Large{Séparation, points extrémaux}
\end{center}
\vspace{-7mm}
\rule{\linewidth}{0.5pt}


\begin{exo}
Soient $\mathcal{A}$ et $\mathcal{B}$ deux convexes  disjoints d'un $\R$-espace affine de dimension finie.
\begin{enumerate}
\item Si $B$ est d'intérieur non vide, montrer qu'il existe un hyperplan affine qui sépare $\mathcal{A}$ et $\mathcal{B}$.
\item Montrer qu'on peut se passer d'hypothèse sur $\mathcal{B}$, en se ramenant à la question précédente.
\end{enumerate}
\end{exo}

\begin{exo}[Séparation, Berger T.~3 sect.~11.4]
Soient $\mathcal{A}$ et $\mathcal{B}$ deux convexes disjoints dans un $\R$-espace vectoriel de dimension finie. Montrer les résultats de séparation suivants.
\begin{enumerate}
\item Si $A$ et $B$ sont ouverts, alors il existe un hyperplan qui les séparent strictement.
\item Si $A$ est fermé et $B$ est compact, alors il existe un hyperplan qui les séparent strictement.
\end{enumerate}
\end{exo}

\begin{exo}[Convexes fermés, Berger T.~3 sect.~11.5]
Montrer qu'un convexe fermé dans un $\R$-espace affine de dimension finie est l'intersection des demi-espaces fermés qui le contiennent.
\end{exo}

\begin{exo}[Lemme de Farkas, Matou\v{s}ek sect.~1.2]
Soit $M \in \mathcal{M}_{np}(\R)$, montrer qu'une et une seule des possibilités suivantes est vérifiée.
\begin{enumerate}
\item Il existe $x \in \R^p \setminus \{0\}$ dont les composantes sont positives ou nulles et tel que $Mx=0$.
\item Il existe $y \in \R^n$ tel que toutes les composantes de $(y^\text{t}) M=0$ soient strictement négatives.
\end{enumerate}
\end{exo}

\begin{exo}[Enveloppe convexe du groupe orthogonal, FGN alg.~1 pp.~329--330, Queffélec--Zuily pp.~206--207]
On munit $\mathcal{M}_n(\R)$ de la norme d'opérateur subordonnée à la norme euclidienne de $\R^n$. Pour tout $M \in \mathcal{M}_n(\R)$, on note $\varphi_M : A \mapsto \tr(AM)$.
\begin{enumerate}
\item Montrer que $M \mapsto \varphi_M$ est un isomorphisme de $\mathcal{M}_n(\R)$ vers son dual.
\item Montrer que $\conv\!\left(O_n(\R)\!\right)$ est un compact inclus dans $\B$, la boule unité fermée de $\mathcal{M}_n(\R)$.
\item Montrer que pour tout $\varphi \in (\mathcal{M}_n(\R))^*$, $\displaystyle\max_{A \in \conv(O_n(\R))} \varphi(A) = \max_{A \in O_n(\R)} \varphi(A)$.
\item Montrer que pour tout $\varphi \in (\mathcal{M}_n(\R))^*$ et tout $M \in \B$, $\varphi(M) \leq \displaystyle\max_{A \in O_n(\R)} \varphi(A)$.\\
(\emph{Indication:} écrire $\varphi$ comme $\varphi_A$ et utiliser la décomposition polaire de $A$)
\item Conclure que $\conv(O_n(\R)) = \B$.
\end{enumerate}
\end{exo}

\begin{exo}[Point extrémal]
Soient $\mathcal{C}$ un convexe d'un $\R$-espace affine et $M \in \mathcal{C}$.
\begin{enumerate}
\item Montrer que $M$ est extrémal si et seulement si $\mathcal{C} \setminus \{M\}$ est convexe.
\item Montrer que $M$ est extrémal si et seulement si pour tout $A,B \in \mathcal{C}$, $M \notin \ ]AB[$.
\end{enumerate}
\end{exo}

\begin{exo}[Existence d'un point extrémal, Barvinok p.~53]
Soit $\mathcal{C}$ un convexe d'un $\R$-espace affine de dimension finie ne contenant pas de droite. Montrer que $\mathcal{C}$ possède un point extrémal.
\end{exo}

\begin{exo}[Théorème de Birkhoff--von Neumann, Barvinok sect.~II.5]
Soit $\sigma \in \mathfrak{S}_n$, on note $M_\sigma \in \mathcal{M}_n(\R)$ la matrice dont les coefficients $(m_{ij})$ vérifient $m_{ij} = 1$ si $j = \sigma(i)$ et $m_{ij}=0$ sinon. Les $(M_\sigma)_{\sigma \in \mathfrak{S}_n}$ sont appelées \emph{matrices de permutations}.

On appelle matrice \emph{bi-stochastique} une matrice $M \in \mathcal{M}_n(\R)$ à coefficients positifs telle que la somme des coefficients de chaque ligne et de chaque colonne soit égale à $1$.
\begin{enumerate}
\item Vérifier que les matrices de permutation sont bi-stochastiques.
\item Montrer que l'ensemble $\mathcal{B}$ des matrices bi-stochastiques est un convexe.
\item Montrer que $\mathcal{B}= \conv\left(\left\{M_\sigma \mvert \sigma \in \mathfrak{S}_n\right\}\right)$.
\end{enumerate}
\emph{Remarque:} une application de ce résultat est de démontrer le théorème de Schur sur les matrices symétriques, voir Barvinok p.~60.
\end{exo}

\end{document}