Separation des convexes

Separation des convexes

Séparation des convexes

Un exemple de séparation stricte

Étant donnés deux convexes d'un même plan ne se rencontrant pas, il est toujours possible de subdiviser le plan en deux demi-plans de sorte que chacun contienne entièrement l'un des convexes. Il en est de même en dimension 3, la séparation des convexes étant alors réalisée par un plan. Plus généralement, on peut en faire autant en dimension finie quelconque à l'aide d'un hyperplan. Sous une hypothèse convenable de compacité on peut même garantir une « séparation stricte », assurant que chacun des deux convexes reste à distance de l'hyperplan qui les sépare ; dans de bonnes conditions la séparation peut également être assurée dans certains espaces vectoriels topologiques de dimension infinie.

Un cas particulier remarquable est celui où l'un des convexes ne contient qu'un point, choisi sur la frontière de l'autre. Dans ce cas, les hyperplans séparants sont appelés hyperplans d'appui du convexe.

Sommaire

Position du problème

On se place dans un espace affine E (de dimension finie), ou dans un espace vectoriel normé sur \mathbb R.

Étant donné un hyperplan affine H de E, il existe une forme linéaire (unique à un facteur multiplicatif près) qui puisse servir d'équation à H, c'est-à-dire pour laquelle il existe un c réel tel que H=\{x\in E\,\mid\,f(x)=c\}. De plus, si H est fermé, f est continue. On pourra dès lors définir les deux « demi-espaces » limités par H comme les ensembles E_1=\{x\in E\,\mid\,f(x)\leq c\} et E_2=\{x\in E\,\mid\,f(x)\geq c\}[1].

Étant données deux parties A et B de E, on dit alors que H sépare A et B lorsque, dans la subdivision de E par H en deux demi-espaces E1 et E2, l'un des ensembles A et B est inclus dans E1 et l'autre dans E2. Dans cette définition (séparation au sens « large »), on n'interdit pas à A et à B de contenir des points de H, voire de se rencontrer l'un l'autre à condition que ce soit sur H.

Sous certaines hypothèses, on peut obtenir des résultats de séparation plus précis et conclure que A et B sont de part et d'autre de H, dans les demi-plans stricts qu'il limite. De fait, on peut parfois faire encore un peu mieux, d'où la définition technique suivante : on dit que H d'équation \{x\in E\,\mid\,f(x)=c\} sépare strictement A et B lorsqu'il existe un ε > 0 tel que l'un des ensembles A et B soit inclus dans le demi-espace E_1'=\{x\in E\,\mid\,f(x)\leq c-\epsilon\} et l'autre dans le demi-espace E_2'=\{x\in E\,\mid\,f(x)\geq c+\epsilon\}.[2].

Théorèmes de séparation au sens large

Deux jeux d'hypothèses permettent d'assurer la séparation au sens large. Le premier des théorèmes qui suit est parfois appelé « première forme géométrique du théorème de Hahn-Banach »[3].

Théorème — Soit E un espace normé, A et B deux convexes de E non vides et disjoints. On suppose A ouvert. Alors il existe un hyperplan fermé séparant A et B.

Théorème — Soit E un espace affine de dimension finie, A et B deux convexes de E non vides et disjoints. Alors il existe un hyperplan séparant A et B.

En revanche, en dimension infinie, on ne peut pas toujours construire un hyperplan fermé de séparation large : il existe un exemple de deux convexes fermés non vides et disjoints mais qui ne peuvent être séparés par un hyperplan fermé[4].

On pourra remarquer que, dans le premier théorème, le convexe ouvert est nécessairement inclus dans un demi-espace strict. En particulier lorsque A et B sont tous les deux ouverts, on a réalisé une séparation où chacun des convexes est inclus dans un des demi-espaces stricts : c'est mieux qu'une séparation large, mais moins bien qu'une séparation stricte au sens qui a été choisi dans cet article.

Principe de la démonstration

Le premier théorème ci-dessus découle assez rapidement de la version de la « forme géométrique du théorème de Hahn-Banach » donnée dans l'article Théorème de Hahn-Banach. L'idée supplémentaire nécessaire pour conclure est de considérer l'ensemble AB c'est-à-dire l'ensemble des ab, où a varie dans A et b dans B. On vérifie sans mal que c'est un convexe ouvert C. On peut alors appliquer le théorème mentionné à l'article Théorème de Hahn-Banach à ce convexe C et à L = {0}, qui fournit un hyperplan H1 ; il est alors facile de constater que parmi les hyperplans parallèles à H1 l'un répond à la question.

Théorème de séparation stricte

Ce résultat est la « deuxième forme géométrique du théorème de Hahn-Banach »[5] :

Théorème — Soit E un espace normé, A et B deux convexes de E non vides et disjoints. On suppose A fermé et B compact. Alors il existe un hyperplan fermé séparant strictement A et B.

Une application particulièrement importante en est la représentation des convexes fermés comme intersection de demi-espaces fermés. Lorsqu'on intersecte des demi-espaces fermés, le résultat de l'opération est de façon évidente un convexe fermé (puisque tant la convexité que la fermeture sont conservées par intersection, même infinie). Il se trouve que la réciproque est vraie[6] :

Corollaire — Dans un espace normé E, tout convexe fermé est l'intersection des demi-espaces fermés qui le contiennent.

Principes des démonstrations

Pour le théorème, on remarque dans un premier temps que la distance d qui sépare A et B est strictement positive (c'est toujours le cas pour la distance entre un fermé et un compact dans un espace métrique). On pose ε = d / 3 et on considère A' (resp. B'), ensembles des points à distance ε de A (resp. B), qui sont encore convexes mais sont eux des ouverts, tout en restant disjoints. On applique à ces ouverts le théorème de séparation au sens large, et on vérifie enfin sans mal que l'hyperplan obtenu sépare de fait strictement A de B.

Pour le corollaire, on prend x0 un point quelconque du complémentaire du convexe fermé C. En appliquant le théorème à C et {x0} on obtient un demi-espace fermé contenant C mais auquel x0 n'appartient pas, ce qui prouve que x0 n'est pas dans l'intersection des demi-espaces fermés contenant C. L'inclusion non évidente est ainsi prouvée.

En dimension finie, on peut aussi démontrer cette forme du théorème de séparation en se reposant sur le théorème de projection sur un convexe fermé. En effet si A est fermé et B est un singleton (contenant un point x0 extérieur à A), on peut trouver un hyperplan les séparant en projetant x0 sur A en un point x_0^* puis en utilisant l'hyperplan perpendiculaire à [x_0,x_0^*] passant par le milieu de ce segment. Dans le cas général, on se ramène à cette situation particulière en séparant le fermé AB de {0}, comme dans la preuve du théorème de séparation large[7].

Hyperplans d'appui

Un exemple d'unicité de l'hyperplan d'appui
Un exemple de non-unicité de l'hyperplan d'appui

Un cas particulièrement important est celui où B est un singleton contenant un seul point x0, choisi sur la frontière de A.

Commençons par une définition : pour A partie d'un espace vectoriel sur \R et x0 élément de A, on dit qu'un hyperplan affine H est un hyperplan d'appui de A en x0 lorsque x0 appartient à H et A est inclus dans un des demi-espaces limités par H.

On peut alors énoncer[8] :

Théorème — Dans un espace affine de dimension finie, soit C un convexe fermé et x0 un point de la frontière de C. Il existe au moins un hyperplan d'appui de C en x0.

Pour le prouver, on se débarrasse d'abord du cas dégénéré où la dimension de C serait plus petite que celle de l'espace ambiant : si c'est ainsi, n'importe quel hyperplan affine contenant l'enveloppe affine de C convient. Une fois ce cas éliminé, l'intérieur int(C) n'est pas vide et on peut appliquer le théorème de séparation à l'ouvert int(C) et au singleton {x0}, qu'on sépare par un hyperplan H. Comme C est l'adhérence de son intérieur (voir l'article Adhérence, intérieur et frontière d'un convexe), il est lui aussi inclus dans un des demi-espaces délimités par H, et cet hyperplan répond donc au cahier des charges.

Les hyperplans d'appui sont des outils fondamentaux pour classifier les points au bord d'un polyèdre convexe en sommets, points des arêtes, points des faces, etc... et plus généralement pour distinguer et étudier des points et parties remarquables de la frontière d'un convexe.

Références

  1. Haïm Brezis, Analyse fonctionnelle : théorie et applications [détail des éditions], p. 4-5 dans l'édition de 1983.
  2. La définition varie selon les sources. Marcel Berger, Géométrie [détail des éditions] par exemple requiert seulement que A et B soient de part et d'autre de H, dans les demi-plans stricts qu'il limite
  3. Ainsi dans Brezis, op. cit., qui a servi de source ; ce sont les théorèmes I-6 et la remarque 4, p. 5 et 7.
  4. Brezis, op. cit. remarque 4, p. 7.
  5. Brezis, op. cit., th. I.7, p. 7.
  6. Marcel Berger, Géométrie [détail des éditions], proposition 11.5.5,, tome 3, p. 45 dans l'édition de 1978 (l' énoncé n'est donné dans cette source qu'en dimension finie).
  7. Jean-Baptiste Hiriart-Urruty et Claude Lemaréchal, Fundamentals of convex analysis, coll. « Grundlehren Text Editions », Springer, 2001 (ISBN 3540422056) p.51-53
  8. Berger, op. cit., Prop. 11.5.2, tome 3, p. 43.
Ce document provient de « S%C3%A9paration des convexes ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Separation des convexes de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Séparation des convexes — Un exemple de séparation stricte Étant donnés deux convexes d un même plan ne se rencontrant pas, il est toujours possible de subdiviser le plan en deux demi plans de sorte que chacun contienne entièrement l un des convexes. Il en est de même en… …   Wikipédia en Français

  • Separation (mathematiques) — Séparation (mathématiques) En topologie et en géométrie, la séparation est une propriété caractérisant la possibilité de séparer de manière convenable deux parties disjointes données d un espace topologique. La manière de séparer ces parties… …   Wikipédia en Français

  • Séparation (mathématiques) — Pour les articles homonymes, voir Séparation. En topologie et en géométrie, la séparation est une propriété caractérisant la possibilité de séparer de manière convenable deux parties disjointes données d un espace topologique. La manière de… …   Wikipédia en Français

  • Theoreme des quatre sommets — Théorème des quatre sommets Une ellipse (en rouge) et sa développée (en bleu), montrant les 4 sommets annulant k , chacun d eux correspondant à un cusp de la développée. Le théorème des 4 sommets consititue un résultat remarquable de géométrie… …   Wikipédia en Français

  • Théorème des quatre sommets — Une ellipse (en rouge) et sa développée (en bleu), montrant les 4 sommets annulant k , chacun d eux correspondant à un point de rebroussement de la développée. Le théorème des quatre sommets constitue un résultat remarquable de géométrie… …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Theoreme optimisation/separation — Théorème optimisation/séparation Le théorème Optimisation/Séparation est une conséquence de la méthode de l ellipsoïde. Il constitue un résultat (très difficile à montrer) majeur en optimisation combinatoire qui fait le lien entre l approche… …   Wikipédia en Français

  • Théorème Optimisation/Separation — Théorème optimisation/séparation Le théorème Optimisation/Séparation est une conséquence de la méthode de l ellipsoïde. Il constitue un résultat (très difficile à montrer) majeur en optimisation combinatoire qui fait le lien entre l approche… …   Wikipédia en Français

  • Théorème Optimisation/Séparation — Le théorème Optimisation/Séparation est une conséquence de la méthode de l ellipsoïde. Il constitue un résultat (très difficile à montrer) majeur en optimisation combinatoire qui fait le lien entre l approche polyèdrale et l algorithmique. Ce… …   Wikipédia en Français

  • Théorème optimisation/séparation — Le théorème Optimisation/Séparation est une conséquence de la méthode de l ellipsoïde. Il constitue un résultat (très difficile à montrer) majeur en optimisation combinatoire qui fait le lien entre l approche polyèdrale et l algorithmique. Ce… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”