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