intersecting a hypercube and a hyperplane

[juan flores]

Hi all,

I have a problem you will laugh about (maybe). Here:

You have a hypercube and a hyperplane. They intersect. In n-D the
intersection region is a (n-1)-D object. I am interested in
determining the vertices of the intersection object. Of course, I can
check all the edges and determine all intersection vertices, but that
takes n 2^(n-1) checks. Do you know of any algorithm to compute that?

The hyperplane is Sum(Xi)=C, for some C, where Xi is the i-th
coordinate.

Idea: For each vertex of the hypercube you add its coordinates, and
form a partition into three sets (vertices behind, at, and in-front of
the hyperplane). That information would allow you to restrict the
search to edges involved in two of those sets. The problem is the
preprocessing time (to compute the sum for every vertex) itself is
exponential on n. I need something more efficient than exponential,
or else, a pointer that indicates that no such algorithm exists.

This comes from an optimization problem. The hypercube is the search
space and the hyperplane corresponds to a energy conservation
constraint. I am using an evolutionary computation technique, and are
interested in generating a population of points that lie in the
intersection.

Any pointers/ideas will be greatly appreciated.

Juan Flores
Univesity of Michoacan, Mexico

[Daniel Lichtblau]

Use linear programming, e.g. as LinearProgramming or NMinimize, to find
all extremal points in the cube subject to lying on the plane.

The hypercube can be written as 2*n inequalities, in pairs of the form
low_j<=p_j<=high_j, where p_j is a linear expression and the normals to
these expressions are all pairwise orthogonal. In the "nice" case, they
are simply coordinates, that is, inequalities are low_j<=x_j<=high<j.
Anyway, this gives 2*n linear programs to solve in order to get all
extremal points. Some may coincide, so take the union.

You might be able to bypass all this by directly calling NMinimize on
your actual objective function. Just pass the relevant constraints and
let NMinimize try to figure out your optimum. If you give explicit
Method->"DifferentialEvolution" then it will be using an evolutionary
algorithm (or, at least, an algorithm with "evolution" in its name; it's
the appearance that matters, I'm told).

Daniel Lichtblau
Wolfram Research

[juan flores]

Thanks, Daniel. I will give it a try.

Juan