Re: intersecting a hypercube and a hyperplane

*To*: mathgroup at smc.vnet.net*Subject*: [mg88952] Re: [mg88941] intersecting a hypercube and a hyperplane*From*: Daniel Lichtblau <danl at wolfram.com>*Date*: Thu, 22 May 2008 02:36:11 -0400 (EDT)*References*: <200805211854.OAA10662@smc.vnet.net>

juan flores wrote: > 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 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

**References**:**intersecting a hypercube and a hyperplane***From:*juan flores <juanfie@gmail.com>