## Projecting a Polytope

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

cyanyoshi
Posts: 394
Joined: Thu Sep 23, 2010 3:30 am UTC

### Projecting a Polytope

I'm having some trouble finding a good way to project a convex polytope into lower dimensions. Specifically, I am given a matrix "G" and column vector "h" which define a set of x in RN such that Gx≤h, and a linear mapping y=Cx. The goal is to find a "P" and "q" to represent Cx as the set of all y such that Py≤q. It's easy to show that P=GC-1 and q=h solve the problem if C is invertible, but this doesn't work if y has a lower number of dimensions than x. I could just project each vertex individually if I knew the set of vertices beforehand, but I'm worried that the curse of dimensionality might make it difficult to enumerate the vertices for N on the order of hundreds or even thousands.

Note: For two vectors "a" and "b" in RN, a≤b is equivalent to a(i)≤b(i) for all i=1,...,N.

Qaanol
The Cheshirest Catamount
Posts: 3065
Joined: Sat May 09, 2009 11:55 pm UTC

### Re: Projecting a Polytope

Here’s something to try:

Form a continuous family of transformations T(t) such that T(0) = C, and T is invertible when t≠0. For example, I think T(t) = t·I + (1−t)·C should work. Find the general solution in terms of T when t≠0, then take the limit as t→0.
wee free kings

cyanyoshi
Posts: 394
Joined: Thu Sep 23, 2010 3:30 am UTC

### Re: Projecting a Polytope

Thanks for the suggestion! I'm not sure how to get around the fact that x and y are in vector spaces of different dimension, though. I know that invertible transformations do exist, but I couldn't even begin to figure out how to construct T(t) which is invertible for t>0, but approaches something linear at t=0.

DavidSh
Posts: 182
Joined: Thu Feb 25, 2016 6:09 pm UTC

### Re: Projecting a Polytope

I don't expect this to be easy. After all, if y is of dimension 1 you basically have Linear Programming (finding a maximum or minimum of a linear function over a region defined by linear inequalities), which took quite some time for somebody to find a polynomial-time algorithm for.

Qaanol
The Cheshirest Catamount
Posts: 3065
Joined: Sat May 09, 2009 11:55 pm UTC

### Re: Projecting a Polytope

cyanyoshi wrote:Thanks for the suggestion! I'm not sure how to get around the fact that x and y are in vector spaces of different dimension, though. I know that invertible transformations do exist, but I couldn't even begin to figure out how to construct T(t) which is invertible for t>0, but approaches something linear at t=0.

I already gave you an example of T. Just write the matrix down using “t” as a variable, calculate its inverse, and solve your original problem. If that solution has a limit as t→0, then you are basically done.

The dimensionality difference is the entire point of using a continuous family of transforms. The lower-dimensional space embeds within the higher-dimensional space, as a subspace orthogonal to the direction of the projection. The projection squashes space flat, but nearby transformations still have full rank. So we can perturb the flattening projection very slightly and see what happens when it is “nearly flat”.

The specific example of T that I posted, namely T(t) = t·I + (1−t)·C, is the natural “flattening” action that you would see in an animation of how C affects space. As you squash space flatter and flatter, everything moves directly toward the flat destination subspace. As long as you haven’t gotten all the way to complete flatness, all the dimensions are still present and you can solve the problem as you described.

And since you are doing the squashing in a continuous manner, you can take the limit as you approach full flatness. Does that make sense?

• • •

This may not work, if it makes everything blow up to infinity. I haven’t actually tried it, it just seemed like perturbation might be tractable.
wee free kings

cyanyoshi
Posts: 394
Joined: Thu Sep 23, 2010 3:30 am UTC

### Re: Projecting a Polytope

I may have found more or less what I've been looking for in "Equality Set Projection: A new algorithm for the projection
of polytopes in halfspace representation" by Jones, Kerrigan, and Maciejowski (2004): http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.137.3998&rep=rep1&type=pdf. It might take a while to digest what's going on here, but it seems to have polynomial worst-case complexity in both the number of outputs and the number of dimensions.