Support Vector Machines — Lecture series — Karush-Kuhn-Tucker conditions part 1
In the previous post, we spoke about the Wolfe dual problem which simply expressed another way in which we could express the SVM optimisation problem. However in this post, we will be looking at the conditions that need to be met before we can declare that the solution obtained from solving this optimisation problem is optimal in nature. These conditions are referred to as Karush-Kuhn-Tucker (KKT) conditions. They are referred to as “Karush-Kuhn-Tucker" conditions because they were first published in 1951 by Harold W. Kuhn and Albert W. Tucker, who later found out that these conditions had already been stated in the masters thesis of William Karush in 1939.
Learning objective:
The main objective of this post is to get familiar with the Karush-Kuhn-Tucker conditions.
Main question:
What are the mathematical expressions that we can fall back on to determine whether the solution obtained from solving an SVM optimisation problem is an optimal one?
Well as stated in the introduction, if the solution obtained from solving an SVM optimisation problem is an optimal one, it would satisfy all of the KKT conditions. The KKT conditions are:
- The Stationary condition
2. The Prime feasibility condition
3. The dual feasibility condition
4. The complementary slackness condition
In the next segment of this post, we will be looking at all of these conditions individually.