1

How can we formulate a linear programme that tells us whether an arbitrary point x[ j ] ∈ X, where X = {x1, ... ,xn} ⊂ Rn is an extreme point of the convex hull of X, that is conv(X)?

According to the solution of this linear programme, we should be able to claim that 'yes, x[ j ] is an extreme point', or 'no'.

Well, what I've in my mind is something like that:

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

If such a[ i ] s exist, that means x[ j ] is a linear combination of other x's, which seems like a violation to the definition of an extreme point.

However, I believe this LP does not cover the whole context. i.e., what if we select an x[ j ] which is located inside the conv(X) (not on the edges) and is not a linear combination of others. Then the model will result in a fallacious outcome. It seems to me that, above model would be fine iff the selected x [ j ] stands on the edges of conv(X).

Thanks.

2
  • You should include what you have tried. There plenty of examples on the web for Convex Hull routines. This looks like a copy paste of a homework assign with no thought.
    – Matt
    Commented Nov 14, 2016 at 17:30
  • @Matt, please see the edit on what I've tried. I've been researching and thinking about it for hours. Asking here, was my last effort, not the first.
    – Izzy
    Commented Nov 14, 2016 at 18:13

1 Answer 1

Reset to default
2

You are quite close. A points belongs to the convex hull of a finite set of points if and only if it can be written as a convex combination of these points. Also, a point is an extreme point only if there are no two other points for which it can be written as a convex combination of them.

Let the point of interest be x_k. Then, the following linear program will do the job:

enter image description here

where x_{ik} is the i-th coordinate of the point you want to check (point k). Note that this point should be one of the points we include in the right-hand side of the equation (i.e., the problem will always have at least one solution were lambda_k = 1 and all other lambdas will equal 0.

If that point is an extreme point, then the only solution you will get is lambda_k=1, other lambdas = 0. Otherwise, a different solution (with smaller lambda_k) will pop up.

(Note that in your problem description both the number of points and the dimensions are n), therefore the corresponding indexes (j and i) run from 1 to n.

I hope this helps!

1
  • Thank you very much. Helped a lot.
    – Izzy
    Commented Nov 16, 2016 at 22:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.