Calculating the hard-margin SVM by hand

less than 1 minute read

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 .

Graph

Calculations

  • Replace .
  • Plug the data and into
  • Simplify
  • 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

Plot

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).

Graph

Remarks

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.

Primal feasibility:

Dual feasibility:

Complementary slackness:

All KKT conditions are satisfied. In practice, you won’t find immediately the optimal solution.

Comments