How to Insure a Rectangle Lies Inside a Polyhedron?

[EngWiPy]

Hi,

How to insure that a rectangle \mathbf{R}=\{\mathbf{x}\in R^n:\mathbf{l}\leq\mathbf{x}\leq\mathbf{u}\} lies inside a polyhedron \mathbf{P}=\{\mathbf{x}\in R^n: \mathbf{A}\mathbf{x}\leq\mathbf{b}\}

Thanks

 

[Stephen Tashi]

If you want to see if a rectangular solid is inside a convex polygon, just test whether its corners are. I can't tell from your notation whether the polygon is convex.

 

[EngWiPy]

If you want to see if a rectangular solid is inside a convex polygon, just test whether its corners are. I can't tell from your notation whether the polygon is convex.

Why not? I am any polyhedron is convex, right? Because it is the intersection of the polygons. Am I right?

 

[EngWiPy]

Ok, another question, because I am really bad in geometric interpretation, what we mean by:

\mathbf{A}^+\mathbf{u}-\mathbf{A}^-\mathbf{l}\leq \mathbf{b}

where:

\mathbf{A}^+=\text{max}(\mathbf{[a_{ij}],0)}

and

\mathbf{A}^-=\text{max}(\mathbf{[-a_{ij}],0)}

Thanks

 

[Stephen Tashi]

I don't understand the notation.

Are \mathbf{u} and \mathbf{l} vectors?

 

[EngWiPy]

I don't understand the notation.

Are \mathbf{u} and \mathbf{l} vectors?

That is right. They are defined in the first post. These two vectors define the rectangle. I appreciate if you help me in understanding this.

 

[Stephen Tashi]

Give a link to the material that you are getting this problem from or explain what book has it. Then I'll look at it. I don't want to spend time thinking about something from an abbreviated description.

 

[EngWiPy]

Give a link to the material that you are getting this problem from or explain what book has it. Then I'll look at it. I don't want to spend time thinking about something from an abbreviated description.

Ok, I am sorry if my description to the problem was not enough. Dr. Byod, from the Stanford university, posted a solution to a homework, which is attached here. From the third line on, from the word "Fortunately", for the first problem, how to understand the constraint, I wrote previously:

<br /> \mathbf{A}^+\mathbf{u}-\mathbf{A}^-\mathbf{l}\leq \mathbf{b}<br />

I hope this makes things more clear.

Thanks

 

[Stephen Tashi]

This is the hazy geometric idea that I have:

The way that the i th row of \mathbf{A} defines a plane (or, in 2D, a line) is that it is a vector normal to the plane. The plane is defined by all the vectors that have a projection of some given length on that normal. The length of the projection is proportional to the dot product of the vector with the normal ( and equal to it if the normal is a unit normal).

An inequality like \sum_{j=1}^n a_{ij} w_j &lt; b_j says that the vector \mathbf{w} is on one particular side of the plane defined by the normal vector \mathbf{a}_i.

The rectangle is defined by two vectors \mathbf{l} and \mathbf{u} which define the lower end of its diagonal and the upper end of its diagonal.

A stereotyped view of this situation is to think of both ends of the diagonal being on the same side of the plane with both ends of it having a postive projection on the normal. In this case, the diagonal of the rectangle projects on the normal with a length less than b_i. Testing diagonal's projection on the normal defined by the i th column vector of \mathbf{A} would correspond to the test:

\sum_{j=1}^n a_{ij} ( u_j - l_j) &lt; b_i
\sum_{j=1}^n ( a_{ij} u_j - a_{ij} l_j) &lt; b_j (eq. 1)

What Prof. Boyd has ( correcting his summation to be over j instead of i) is:

\sum_{j=1}^n (a_{ij}^+ u_j - a_{ij}^- l_j) &lt; b_i

His definitions of a_{ij}^+ and a_{ij}^- must fix what is wrong with the stereotyped view. For example, the test (eq. 1) is invalid when the "far" end of the diagonal is on the "far" side of the plane and the "near" end of the diagonal is on the otherside.

I'll have to think more about this.

 

[EngWiPy]

...

What Prof. Boyd has ( correcting his summation to be over j instead of i) is:

\sum_{j=1}^n (a_{ij}^+ u_j - a_{ij}^- l_j) &lt; b_i

His definitions of a_{ij}^+ and a_{ij}^- must fix what is wrong with the stereotyped view. For example, the test (eq. 1) is invalid when the "far" end of the diagonal is on the "far" side of the plane and the "near" end of the diagonal is on the otherside.

I'll have to think more about this.

Thank you for this reply. I mean I have to read it over and over to understand it, but at least I have some thing to read. You are right, the summation must be over j not i. Can you please elaborate more on the quoted part? I mean suppose we have 2D polytope, what is the far and near ends?

Thanks

 

[Stephen Tashi]

It's hard to elaborate hazy ideas, but I'll try.

First, the idea that one can determine whether the rectangle statisfies a given constraint by determining whether \mathbf{u} and \mathbf{l} do is, in general, false. Think about 2D where they are opposite corrners of a rectangle. You can imagine a situation where \mathbf{u} and \mathbf{l} are on one side of line, but some other corner falls on the opposite side.

Second, there are special cases where determining whether \mathbf{u} and \mathbf{l} satisfy a constraint does determine whether the rectangle satisifies it. In 2D, consider the case where a row of \mathbf{A} is (2,3). The constraint it defines is given by a line perpendicular to the vector (2,3). Let's say that constraint is 2x + 3y < 5. If we have a rectangle where the upper (i.e. northeast) corner \mathbf{u} satisfies the constraint( i.e. falls on the southwest side of the line) then the whole rectangle must.

Edit: I posted the problem to the SOS Mathematics Cyberboard http://www.sosmath.com/CBB/viewtopic.php?p=215893#215893


Notice how Prof. Boyds constraint economically tests this:
In \mathbf{A^+} the row is (2,3). In \mathbf{A^-} the row is (0,0)
The test is whether ( 2 u_1 + 3 u_2 ) - ( (0)(l_1) + (0)(l_2)) &lt; 5
So it amounts to testing whether \mathbf{u} satisfies the constraint.

It's like Prof. Boyds constraint has some sort of built-in intelligence that adapts the test to fit the situation.

Edit: I posted this problem on the SOS mathematics cyberboard

 

[Stephen Tashi]

The poster "outermeasure" on sosmath.com offered an explanation of Prof. Boyd's constraint. (I don't understand the explanation yet.)
In my own words the explanation is as follows:

A vertex of the rectangle \mathbf{R} is formed by chosing (for each i) it's ith component to be either \mathbf{l}_i or \mathbf{u}_i. For the jth constraint \mathbf{A}_j v &lt; b_j, it is sufficient that we only check whether the vertex that produces the largest value of \mathbf{A}_j v satisfies the constraint. The professors expression: \mathb {A}_j^+ \mathbf{u} - \mathf{A}_j^- \mathbf(l)
computes this value.


Here is a 2 dimensional Example:
\mathbf{u} = (2,1) , \mathbf{l} = (1,-2)
Rectangle corners: {(1,-2),(2,-2),(1,1),(2,1)}
\mathbf{A}_j = (5,-3)

Then
\mathbf{A}_j^+ =(5,0)
\mathbf{A}_j^- =(0,3)

\mathbf{A}_j^+ \mathbf{u} - \mathbf{A}_j^+ \mathbf(l)
= ((5)(2) + (0)(-2)) - ((0)(1) + (3)(-2))
= (5)(2) - (3)(-2)
= (5)(2) + (-3)(-2)

This is the same as computing the value of \mathbf{A_j} \mathbf{v} for \mathbf{v} = the corner (2,-2).

Still looks like magic to me!

 

[EngWiPy]

...
Still looks like magic to me!

Thank you for this. Yes, it is not easy to understand. I am just very busy these days. I will read these posts later on.

Thank you again Stephen.

Regards

 

[EngWiPy]

...

The way that the i th row of \mathbf{A} defines a plane (or, in 2D, a line) is that it is a vector normal to the plane. The plane is defined by all the vectors that have a projection of some given length on that normal. The length of the projection is proportional to the dot product of the vector with the normal ( and equal to it if the normal is a unit normal).

...

Hi Stephen Tashi,

I just start read you posts to understand the solution of prof. Boyd. Can we go step by step? As I told you, I am very bad in geometric mathematics, so can you please elaborate more on the quoted part above? or direct me to some useful material about this?

Regards

 

[Stephen Tashi]

OK. FIrst is it clear that a row of \mathbf{A} defines a line or plane?

In 2D it defines an inequality like a_{j,1} x_1 + a_{j,2} x_2 \leq b_j


Are you familiar with the geometric interpretation of the dot product ( a.k.a. "inner product") of vectors?

In terms of the dot product, equation says (a_j1, a_j2) \cdot (x_1, x_2) \le b_j

Geometrically, the dot product of vector A with vector X can be computed by projecting X on to A and multiplying the length of that projection times the length of A. (If the projection goes opposite to the direction of A, it is considered to be negative).

If we pretend the inequality above is an equation, it is statisfied by all vectors X that project to some constant length on a_j. Think of a line or a plane perpendicular to vector a_j. All the vectors whose heads lie in that line or plane project to the same length on a_j.

 

[EngWiPy]

OK. FIrst is it clear that a row of <br /> \mathbf{A} <br /> defines a line or plane?

Not really.

In 2D it defines an inequality like <br /> a_{j,1} x_1 + a_{j,2} x_2 \leq b_j <br />

Ok.

Are you familiar with the geometric interpretation of the dot product ( a.k.a. "inner product") of vectors?

I just know that a inner product of two vectors is the product of their respective length times cosine the angle between them.

Geometrically, the dot product of vector A with vector X can be computed by projecting X on to A and multiplying the length of that projection times the length of A. (If the projection goes opposite to the direction of A, it is considered to be negative).

I did not understand this very well. What is the length of the projection? I mean how to compute it?

If we pretend the inequality above is an equation, it is statisfied by all vectors X that project to some constant length on a_j. Think of a line or a plane perpendicular to vector a_j. All the vectors whose heads lie in that line or plane project to the same length on a_j.

so, in <br /> a_{j,1} x_1 + a_{j,2} x_2 = b_j <br />, b_j is the projection of vector x onto vector a_j?

Thank you for your patience.

Regards

 

[Stephen Tashi]

I just know that a inner product of two vectors is the product of their respective length times cosine the angle between them.

I did not understand this very well. What is the length of the projection? I mean how to compute it?

Draw two vectors A and B tail to tail. (If B is short, draw a long line that goes through B). Let the angle between the vectors be \theta The length of A is the hypotenuse of a right triangle which has one leg along the line of B. The length of A projected on B is the length of this leg. Trigonometry says that this leg has length is the length of A times cos(\theta) So the dot product is the length of the projection times the length of B.

Understanding why multiplying the respective coordinates of A and B and adding them computes the same thing as computing the dot product is not as simple a matter. I think we shouldn't get into that right now, unless you want it demonstrated. If you accept that multiplying the respective coordinates of A and B and adding them computes the same as the above, this explains why an expression like a_{1,j} x_j + a_{2,j} x_j represents something involving a projection.

so, in <br /> a_{j,1} x_1 + a_{j,2} x_2 = b_j <br />, b_j is the projection of vector x onto vector a_j?

It isn't the length of the projection on a_j unless the length of a_j is 1. Remember the dot product involves a factor from the length of the projection and also a factor from the length of the vector upon which we project.

 

[EngWiPy]

Draw two vectors A and B tail to tail. (If B is short, draw a long line that goes through B). Let the angle between the vectors be \theta The length of A is the hypotenuse of a right triangle which has one leg along the line of B. The length of A projected on B is the length of this leg. Trigonometry says that this leg has length is the length of A times cos(\theta) So the dot product is the length of the projection times the length of B.

Understanding why multiplying the respective coordinates of A and B and adding them computes the same thing as computing the dot product is not as simple a matter. I think we shouldn't get into that right now, unless you want it demonstrated. If you accept that multiplying the respective coordinates of A and B and adding them computes the same as the above, this explains why an expression like a_{1,j} x_j + a_{2,j} x_j represents something involving a projection.



It isn't the length of the projection on a_j unless the length of a_j is 1. Remember the dot product involves a factor from the length of the projection and also a factor from the length of the vector upon which we project.

Ok, I understood the first paragraph. I feel that, we have to go through showing that the sum of the products of respective coordinates of the two vectors is the same as the inner product. This will ease understanding the equation you gave with equality, and explain the last paragraph.

 

[Stephen Tashi]

What about an outline of the process in 2D and you see if you can do the algebra!

The procedure must be to express every factor of |A| |B| cos(theta) in coordinates. Before that, you can express cos(theta) by solving for it in the law of cosines.

|C|^2 = |A|^2 + |B|^2 - 2 |A| |B] cos(theta) where C is a vector from the head of A to the head of B.

so cos(theta) = ( |A|^2 + |B\^2 - |C|^2)/ (2|A||B|)

So A dot B = |A| |B| ( |A|^2 + |B]^2 - |C|^2)/ (2|A||B|)

= ( |A|^2 + |B|^2 - |C|^2) / 2

Then you must express all those lengths squared in terms of their coordinates.
A = (a_1,a_2), B= (b_1,b_2) so C = (b_1 - a_1, b_2 - a_2)
Use the substitutions:
|C|^2 = (b_1 - a_1)^2 + (b2 - a_2)^2
|A|^2 = a_1^2 + a_2^2
|B|^2= b_1^2 + b_2^2

Do that algebra, and what should happen is that the square terms cancel out leaving
( 2 a_1 b_1 + 2 a_2 b_2)/ 2

 

[EngWiPy]

What about an outline of the process in 2D and you see if you can do the algebra!

The procedure must be to express every factor of |A| |B| cos(theta) in coordinates. Before that, you can express cos(theta) by solving for it in the law of cosines.

|C|^2 = |A|^2 + |B|^2 - 2 |A| |B] cos(theta) where C is a vector from the head of A to the head of B.

so cos(theta) = ( |A|^2 + |B\^2 - |C|^2)/ (2|A||B|)

So A dot B = |A| |B| ( |A|^2 + |B]^2 - |C|^2)/ (2|A||B|)

= ( |A|^2 + |B|^2 - |C|^2) / 2

Then you must express all those lengths squared in terms of their coordinates.
A = (a_1,a_2), B= (b_1,b_2) so C = (b_1 - a_1, b_2 - a_2)
Use the substitutions:
|C|^2 = (b_1 - a_1)^2 + (b2 - a_2)^2
|A|^2 = a_1^2 + a_2^2
|B|^2= b_1^2 + b_2^2

Do that algebra, and what should happen is that the square terms cancel out leaving
( 2 a_1 b_1 + 2 a_2 b_2)/ 2

Math is fantastic! Now I have a more clear picture about the relationship between the form
a_{j1}x_1+a_{j2}x_2 and the inner product. So, if this summation is equal to some constant b, this means that the solution is the set of vectors {x} such that their inner product with a_j is constant = b. That is great, we have some progress. Now, how to connect this with the understanding of the quotation in post #14?

 

[Stephen Tashi]

Post #14? Do you mean the question of how the constraint defines a line in 2D or plane in 3D?

 

[EngWiPy]

Post #14? Do you mean the question of how the constraint defines a line in 2D or plane in 3D?

Yes, that is right.

 

[Stephen Tashi]

Draw (in 2D) a vector 'a' from the origin Then draw another vector 'x' from the origin. Draw the projection of x onto 'a'. To do this, you "drop" a perpendicular (to 'a') from the end of 'x' and the perpendicular hits the line of 'a'. It doesn't matter if the perpendicular hits the vector 'a' itself. If it is going to hit the line containing 'a' beyond the head of 'a' or before the tail, extend the line through 'a' to meet it.

The inner product of x with 'a' is the length of this projection times the length of 'a'.

Draw another vector y from the origin to some point on the perpendiclar.

Note that the projection of y onto 'a' is the same length as the projection of 'x' onto 'a'.

So (y dot a) = (x dot a). Thus any vector y on the perpendicular satisfies the constraint (y dot a) = b, where b = (x dot a). An inequality that says (y dot a) =< b will define an infinite area bounded on one side by the perpendicular line.
.

 

[EngWiPy]

Draw (in 2D) a vector 'a' from the origin Then draw another vector 'x' from the origin. Draw the projection of x onto 'a'. To do this, you "drop" a perpendicular (to 'a') from the end of 'x' and the perpendicular hits the line of 'a'. It doesn't matter if the perpendicular hits the vector 'a' itself. If it is going to hit the line containing 'a' beyond the head of 'a' or before the tail, extend the line through 'a' to meet it.

The inner product of x with 'a' is the length of this projection times the length of 'a'.

Draw another vector y from the origin to some point on the perpendiclar.

Note that the projection of y onto 'a' is the same length as the projection of 'x' onto 'a'.

So (y dot a) = (x dot a). Thus any vector y on the perpendicular satisfies the constraint (y dot a) = b, where b = (x dot a). An inequality that says (y dot a) =< b will define an infinite area bounded on one side by the perpendicular line.
.

Ok. I did as you told me, where all vectors a,x, and y are in the first quarter. I can see that all vectors originating from the origin to the perpendicular line has the same inner product with a. How these vectors form a line in 2D? I mean, as I can see from my graphing, it forms an area between the y-axis and the perpendicular line! Unless we have to consider just the heads of the vectors. Which one is true?

 

[Stephen Tashi]

We just consider the heads of the vectors. So the constraint with an "=" sign just describes the heads of the vectors. The "heads" are the "points" on the line. If you include the '<' then we also include heads of vectors that are on one side of the line.

Linear algebra uses what are called "bound" vectors. So (in Cartesian coordinaes) the notation (2,3) mean a vector that starts at (0,0) and goes to (2,3). All vectors are understood to start at (0,0). So a "point in space" is regarded as the same as "the head of a vector to that point".

Notice that in the derivation of the dot product we used a vector C that went from A to B. If you drew it that way, C would be a "free" vector since it does not begin at the origin. However, when you compute it's length you do the calculations with the vector (b1-a1,b2-a2) which is a "bound" vector that starts at the origin. This vector has the same length as the "free" vector so the calculations are correct.

 

[EngWiPy]

We just consider the heads of the vectors. So the constraint with an "=" sign just describes the heads of the vectors. The "heads" are the "points" on the line. If you include the '<' then we also include heads of vectors that are on one side of the line.

Linear algebra uses what are called "bound" vectors. So (in Cartesian coordinaes) the notation (2,3) mean a vector that starts at (0,0) and goes to (2,3). All vectors are understood to start at (0,0). So a "point in space" is regarded as the same as "the head of a vector to that point".

Notice that in the derivation of the dot product we used a vector C that went from A to B. If you drew it that way, C would be a "free" vector since it does not begin at the origin. However, when you compute it's length you do the calculations with the vector (b1-a1,b2-a2) which is a "bound" vector that starts at the origin. This vector has the same length as the "free" vector so the calculations are correct.

Thank you very much. Now I have a very clear idea about how the inner product of two vectors <a,x>=b for a given a and b is a line in 2D, especially the second paragraph that says a point in the Cartesian coordinates is represented by the head of a vector from the origin to that point. And it is clear now that how a is normal to that line and why it is normal. When you follow the derivation step by step, the wonder is gone.

What is next?

 

[Stephen Tashi]

If you can visualize a similar situation in 3D, imagine a plane perpendicular to the vector 'a' instead of a line perpendicular to it. The same sort of thing holds. The "=" part of the constraint defines a plane.

Do you see how system of several contraints can define a polyhedra?

Then there is the question of whether a given point x is inside a polyhedra. I must visit a friend for the afternoon and then do some shopping. So I'll be offline soon and won't be back till about 6:30 PM MST.

 

[EngWiPy]

If you can visualize a similar situation in 3D, imagine a plane perpendicular to the vector 'a' instead of a line perpendicular to it. The same sort of thing holds. The "=" part of the constraint defines a plane.

Do you see how system of several contraints can define a polyhedra?

Then there is the question of whether a given point x is inside a polyhedra.


I must visit a friend for the afternoon and then do some shopping. So I'll be offline soon and won't be back till about 6:30 PM MST.

It is ok, take your time.

Yes, it is pretty clear how a simultaneously satisfied inequality constraints define a polyhedron, which is the intersection of the half spaces created by the planes (in 3D) or lines (in 2D). But before we examine if a point x is inside a polyhedron, there is another question, just to agree on the terminologies: I read somewhere that a polyhedron is the intersection of all the inequality constraints, and a polytope is a bounded polyhedron, or a bounded intersection of a finite number of half spaces. Based on this, a polyhedron may not be bounded, in which case the maximum volume rectangle will be infinity. So, we need a bounded polyhedron (polytope) to find meaningfully the maximum volume rectangle inside it, right? Another thing, we need to make sure that this bounded polyhedron is convex to apply the convex optimization algorithms such as the interior point method. We do not have to care too much about this, because the matrix A is given as well as vector b, that insure convexity of the polytope.

 

[Stephen Tashi]

You know more about the polyhedron vs polytope terminology than I do. I'd just have to look it up on the web.

A single constraint defines a an unbounded convex region of space. The intersections of the the spaces defined by all the constraints is convex (it might be the null set, so I count the null set is a convex set too) and, as you point out, the intersection may not be bounded. The wording of Prof. Boyd's problem indicates that the polyhedron is assumed to bound a non-zero volume.

 

[EngWiPy]

You know more about the polyhedron vs polytope terminology than I do. I'd just have to look it up on the web.

A single constraint defines a an unbounded convex region of space. The intersections of the the spaces defined by all the constraints is convex (it might be the null set, so I count the null set is a convex set too) and, as you point out, the intersection may not be bounded. The wording of Prof. Boyd's problem indicates that the polyhedron is assumed to bound a non-zero volume.

The question is: are all polyhedra convex? It must be, right? because the intersection of convex sets (closed halfspaces) is also convex. This is one of the properties of convexity.

Do you want to add anything else up to this point?

I think we are ready now to discuss the core of the problem, which is: how to ensure that a maximum volume rectangle is included withing a polytope? I prefer to use the term polytope from now on, because even prof. Boyd says somewhere in his famous book Convex Optimization:

... A bounded polyhedron is sometimes called a polytope, but some authors use the opposite convention ...

 

[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.