I have a normal vector $n$ in a $d$ (large) dimensional space. This normal vector defines a hyperspace which crosses the origin. The points on the plane can be defined as $x$ where:

$$ x \cdot n = 0 $$

I would like to find $P$, which is the farthest point of intersection of the positive side of the unit cube and the hyperplane. Which means, I am looking for a $P$, where:

$$ \forall i \in [1 \dots d] : P_i \geq 0 $$ $$ \max_{i \in [1 \dots d]} P_i = 1 $$ $$ P \cdot n = 0 $$

It is trivial to solve this equation for $d=2$, but it gets complicated for higher dimensions. I tried to find an equation for the cube-hyperplane intersection, but I am not sure if I am on the right track.

How is it possible to solve a problem like this?

  • $\begingroup$ Please check the statement of the problem. If $d=2$ and $n=(1,1)$ the feasible set is empty. $\endgroup$ – Christian Blatter Jul 11 '18 at 18:26
  • $\begingroup$ Yes, there are some rare cases, when there is no solution $\endgroup$ – Iter Ator Jul 11 '18 at 20:04

Not sure if this will be easier to do, but here is something you could try:

You would like to maximize the (square of the) distance function $f:\mathbb{R}^d\to\mathbb{R}$, $$f(P_1,\dots,P_d) := d(\vec{P},0)^2= \sum_{i=1}^d P_i^2$$ subject to the following constraints:

$\sum_{i=1}^d P_in_i =0 \ \ \ \ $ (this ensures that the maximizing point is on the plane $x\cdot n=0$)

$0\leq P_i\leq 1$ for all $i=1,\dots,d \ \ \ \ $ (this ensures that the point is in the unit cube)

$\prod_{i=1}^d(P_i-1)=0 \ \ \ \ $ (this ensures that at least one of the $P_i$ is equal to 1)

In order to solve this maximization problem you could try to use the Kuhn-Tucker conditions. Best of luck!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.