Equality Set Projection
A new algorithm for the projection of
polytopes in halfspace representation
This page discusses a new method of polytopic projection dubbed Equality
Set Projection. For details of the approach, please see the report "Equality
Set Projection: A new algorithm for the projection of polytopes in
halfspace representation".
Abstract
In this paper we introduce a new algorithm called Equality Set Projection
(ESP) for computing the orthogonal projection of bounded, convex
polytopes. Our solution addresses the case where the input polytope is
represented as the intersection of a finite number of halfplanes and its
projection is given in an irredundant halfspace form. Unlike many existing
approaches, the key advantage offered by ESP is its output sensitivity,
i.e., its complexity is a function of the number of facets in the
projection of the polytope. This feature makes it particularly suited for
many problems of theoretical and practical importance in which the number
of vertices far exceeds the number of facets. Further, it is shown that
for non-degenerate polytopes of fixed size (dimension and number of facets)
the complexity is linear in the number of facets in the projection.
Numerical results are presented that demonstrate that high dimensional
polytopes can be projected efficiently.
Code
The ESP code is available in Matlab as a (very) alpha release here. To see how it works type 'help esp' at the
Matlab command prompt. The ESP code is compatible with ETH's MPT Toolbox by running the function
mpt_esp (and is part of the latest MPT release here). If you find any bugs in the
software I would love to hear about them: email.
If you would like to run the 'old favourite' fourier elimination, I have
written mex-code (Matlab compatible C code), which is available here for Windows and Linux.
Fun with polytopes
Hey - it's better than filling this page with maths right?
A few examples of high-dimensional polytopes projected using the ESP
algorithm.
The rendering was done with thanks to POVRay
Click on the thumbnail to get
a full sized (1280x1024) image.
|
The minimal invariant set of the
longitudinal modes of a 747 aircraft.
These polytopes depict the minimal set around the trim point that we can
hold the aircraft against wind disturbances using a simple linear LQG
controller.
|
|
Hypercubes
ESP is particularly efficient at computing non-axis aligned hypercubes in
high dimensions. These are unit hypercubes in R^n that are rotated in R^n
and then projected to R^3.
|
 |
 |
 |
| 8 Dimensional |
5 Dimensional |
12 Dimensional |
 |
 |
 |
| 8 Dimensional |
8 Dimensional |
50 Dimensional |
|
|
Multiparametric Quadratic
Programming
The links between projection and mpQPs will be made clear in later
publications. For now, we have all the colors of Matlab:
|
