1

Say I have access to a set of points $C = \{x_1, x_2, ..., x_{N}\}$ where $x_i \in \mathbb{R}^{d}$.
I would like to find supporting hyperplanes of $C$ numerically. Particularly, my characterization to find $w \in \mathbb{R}^d, b \in \mathbb{R}$ is the following:
$\begin{align} & \exists i: w^Tx_i + b = 0 \\ & \forall i: w^Tx_i + b \ge 0 \\ & ||w||_{2} =1 \end{align}$

I have $||w||_2 = 1 $ to escape the trivial solution (where $w = 0, b=0$).

However, I cannot formulate a tractable optimization problem / algorithm to solve this problem. Does anybody have any pointers that might be helpful? Thanks in advance!

yugosmer
  • 11
  • 1
  • I think you are missing some property. Otherwise, you could choose any unit vector $w$ and an appropriate $b = -\max_i w^\top x_i$. – gerw Jul 07 '22 at 13:45
  • Thanks @gerw! Actually this is pretty cool, and it certainly satisfies the supporting hyperplane condition. Geometrically it makes sense too, I guess? Fixing a direction, I can push any hyperplane until it's tangent to the convex hull/region. Then, it may make sense to find the facets of the convex hull to get rid of the redundancy. Thanks a lot again, this was helpful! – yugosmer Jul 10 '22 at 23:09

0 Answers0