I have a set of vectors $\{V_i\}$ in $n$-dimensional space. There is a number corresponded to each vector $\alpha_i = f(V_i)$ ($\alpha_i$ can be negative). I want to find a hyperplane which would maximize the difference between sums of $\alpha_i$ on the different sides of the space, divided by plane.

What is the best way to do this?

  • $\begingroup$ What if you fit a line? It would have low value where f is low, and high value where f is high. It would for a normal to the hyperplane of best separation. The search along that line would then be simpler than a search in the space. The domain is n-dimensional, but the range is 1d. $\endgroup$ – EngrStudent Jul 13 '14 at 4:01
  • $\begingroup$ Perhaps I am missing a key point. If you put your plane far away from the points, with all points on one side and no points on the other, then you could create an unbounded difference. Or do you also require that |V|/2 points are on one side and |V|/2 points are on the other? Which is certainly the more interesting problem. $\endgroup$ – Peter Leopold Feb 17 '19 at 16:14
  • $\begingroup$ Numbers can be negative so your suggestion isn't correct. $\endgroup$ – alex_io Feb 17 '19 at 18:07
  • $\begingroup$ Do you have any information about $f$? Is continuous? Linear? $\endgroup$ – DanielTheRocketMan Feb 19 '20 at 10:50
  • $\begingroup$ $f$ is continuous but not linear. $\endgroup$ – alex_io Feb 19 '20 at 12:44

This looks like a NP hard problem. If no addtional info about alpha, n and Vi are available, I would try to use simulated annealing to find a good enough solution.

  • $\begingroup$ Maybe not! A hyperplane is not able to separate any set of points. So there is a clear constraint to the problem. It is well known that if N is larger or equal to 3 a hyperplane is not able to separate all sets of points. For instance suppose that points 1, 2 and 3 are colineares. A straight line is not able to form a set of points composed by points 1 and 3 that does not have point 2. $\endgroup$ – DanielTheRocketMan Feb 15 '20 at 15:08

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.