Support Vector Machines — Lecture series — Karush-Kahn-Tucker conditions part2

In the previous post, we looked at the various conditions that make up the Karush-Kahn-Tucker (KKT) conditions. In this post, we would explore each of those conditions and explain what they mean.

Learning objective:

Understand the main ideas behind the various KKT conditions.

Main questions:

What do the following KKT conditions mean:

1. The stationary condition
2. The prime feasibility condition
3. The dual feasibility condition
4. The Complementary slackness condition

The stationary condition:

The stationary condition just states that the selected point must be a stationary point. A stationary point refers to the point at which the function stops increasing or decreasing. When there is no constraint, the stationary point is the point where the gradient of the objective function is zero. However, when there are constraints, we use the gradient of the Lagrangian.

The primal feasibility condition:

The primal feasibility condition(s) refers to the constraint(s) of the primal problem. These conditions have to be satisfied in order to find the minimum of the function.

The dual feasibility condition:

The dual feasibility condition(s) refers to the constraint(s) of the dual problem. These conditions also have to be satisfied in order to find the minimum of the function.

For the complementary slackness condition, we will look at it in detail in the next lecture post. This is because, we will have to delve deeper into the concept of slackness in addition to explaining the concept of ‘complementary slackness’ and how it contributes to aid us in finding the optimal solution for an optimisation problem.