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 résultat établit l'équivalence, du point de vue de la complexité algorithmique, entre "optimiser" et "séparer" sur un même polyèdre. Un polyèdre $P$ de $\mathbb R^n$ est constitué par l'ensemble des points $x\in \mathbb R^n$ satisfaisant un nombre arbitrairement grand mais fini d'inégalités linéaires (i.e. de la forme $\sum_{i=1}^{i=n} a_ix_i \le b$ ).

Optimiser sur $P$ consiste à déterminer $\max_{x\in P} f(x)$ pour toute fonction linéaire $f (x)$ .
Séparer sur $P$ consiste à déterminer si $\bar x\in P$ ou non, pour tout point $\bar x \in \mathbb R^n$ , et si non à déterminer un hyperplan séparant $\bar x$ de $P$ (i.e. trouver une inégalité linéaire violée par $\bar x$ mais satisfaite par tout point de $P$ ).

Théorème Optimisation/Séparation (M. Grötschel, L. Lovász, A. Shrijver, 1981) On peut optimiser sur un polyèdre en temps polynomial si et seulement si on peut séparer sur ce polyèdre en temps polynomial.

Articles en rapport avec la convexité
Géométrie convexe	Article principal : Ensemble convexe Outils et résultats fondamentaux : Enveloppe convexe • Adhérence, intérieur et frontière d'un convexe • Projection sur un convexe fermé • Séparation des convexes • Points remarquables à la frontière d'un convexe • Polytope • Théorème de Krein-Milman • Lemme de Farkas Géométrie combinatoire : Théorème de Carathéodory • Théorème de Radon • Théorème de Helly Géométrie métrique : Courbe de largeur constante • Théorème des quatre sommets Algorithmes de géométrie convexe : Approche polyèdrale • Marche de Jarvis • Parcours de Graham • Théorème optimisation/séparation Optimisation linéaire : Programmation linéaire • Algorithme du simplexe • Génération de colonnes
Interactions géométrie-analyse	Théorème de Hahn-Banach • Jauge
Analyse convexe	Article principal : Fonction convexe Outils et résultats fondamentaux : Inégalité de Jensen Optimisation convexe : Conditions de Kuhn-Tucker • Méthode du point intérieur
Utilisations de la convexité	Inégalités de convexité : Inégalité arithmético-géométrique • Inégalité de Hölder Analyse fonctionnelle : Espace localement convexe • Théorème du point fixe de Schauder Localisation de zéros de polynômes : Théorème de Gauss-Lucas Théorie des nombres : Théorème de Minkowski

Portail des mathématiques

Ce document provient de « Th%C3%A9or%C3%A8me optimisation/s%C3%A9paration ».

Catégories : Théorème de mathématiques | Optimisation | Optimisation combinatoire | Algorithmique et convexité

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Théorème optimisation/séparation de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

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
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… … Wikipédia en Français
Theoreme de projection sur un convexe ferme — Théorème de projection sur un convexe fermé En mathématiques, le théorème de projection orthogonale sur un convexe est un résultat de minimisation de la distance qui généralise la projection orthogonale sur un espace vectoriel. Il remplace… … Wikipédia en Français
Théorème de projection orthogonale sur un convexe — Théorème de projection sur un convexe fermé En mathématiques, le théorème de projection orthogonale sur un convexe est un résultat de minimisation de la distance qui généralise la projection orthogonale sur un espace vectoriel. Il remplace… … Wikipédia en Français
Theoreme de Hahn-Banach — Théorème de Hahn Banach Ce théorème, auquel a été donné le nom des deux mathématiciens Hans Hahn et Stefan Banach, garantit l existence d une forme linéaire vérifiant certaines conditions (valeurs imposées sur une partie de l espace, mais… … Wikipédia en Français
Théorème de hahn-banach — Ce théorème, auquel a été donné le nom des deux mathématiciens Hans Hahn et Stefan Banach, garantit l existence d une forme linéaire vérifiant certaines conditions (valeurs imposées sur une partie de l espace, mais limitées partout). En… … Wikipédia en Français
Théorème de Helly — dans le plan : si trois quelconques des convexes de la famille se rencontrent alors l intersection de tous ces convexes est non vide. Le théorème de Helly est un résultat combinatoire sur les convexes. Ce résultat a été prouvé en 1913 par… … Wikipédia en Français
Théorème de carathéodory (géométrie) — Le théorème de Carathéodory est un théorème de géométrie relatif aux enveloppes convexes dans le contexte des espaces affines de dimension finie. Sommaire 1 Énoncé 2 Preuves 2.1 La preuve usuelle … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Théorème optimisation/séparation