Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

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>