Un programme linéaire pour détecter les points extrêmes d'une coque convexe

Question

Comment pouvons-nous formuler un programme linéaire qui nous indique si un point arbitraire x [j] ∈ X, où X = {x1, ..., xn} ⊂ Rn est un point extrême de la coque convexe de X, c'est-à-dire conv (X)? Selon la solution de ce programme linéaire, nous devrions pouvoir affirmer que 'oui, x [j] est un point extrême', ou 'non'.

Eh bien, ce que j'ai dans mon esprit est quelque chose comme ça:

{min: 0} s.t. x[ j ] = Σi (a[ i ] * x[ i ]); i ∈ {1, ... ,k}, ∀ j ∈ {1, ... ,k}

Si un [i] s existe, cela signifie que x [j] est une combinaison linéaire d'autres x de, ce qui semble être une violation de la définition d'un point extrême.

Cependant, je crois que cette LP ne couvre pas tout le contexte. c'est-à-dire, si nous sélectionnons un x [j] qui est situé à l'intérieur de la conv (X) (pas sur les bords) et n'est pas une combinaison linéaire d'autres. Ensuite, le modèle entraînera un résultat fallacieux. Il me semble que, au-dessus du modèle serait bien si le x [j] sélectionné se trouve sur les bords de conv (X).

Merci.

Answer 1

Vous êtes assez proche. Un point appartient au convex hull of a finite set of points si et seulement s'il peut être écrit comme une combinaison convexe de ces points. Aussi, un point est un point extrême seulement s'il n'y a pas deux autres points pour lesquels il peut être écrit comme une combinaison convexe d'entre eux.

Laissez le point d'intérêt être x_k. Ensuite, le programme linéaire suivant fera le travail:

où x_ {ik} est la i -ème coordonnée du point que vous voulez vérifier (point k). Notez que ce point devrait être l'un des points que nous incluons dans la partie droite de l'équation (ie, le problème aura toujours au moins une solution: lambda_k = 1 et tous les autres lambdas seront égaux à 0.

Si ce point est un point extrême, alors la seule solution que vous obtiendrez est lambda_k = 1, autre lambdas = 0. Sinon, une solution différente (avec lambda_k plus petit) apparaîtra

(Notez que dans la description de votre problème à la fois le nombre de points et les dimensions sont n), donc la course 1-n.

indices correspondants (j et i) Je souhaite th est utile!