How to Insure a Rectangle Lies Inside a Polyhedron?

[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 < 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) < 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 )< b$$

We have to convince ourselves that using Prof. Boyd's $a^+$ and [itex] 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) < b$$

with

Constraint 2: $$a_1^+ u_1 + a_2^+ u_2 - (a_1^- l_1 + a_2^- l_2 )< 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 [itex] l_1 < u_1 [/tex]

Suppose $a_1 > 0$.

If we set $\delta_1 = 1$ then the total contribution of the two terms is

$$a_1 u_1$$

If we set $\delta = 0$ then the total contribution of the two terms is

$$- a_1( -1)l_1 = a_1 l_1$$

So the best choice is [itex] \delta_1 = 1 [/tex]

Notice how Prof. Boyd's use of the $\mathbf{A^+}$ and $\mathbf{A^-}$ matrices makes the same choice in this case.

In Constraint 2: $$a_1^+ u_1 + a_2^+ u_2 - (a_1^- l_1 + a_2^- l_2 )< b$$

if $a_1 > 0$ then $a_1^+ = a_1$ and $a_1^- = 0$

So the total contribution of the terms involving $a_1$ is the same as in Constraint 1.

I think we prove Prof. Boyd'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.