Support Vector Machines — Lecture series — Karush-Kahn-Tucker conditions part 4
In the previous post, we looked at what primal and dual problems were. In this post, we will be looking at a theorem which expresses the inferences that we can derive from the relationship between the dual and the primal linear programming problems. This theorem is called the ‘duality’ theorem.
Learning objective:
The main objective of this post is to gain an understanding of the duality theorem.
Main question:
Can we draw any conjectures from the relationship between primal problems and their corresponding dual problems?
The answer to this question is yes and the duality theorem aids us in doing so. The duality theorem can be expressed in two parts. The first part is that of the theory of ‘weak’ duality and the second part is that of the theory of ‘strong’ duality.
Weak duality theorem:
The weak duality theorem states that, for each feasible solution x of the primal problem and each feasible solution y of the dual problem, c.x ≤ b.y .
That is, the objective value in each feasible solution in the dual problem is an upper bound to the objective value in each feasible solution in the primal problem.
The concept of the weak duality theorem is depicted in the mathematical expression in Fig. 1 below:
Strong duality theorem:
The strong duality theorem states that, if one of the two problems (primal and dual problems) has a feasible solution, so does the other one and the bounds given by the weak duality theorem are tight.
The concept of the strong duality theorem is depicted in the mathematical expression in Fig. 2 below:
With this understanding of the weak and strong duality theorem, in the next post, we will be looking at the concept of ‘complementary slackness’.