In this blog post, I will show how to calculate the hard-margin SVM by hand. If you are interested in a computational solution, refer to my last post.
Setting up the optimization problem
There are different ways to write the hard-margin optimization problem. We will be using here the following formulation:
The data for the calculations is with .
- Replace .
- Plug the data and into
- Change signs
- Setup Lagrangian
- Calculate gradient and set equation
- Simplify equation
- Set and solve the linear system of equations with Gaussian elimination.
- The separating hyperplane and the two supporting hyperplanes are
We write the hyperplanes in slope-intercept form in order to plot them.
In the following plot is the separating hyperplane and are the supporting hyperplanes (support vectors).
When solving the system of equations, I assumed , and . Then according to complementary slackness, the inequality constraints and must equal .
After Gaussian elimination, we can check whether the assumptions were correct.
All KKT conditions are satisfied. In practice, you won’t find immediately the optimal solution.