How to Insure a Rectangle Lies Inside a Polyhedron?

[Stephen Tashi]

All polyhedra formed by the intersection of convex sets are convex. But I think you can make polyhedra that are not convex by other means. I recall Christmas ornaments that were polyhedra shaped like 3 dimensional stars. They involved pyramids to form the arms of the star.

OK, polytope it is, if remember to use that word.

If were are ready to get to the hard part then we'll have to figure it out!

I think understanding the magic of A^+ [/tex] and A^- is mainly an exercise in algebra, not geometry.<br /> <br /> I suspect (but am not certain) that the following is a useful thought:<br /> <br /> Every vertex \mathbf{v} of the rectangle has a components of the form<br /> v_i = l_i + \delta_i ( u_i - l_i)<br /> where \delta_i is either 0 or 1.<br /> <br /> This says to form a vertix, you look in each coordinate and you either make it the corresponding coordinate in the &quot;lower&quot; vertex of the rectangle or you make it equal the correspoinding coordinate of the &quot;upper&quot; vertex.<br /> <br /> All possible combinations of choices give all possible vertices.

 

[EngWiPy]

All polyhedra formed by the intersection of convex sets are convex. But I think you can make polyhedra that are not convex by other means. I recall Christmas ornaments that were polyhedra shaped like 3 dimensional stars. They involved pyramids to form the arms of the star.

...

I suspect (but am not certain) that the following is a useful thought:

Every vertex \mathbf{v} of the rectangle has a components of the form
v_i = l_i + \delta_i ( u_i - l_i)
where \delta_i is either 0 or 1.

This says to form a vertix, you look in each coordinate and you either make it the corresponding coordinate in the "lower" vertex of the rectangle or you make it equal the correspoinding coordinate of the "upper" vertex.

All possible combinations of choices give all possible vertices.

So, you are saying that, not all poyhedra are convex sets? This point is not clear enough to me. I mean all halfspaces formed by the inequality constraints are convex sets, right? and the intersection of convex sets is also convex, is not it? So, why a polyhedron is not always convex?

I did not understand the last part. How did you write a vertex in that form and why? I read you comment on this, but it is still not clear. Just to make sure, a polytope is a connected hyperplanes, i.e.: each edge of a hyperplane, is an edge to other hyperplane. The point where these edges connected is called vertex, right? As in two dimensional rectangle, for example, we have four vertices, i.e.: the corners.

 

[Stephen Tashi]

So, you are saying that, not all poyhedra are convex sets? This point is not clear enough to me. I mean all halfspaces formed by the inequality constraints are convex sets, right? and the intersection of convex sets is also convex, is not it? So, why a polyhedron is not always convex?

All polyhedra/polytopes that you make by defining constraints of the form Ax <= b are convex. That's not the only way to define a polyhedron.. I think all you need for a polyhedron is for it to have faces that are polygons. You can glue together all sorts of shapes with polygonal faces cut out of cardboard.

I did not understand the last part. How did you write a vertex in that form and why? I read you comment on this, but it is still not clear.

It just my preliminary guess at a systematic way of representing the vertices. Its a form of mental filing and sorting. Is it clear that all vertices can be represented that way?
For example, in 2D, L = (1,2) , U = (5,7) , U-L = (4,5)
vertex (1,2) = (1+ (0)4, 2 + (0)5)
vertex (1,5) = (1 +(0)4, 2 + (1)5)
vertex (5,2) = (1 + (1)4, 2 + (0)5)
vetex (5,7) = (1 + (1)4, 2 + (1) 5)

Just to make sure, a polytope is a connected hyperplanes, i.e.: each edge of a hyperplane, is an edge to other hyperplane.

I say that a polytope is formed by "intersecting" hyperplanes (if we mean only the boundary of the volume, not the interior). The edges are intersections of hyperplanes but we should say more since the intersection of of two hyperplanes is usually a line, not a line segment. An edge is a line segment. We need some way to describe that.

The point where these edges connected is called vertex, right?
As in two dimensional rectangle, for example, we have four vertices, i.e.: the corners.

Yes, a point where two or more edges meet is a vertex.

 

[Stephen Tashi]

It's time for me to ride the exercise machine for half an hour. I'll be back later. I think the definition of polytopes must be done by intersecting half spaces , not merely half planes. The we can say something about an edge being the part of a line of intersection between two hyperplanes that is also on the boundary of the volume formed by all the intersecting half spaces.

 

[EngWiPy]

All polyhedra/polytopes that you make by defining constraints of the form Ax <= b are convex. That's not the only way to define a polyhedron.. I think all you need for a polyhedron is for it to have faces that are polygons. You can glue together all sorts of shapes with polygonal faces cut out of cardboard.

Ok, I see. Now it makes sense.

It just my preliminary guess at a systematic way of representing the vertices. Its a form of mental filing and sorting. Is it clear that all vertices can be represented that way?
For example, in 2D, L = (1,2) , U = (5,7) , U-L = (4,5)
vertex (1,2) = (1+ (0)4, 2 + (0)5)
vertex (1,7) = (1 +(0)4, 2 + (1)5)
vertex (5,2) = (1 + (1)4, 2 + (0)5)
vetex (5,7) = (1 + (1)4, 2 + (1) 5)

Ok, I agree on that formulating.

I say that a polytope is formed by "intersecting" hyperplanes (if we mean only the boundary of the volume, not the interior). The edges are intersections of hyperplanes but we should say more since the intersection of of two hyperplanes is usually a line, not a line segment. An edge is a line segment. We need some way to describe that.

I have a book in geometry defines a convex polyhedron as following (which means that there are non convex polyhedra as you said):

A convex polyhedron is a system of finitely many convex polygons, with the property that each side of every polygon is also aside of a second polygon and for every polygon in the system the vertices of the polyhedron that do not lie on the given polygon are all in the same halfspace determined by the plane of the polygon

(I do not understand the underlined part). I think, we can say that each hyperplane is cut by two other hyperplanes to form a polytope. This process makes a polytope intersected polygons, and a polygon is bounded, and its edges are line segments. Am I right on this?

 

[EngWiPy]

It's time for me to ride the exercise machine for half an hour. I'll be back later. I think the definition of polytopes must be done by intersecting half spaces , not merely half planes. The we can say something about an edge being the part of a line of intersection between two hyperplanes that is also on the boundary of the volume formed by all the intersecting half spaces.

have a nice time.

 

[Stephen Tashi]

(I do not understand the underlined part).

It means that if you pass a plane through the face of a convex polygon then either all the polygon is on one side of the plane or all of the polygon is on the other side of the plane. You don't have part on one side and part on the other.

I think, we can say that each hyperplane is cut by two other hyperplanes to form a polytope. This process makes a polytope intersected polygons, and a polygon is bounded, and its edges are line segments. Am I right on this?

[/QUOTE]

I don't think that is precise enough for a mathematical definition, but you might have the correct intuitive idea. It isn't clear whether your phrase "two other hyperplanes" means "exactly two" or "at least two". Look at the plane that contains one face of a rectangular solid. It is intersected by 4 other planes that bound the figure.

If you want to get the verbal definition of polygon/polytope correct, we both are going to have to consult some references!

 

[EngWiPy]

Let us skip this discussion for a moment, because this requires us to go back to some definitions and references, and let us focus more on the core problem.

This says to form a vertix, you look in each coordinate and you either make it the corresponding coordinate in the "lower" vertex of the rectangle or you make it equal the correspoinding coordinate of the "upper" vertex.

All possible combinations of choices give all possible vertices.

What do you mean by this?

 

[Stephen Tashi]

What do you mean by this?

Think of the 0's and 1's in the example as representing a decision.
1 = go to the coordinate of the upper vertex U,
0 = stay at the corner of the lower vertex L.

L = (1,2) , U = (5,7) , U-L = (4,5)

All possible ordered pairs of 0's and 1's represent all possible decisions about the vertices.

(0,0) -> vertex (1,2) = (1+ (0)4, 2 + (0)5)
(1.1)-> vertex (1,7) = (1 +(0)4, 2 + (1)5)
(1, 0)-> vertex (5,2) = (1 + (1)4, 2 + (0)5)
(1,1)-> vetex (5,7) = (1 + (1)4, 2 + (1) 5)

 

[EngWiPy]

Think of the 0's and 1's in the example as representing a decision.
1 = go to the coordinate of the upper vertex U,
0 = stay at the corner of the lower vertex L.

L = (1,2) , U = (5,7) , U-L = (4,5)

All possible ordered pairs of 0's and 1's represent all possible decisions about the vertices.

(0,0) -> vertex (1,2) = (1+ (0)4, 2 + (0)5)
(1.1)-> vertex (1,7) = (1 +(0)4, 2 + (1)5)
(1, 0)-> vertex (5,2) = (1 + (1)4, 2 + (0)5)
(1,1)-> vetex (5,7) = (1 + (1)4, 2 + (1) 5)

I just arrange this formulating to this example as following:

v_i=(v_{i1},v_{i2})=(1+\delta_{i1}(4),2+\delta_{i2}(5))

And as you said, all combinations of (\delta_{i1},\delta_{i2}) give all possible vertices of the rectangle in 2D with upper vector U and lower vector L. Again, I agree on this formulating. The question now: why did you did that systemic formulation of the vertices? How this can help us understanding the problem?

 

[Stephen Tashi]

I'm thinking about making an equation that looks like Prof. Boyd's method. That was my motivation for enumerating the vertices with the deltas.Let a represent one row of the constraint matrix \mathbf{A}. Pretend we're in 2 dimensions, so a = (a_1,a_2)

The row defines the left hand side of a constraint , which is:

a_1 x_1 + a_2 x_2 \leq b where b is a scalar.

The crucial values for (x_1,x_2) are the vertices of the rectangle. If one vertex fails to satisfy the constraint, the rectangle isn't a solution.

Let the lower vertex of the rectangle be l = (l_1,l_2) and the upper vertex be u = (u_1, u_2).

To represent testing all vertices in the constraint, we can write

a_1 (l_1 + \delta_1(u_1 - l_1) + a_2(l_2 + \delta_2(u_2 - l_2) \leq b

Where \delta_1 and \delta_2 range over all possible combinations of 0's and 1's.

Applying some algebra to the above:

a_1 \delta_1 u_1 - a_1(\delta_1 - 1) l_1 + a_2 \delta_2 - a_2( \delta_2 - 1) l_2 &lt; b

= a_1 \delta_1 u_1 + a_2 (\delta_2) - ( a_1 (\delta_1-1)l_1 + a_2(\delta_2 - 1) l_2) &lt; b

This has a strong resemblance to Prof Boyd's constraint, which would be:

a_1^+ u_1 + a_2^+ u_2 - (a_1^- l_1 + a_2^- l_2 )&lt; b

We have to convince ourselves that using Prof. Boyd's a^+ and a^- [/tex] somehow picks out the values for the deltas that maximize the left hand side of the constraint.

 

[EngWiPy]

Ok, that is good. But what is the geometric interpretation for this? I mean, as prof. Boyd's said in the solution, a trivial way is to check that all vetrices of the rectangle lie within the polytope, where we have 2^{n} vertices, right? But, apparently, there is a much more efficient way.

Let me give example: Suppose we want to insure that all elements of a matrix is less that a constant, say c. Then it suffices to check that the min element of the matrix is less than c. I think, prof. Boyd's method resembles this thinking. I don't know, may be if the maximum difference of something and something less than b, then all vertices are less than b. However, I don't know what is this "something", and what is the geometric interpretation of it.

 

[Stephen Tashi]

I don't see a good geometric interpretation for Prof. Boyd's constraint. I think the way to see it is from algebra.

I shall fix a typo ( a missing u_2 ) in my constraint and compare it

Constraint 1: a_1 \delta_1 u_1 + a_2 \delta_2 u_2 - ( a_1 (\delta_1-1)l_1 + a_2(\delta_2 - 1) l_2) &lt; b

with

Constraint 2: a_1^+ u_1 + a_2^+ u_2 - (a_1^- l_1 + a_2^- l_2 )&lt; b

If we were trying to make the left hand side of Constraint 1 as large as possible, which values for the deltas would we pick?

Relevant to \delta_1 are the terms a_1 (\delta_1-1) u_1 and a_1(\delta1 -1) l_1.

We know l_1 &lt; u_1 [/tex]<br /> <br /> Suppose a_1 &amp;gt; 0. <br /> <br /> If we set \delta_1 = 1 then the total contribution of the two terms is <br /> <br /> a_1 u_1<br /> <br /> If we set \delta = 0 then the total contribution of the two terms is<br /> <br /> - a_1( -1)l_1 = a_1 l_1<br /> <br /> So the best choice is \delta_1 = 1 [/tex]&lt;br /&gt; &lt;br /&gt; Notice how Prof. Boyd&amp;#039;s use of the \mathbf{A^+} and \mathbf{A^-} matrices makes the same choice in this case.&lt;br /&gt; &lt;br /&gt; In Constraint 2: a_1^+ u_1 + a_2^+ u_2 - (a_1^- l_1 + a_2^- l_2 )&amp;amp;lt; b&lt;br /&gt; &lt;br /&gt; if a_1 &amp;amp;gt; 0 then a_1^+ = a_1 and a_1^- = 0&lt;br /&gt; &lt;br /&gt; So the total contribution of the terms involving a_1 is the same as in Constraint 1.&lt;br /&gt; &lt;br /&gt; I think we prove Prof. Boyd&amp;#039;s constraint by looking at the various cases for the sign of the a_i. We decide what the best value for \delta_i is and we confirm that the a^+_i and a^-_i terms produce the contribution that matches our choice of \delta_i.

 

[EngWiPy]

That is awesome. I tried all combinations of (\delta_1,\delta_2) and all signs of (a_1,a_2) and compare them with prof. Boyd's notation, and it is just working perfectly.

I wonder how math can do all of this. It is amazing. I mean, I am an engineer, and you just have to set up the problem mathematically, and see if a system is working!

Thank you Stephen Tashi for your patience. I am really appreciate your help and you time.

Best regards

 

[Stephen Tashi]

You're welcome. I hope if you come across other problems that are this interesting that you will post them.

 

[EngWiPy]

You're welcome. I hope if you come across other problems that are this interesting that you will post them.

Of course I will.