• 12
• 12
• 9
• 10
• 13

[HELP] hyperplane - halfspace intersection

This topic is 4205 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

Hi there! I'm preparing a seminar-presentation for my university and I got stuck in a formula: (0 <= li <= hi <= 1) Their description: "We can interpret Wn' geometrically as an intersection of 2n halfspaces and one hyperplane. It means that Wn' is an (n-1) Dimensional convex set in R^n, and it can be expressed as a convex hull of some points in R^n" We consider n=3. My problem: How can I see it figurative, that the formula describes the intersection?? Where they took the 2n halfspaces from? [help]

Share on other sites
n halfspaces li <= wi
n halfspaces wi <= hi
2n together

(n-1) dimmensional because wn is a function of w1 .. wn-1

In 3 dimensions the 2n halfspaces is box and the last constraint, the sum describes a plane. So Wn' is the intersection of those two.

Hope it helps.

Share on other sites
li and hi are basically inequality constraints. The relation li ≤ wi ≤ hi for each of n dimensions can be expressed as a series of linear constraints:

1*w1 + 0*w2 + 0*w3 + ... + 0*wn ≥ l1
0*w1 + 1*w2 + 0*w3 + ... + 0*wn ≥ l2
0*w1 + 0*w2 + 1*w3 + ... + 0*wn ≥ l3
...
0*w1 + 0*w2 + 0*w3 + ... + 1*wn ≥ ln

Those are the n constraints for the lower bounds. There are also n constraints for the upper bounds, creating a total of 2n constraints (each of which defines a half-space). The intersection of the half-spaces alone create a hypercube (or in the case of n=3, a regular cube). Keep in mind that the term "intersection" in a linear programming sense simply means the set of all points satisfying the constraints.

The second part of the equation with the summation creates the hyperplane. This constraint looks like this:

1*w1 + 1*w2 + 1*w3 + ... + 1*wn = 1

The intersection is (n-1) dimensional because you intersect with a hyperplane, which is (n-1) dimensional (the same way that a plane is a 2D set in R3). Said in a different way, each linearly independent equality constraint reduces the dimension of the potential solution set, while inequalities do not (although they may reduce the set, the dimension is unchanged).

[Edited by - Zipster on September 14, 2006 8:26:04 AM]

Share on other sites
Big thanks guys - you are great!!!

Rate++ 4 u :)

But now I have a one more question.

It's said: "It means that Wn' is an (n-1) Dimensional convex set in R^n, and it can be expressed as a convex hull of some points in R^n"

How can I compute that convex-hull-defining-points? I see, that are some kind of extrema of the halfspace-plane intersections. But how can I compute them?

I know, I should repeat some math [rolleyes]. I'll do it, when I find some spare time ;)

Share on other sites
Think of the case in dimension 3. The intersection of a box and a plane is a polygon. The vertices of the polygon are the minimal set of points whose convex hull is Wn'. It is not obvious to me how to compute that set of points, but it has to be something like computing the intersection of n-1 of the half-space-defining hyperplanes (these gives you the 1-dimensional edges of the hyper-box) and the given hyperplane. Some of those intersections will be away from the hyper-box, and you can just ignore those.

I can try to hack together some code, if that's what you need.

Share on other sites
The first 6 half-space equations define a hypercube, and the last equation defines a hyperplane. So you basically clip the plane to the cube, which will leave you with the convex hull you're looking for. Keep in mind that Wn' could be empty if there aren't any points satisfying the constraints, i.e. if the lower bounds are two big or the upper bounds are too small.

The clipping can either be done mathematically or literally (by clipping a bounded Rn-1 set against 2n hyperplanes), but since you have such a small number of planes and you don't need a convex hull as your result (just a set of points), the mathematical way is easier to implement. As a matter of fact, all you need is a simple matrix library that performs inversion.

Assuming n=3 now, the idea is that a cube is formed by 12 edges in addition to the 6 sides. Every adjacent pair of sides form an edge, and of course sides that are opposite each other don't intersect to form edges. It's the case that the extreme points you're looking for occur at the intersection of the edges and the hyperplane. So what you do is take each pair of half-space equations (treating them as equalities), and solve them simultaneously along with the hyperplane equation. This performs intersection between the edge lines and the plane to get a point. You would use 3x3 matrices to solve these systems. In the 3 cases where the two half-space equations are dependent, matrix inversion will fail, and you can simply ignore that system. Make a list of all the solutions - there should be 12. Now the issue is that most of those solutions aren't real, since the plane equations we used to find the solutions don't "know" that they're really forming a bounded hypercube. The bad solutions will have a component that is outside the bounds, so simply iterate each solution and throw away the ones where there is a component out-of-bounds. You will be left with anywhere from 0-4 points, which define your hull, in no particular order! This method can also be expanded to any number of dimensions simply by solving larger systems, which is handled automatically by the matrices.

However there is a huge optimization you can make in this particular case since your clipping region is a hypercube. All the half-space equations only have a single 1 coefficient and the rest are 0's. This means that you don't even have to use general matrix inversion - the values of (n-1) of the variables are just given to you, and all you have to do is plug them into the hyperplane equation to get the last variable! For instance, if you have a matrix equation that looks like this:
| 0 1 0 0 |   | x |   | 7 || 1 0 0 0 | * | y | = | 4 || 0 0 0 1 |   | z |   | 9 || A B C D |   | w |   | 6 |

You know immediately that y = 7, x = 4, and w = 9. All you do is plug those into the last equation to solve for z.

[Edited by - Zipster on September 17, 2006 7:58:55 AM]