Support Vector Machines — Lecture series — Karush-Kahn-Tucker conditions part 3
In the previous post, I explained the various what the various KKT conditions were about with the exception of the ‘complementary slackness’ condition. In the subsequent series of posts, I intend to break down this concept to enable you to have maximum understanding. To begin this quest, I will be first be talking about the concept of ‘Primal’ and ‘Dual’ linear programming problems.
Learning objective:
To have an understanding of the complementary slackness condition, I will first be explaining the concept of ‘Primal’ and ‘Dual’ problems.
Main question:
What are the ‘primal’ and ‘dual’ natures of linear programming problems?
Consider the linear programming problem expressed in Fig. 1 below:
The linear programming problem expressed in Fig. 1 can be referred to as a ‘primal’ problem because it serves as the basis from which another linear programming problem can be derived.
Let’s assume that c is a vector containing n variables, b is a vector containing m variables and A is a matrix with m rows and n columns. Using the data contained in the forms of c, b and A, we can formulate a new linear programming problem.
The new linear programming problem that can be obtained from the ‘primal’ problem is referred to as the ‘dual’ problem. The dual problem is constructed by “switching around” the parts of the primal problem. By “switching around”, I mean that the problem transforms from a max problem to a min problem, inequality signs in the constrains switch from ≤ to ≥, the number of constraints changes from m to n, the number of variables changes from n to m and the objective function co-efficients switch roles with the right-hand constraints.
The linear programming problem showcased in Fig. 2 represents the ‘dual’ problem:
In the next post, we would be looking at the Duality Theorem.