Re: intersecting a hypercube and a hyperplane
- To: mathgroup at smc.vnet.net
- Subject: [mg88985] Re: intersecting a hypercube and a hyperplane
- From: juan flores <juanfie at gmail.com>
- Date: Fri, 23 May 2008 03:05:41 -0400 (EDT)
- References: <200805211854.OAA10662@smc.vnet.net> <g134fd$m1g$1@smc.vnet.net>
On May 22, 1:39 am, Daniel Lichtblau <d... at wolfram.com> wrote: > 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 Thanks, Daniel. I will give it a try. Juan
- References:
- intersecting a hypercube and a hyperplane
- From: juan flores <juanfie@gmail.com>
- intersecting a hypercube and a hyperplane