Support Vector Machines — Lecture series — Karush-Kahn-Tucker conditions part 5

In the previous post, we spoke about the duality theorem and we gained an understanding of how the duality theorem showcases the relationship between primal problems and their corresponding dual problems. In this post, we would be looking at the concept of ‘complementary slackness’.

Learning objective:

Understand the concept of ‘complementary slackness’.

Main question:

Is there a relationship between the variables in the primal problem and the constraints in the dual problem? or vice versa? And how is this relationship expressed?

Firstly, to gain a refreshed understanding on how primal problems and dual problems are related you can read this article here.

Now to the main question, there is indeed a relationship between the variables in the primal problem and the constraints in the dual problem. However, there is also a relationship between the variables in the dual problem and the constraints of the primal problem.

These relationships are complementary in nature where the number of variables in the primal problem is equal to the number of constraints in the dual problem and the number of variables in the dual problem is equal to the number of constraints in the primal problem.

This complementary relationship is demonstrated in the example below:

Primal problem:

Maximize z = 3x1 + 5x2

Subject to:

x1 ≤ 4

2x2 ≤ 12

3x1 + 2x2 ≤ 18

x1, x2 ≥ 0

Dual problem:

Minimize w = 4y1 + 12y2 + 18y3

Subject to:

y1 + 3y3 ≥ 3

2y2 + 2y3 ≥ 5

y1, y2, y3 ≥ 0

“Complementary slackness” therefore refers to a relationship between the “slackness” in a primal constraint and the “slackness” of its associated dual variable or vice versa.

NOTE: To gain a better understanding of the concept of “slack”, please read more about it here.

The main idea of complementary slackness is that, if the slack of a primal constraint is zero (indicating that, that primal constraint is binding), the slack of its associated dual variable would be greater than zero. However, if the slack of a primal constraint is greater than zero (indicating that, the primal constraint is non-binding), the slack of its associated dual variable would be equal to zero.

This idea also applies in the opposite direction. That is, if the slack of a dual constraint is zero (indicating that, that dual constraint is binding), the slack of its associated primal variable would be greater than zero. However, if the slack of a dual constraint is greater than zero (indicating that, the dual constraint is non-binding), the slack of its associated primal variable would be equal to zero.

However note that, it is also possible for a primal constraint to be binding while the associated dual variable is equal to zero.

In the next post, we will be looking at why the complementary slackness condition is true.