Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Combinaison convexe
Résumé
En géométrie affine, une combinaison convexe de certains points est un barycentre de ces points avec des coefficients tous positifs. L'ensemble des combinaisons convexes de ces points est donc leur enveloppe convexe.
Soit E un espace affine réel (c'est-à-dire que les scalaires sont les
nombres réels). Si et sont des points de E, une combinaison convexe des est un point de la forme
où sont des réels positifs de somme 1.
Le problème du point extrême consiste à déterminer si un point P0 est ou non une combinaison convexe de points Pi, 1 ≤ i ≤ n. Dobkin et Reiss ont montré que ce problème avait une complexité linéaire, en O(n), dans et . Megiddo a montré que la complexité était linéaire en dimension finie, dans avec d fini.
La résolution se ramène à savoir s'il existe une droite (dans ), un plan (dans ) ou un hyperplan (dans , d > 3) passant par P0, tel que tous les points Pi sont du même côté de la droite, du plan ou de l'hyperplan. Cela revient donc au problème de séparation : séparer un ensemble de points par un hyperplan.
Dans le plan, la recherche peut se faire de la manière suivante. On effectue une transformation affine de sorte que P0 ait pour coordonnées (0 ; 0) et P1(0 ; 1) ; de ce fait, la droite de séparation, si elle existe, ne peut pas être l'axe des y. Le point Pi a pour coordonnées (xi, yi).
La droite cherchée passe par P0, l'origine, et a donc pour équation :
y = ax, ce qui s'écrit également si x est non nul y/x = a.
Cette droite délimite deux demi-plans d'équation (y < ax) et (y > ax).
Si P0 n'est pas dans l'enveloppe convexe, alors tous les points sont dans le même demi plan, c'est-à-dire que tous les points doivent être au-dessus de la droite (puisqu'au moins un point, P1, l'est). On doit donc avoir pour tout i
yi > axi
soit
si xi > 0, alors yi/xi > a ;
si xi < 0, alors yi/xi < a.
On a donc la condition nécessaire et suffisante pour que a existe, c'est-à-dire pour que P0 soit hors de l'enveloppe convexe :
Calcul de l'enveloppe convexe
Combinaison barycentrique
Catégorie:Analyse convexe
Catégorie:
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Proximité ontologique
Cours associés (6)
MGT-418: Convex optimization
This course introduces the theory and application of modern convex optimization from an engineering perspective.
MATH-261: Discrete optimization
This course is an introduction to linear and discrete optimization.
Warning: This is a mathematics course! While much of the course will be algorithmic in nature, you will still need to be able to p
EE-556: Mathematics of data: from theory to computation
This course provides an overview of key advances in continuous optimization and statistical analysis for machine learning. We review recent learning formulations and models as well as their guarantees
Séances de cours associées (35)
Matrices de densité réduite: System+Environnement
Couvre le concept de matrices de densité et l'interaction système-environnement.
La communautarité en anneaux
Couvre la commutabilité dans les anneaux, les options d'évaluation et les combinaisons linéaires formelles.
Ensembles de convex : séance de cours MGT-418
Sur Convex Optimization couvre l'organisation des cours, les problèmes d'optimisation mathématique, les concepts de solution et les méthodes d'optimisation.
Publications associées (46)
Personnes associées (9)
Unités associées (1)
Concepts associés (11)
Conical combination
Given a finite number of vectors in a real vector space, a conical combination, conical sum, or weighted sum of these vectors is a vector of the form where are non-negative real numbers. The name derives from the fact that a conical sum of vectors defines a cone (possibly in a lower-dimensional subspace). The set of all conical combinations for a given set S is called the conical hull of S and denoted cone(S) or coni(S). That is, By taking k = 0, it follows the zero vector (origin) belongs to all conical hulls (since the summation becomes an empty sum).
Combinaison barycentrique
En géométrie vectorielle, une combinaison barycentrique ou combinaison affine de vecteurs est une combinaison linéaire dont la somme des coefficients est égale à 1. L’expression s’emploie par défaut pour une somme finie, mais parfois aussi pour la limite d’une série sous réserve de convergence. Les combinaisons barycentriques correspondent ainsi aux barycentres des vecteurs vus comme des points de l’espace affine associé, et l’ensemble de ces combinaisons barycentriques constitue le sous-espace affine engendré par ces points.
Cône convexe
En algèbre linéaire, un cône convexe est une partie d'un espace vectoriel sur un corps ordonné qui est stable par combinaisons linéaires à coefficients strictement positifs. droite|vignette|Exemple de cône convexe (en bleu clair). À l'intérieur de celui-ci se trouve le cône convexe rouge clair qui est composé des points avec, et étant les points représentés sur la figure. Les courbes en haut à droite indiquent que les régions se prolongent à l'infini.