Support Vector Machines — Lecture series — The SVMs optimisation problem part 3
In the previous post, we spoke about how to reframe the geometric margin optimisation problem into a form which is much easier to solve. In this post, we will be looking at how to further refine the optimisation problem statement that we formulated in the part 2 of this lecture series. Refining the optimisation problem statement is a necessary activity because it speeds up the time taken by a Quadratic Programming solver to solve for the parameters of the geometric margin.
NOTE: A quadratic programming solver is a computer program that can solve optimisation problems involving quadratic functions.
Learning objective:
Learn how to refine the geometric margin optimisation problem statement for a quadratic programming solver.
Main question:
Given the following geometric margin optimisation problem statement in Fig. 1, how do we refine it such that it is well designed for a quadratic programming solver?
Well, we can begin by squaring the norm to get rid of the square root. This makes the expression of w a quadratic expression. We need this to be a quadratic expression because we are using a quadratic programming solver to solve this problem.
Just in case you have forgotten how the norm of a vector is expressed, check out Fig. 2. Fig. 2 demonstrates the expression of the norm of the vector u. You will observe that when we square the norm of the vector u, the only that remains is a quadratic expression.
After the norm of w has been squared, the next thing that is usually done is that we multiply the quadratic expression representing w by 1/2. This is done to speed up the executing time of the solver by slashing the magnitude of the problem that the solver has to address. The final result of the geometric margin optimisation problem statement can be seen in Fig. 3:
In the next post, we will be moving on to Lagrange multipliers.