Projecting a Polytope

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
cyanyoshi
Posts: 384
Joined: Thu Sep 23, 2010 3:30 am UTC

Projecting a Polytope

Postby cyanyoshi » Fri Apr 13, 2018 10:20 pm UTC

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.

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

Re: Projecting a Polytope

Postby Qaanol » Mon Apr 16, 2018 4:24 pm UTC

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

User avatar
cyanyoshi
Posts: 384
Joined: Thu Sep 23, 2010 3:30 am UTC

Re: Projecting a Polytope

Postby cyanyoshi » Mon Apr 16, 2018 9:21 pm UTC

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: 120
Joined: Thu Feb 25, 2016 6:09 pm UTC

Re: Projecting a Polytope

Postby DavidSh » Mon Apr 16, 2018 9:51 pm UTC

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.

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

Re: Projecting a Polytope

Postby Qaanol » Mon Apr 16, 2018 10:18 pm UTC

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

User avatar
cyanyoshi
Posts: 384
Joined: Thu Sep 23, 2010 3:30 am UTC

Re: Projecting a Polytope

Postby cyanyoshi » Thu Apr 19, 2018 7:05 pm UTC

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.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 8 guests