# Linear Program for Hyperplane Sparation

GOAL: I want create a simple linear programming model that can be used to classify new data based off of a found hyperplane. In this particular case I have two classes and I'm given a data set in which the data is already classified.

ATTEMPT:

So I have that $$x'$$, $$x''$$ are given data and my objective is to find a "line" separating the data.

When I say I desire a "line" separating the data, what I actually mean is a vector $$a=[a_0, a_1, ..., a_n]$$ such that $$\sum_{i=1}^{n} a_i x_i = a_0$$ with the property that one class is on one side of the line and the other class is on the other side.

So far I have come up with the following thought process..

$$x'$$ is on one side if $$\sum_{i=1}^{n} a_{i}x'_{i} > a_{0}$$

$$x''$$ is on the other side if $$\sum_{i=1}^{n} a_{i}x''_{i} < a_{0}$$

We can scale up or down such an algebraic expression; the hyperplane stays the same.

So, $$\sum a_{i}x'_{i} \geq a_{0} + 1$$ and $$\sum a_{i}x''_{i} \leq a_{0} - 1$$

For each point $$x'$$ of class A, introduce $$y'_{i} \geq 0$$, where $$y'_{i} \geq a_{0} + 1 - \sum a_{i}x'_{i}$$

Similarly for each point $$x''$$ of B, introduce $$y''_{i} \geq 0$$, where

$$y''_{i} \geq \sum a_{i}x''_{i} - a_{0}+1$$

Then recall $$x'$$, $$x''$$ are data given and we are looking for $$a$$, $$y'$$, $$y''$$

Now I try to minimize each of $$y'$$, and $$y''$$

I obtain the linear program

$$\begin{array}{ll@{}ll} \text{minimize} & \displaystyle \sum_{i \in A} & y'_{i} + \displaystyle \sum_{i \in B} y''_{i} \\ \text{subject to} & y'_{i} &\geq a_{0} + 1 - \sum_{j=1}^{n} a_{j}x'_{j} &\forall i \in A\\ & y''_{i} &\geq \sum_{j=1}^{n} a_{j} x''_{j} - a_{0} + 1 &\forall i \in B\\ & a_{i} &\in \mathbb{R} &\forall i\in A \cup B\\ & y'_{i} &\geq 0 &\forall i \in A\\ & y''_{i} &\geq 0 &\forall i \in B\\ \end{array}$$

Once I have the vector $$a$$, to classify a new point $$z$$ I just compute $$\sum a_{i}z_{i} - a_{0}\text{,}$$ which is is either positive or negative, indicating $$z$$ belongs to cluster A or cluster B.

QUESTIONS:

1. I'm struggling to determine the correctness of this model. Can this be confirmed?
2. It's clear that to avoid misclassification, a better hyperplane would maximize the distance from the planes to each class (like a support vector machine). How can my current model be extended to do this?

1. The proposed model works as expected.

2. To avoid chance of misclassification by finding a better hyperpland that maximizes the distance from the planes to each class (like a SVM) can be done in the following way if we assume the data is linearly separable:

$$minimize: \sum_{j=1}^{p}( \vec{w}_{j}^{+} + \vec{w}_{j}^{-})$$

Constraints:

• $$(\vec{w}^T\vec{x}_{j})y_j \geq 1 - \epsilon _{j}, \forall j$$
• $$w_{i}^{+}, w_{i}^{-}, \epsilon_{i} \geq 0$$

Where $$|\vec{w}|$$ is the distance from the hyperplane to a class, and $$w = w^+ - w^-$$

Note this is equivalent to the quadratic support vector machine approach but instead of using the L2 norm for distance we use the L1 norm