Let's start by introducing the so-called primal-dual pairs. Let's considered this linear program. In this linear program, we have three decision variables, all are non-negative. We have two constraints all are less than or equal two. We want to maximize something. Everything looks so typical. Let's assume this linear program is actually very hard to solve. I know it's not very hard, you just run the simplest maze or whatever you are able to solve it, but let's assume now we don't want to solve it or we have no way to solve it. Suppose your friend propose this solution. This solution is called x-hat, where the values are 1/2, 1 and 1. If you plug-in, you may see that the corresponding objective value would be z-hat, which is 15. Somehow, we want to justify or we want to confirm whether this suggestion x-hat is reasonable. We of course may check it's feasibility. We may take a look at this objective value, but we have no idea about whether this z-hat is good or not. Somehow, if we want to know whether it is good or not, ideally we should know z-star, which is the optimal objective value for this particular thing. In that case, we want to know z-star, but of course, we have no way to know z-star because we don't know how to solve it. That's the whole point. We want to do somehow different thing. Let's try to see whether we may find an upper bound of z-star. Suppose we are able to know an upper bound of z-star. Let's say it is something called z-double star. If that's the case, z-star cannot be greater than z-double star. We know z-hat as a feasible solution, it is not going to be greater than z-star. We are able to compare z-hat with z-double star to see what's the difference. If z-hat is close to the upper bound, we will say that x-bar is quite good. That's the idea of looking for an upper bound. If we look at this particular program and if we want to find an upper bound for z-star, now the question is, how may we do that? Very quickly, let me show you how. How about this. I'm going to multiply the first constraint by 2, and then multiply the second constraint by 1, and then add them together. If I do that, I'm going to get another inequality, which goes to 4x_1 plus 5x_2 plus 8x_3. I certainly do this with some purpose. Let's take a look at the objective function. I want to maximize 4x_1 plus 5x_2 plus 8x_3, and at the same time, I know 4x_1 plus 5x_2 plus 8x_3 cannot be greater than 16. As long as I have a feasible solution, I need to satisfy these constraints. so I know z-star would be no greater than 16. We don't know whether z-star is really 16. If z-star is really 16, we would say the upper bound is tight, where tight means it exactly indicates the objective value. We don't know whether it is true, but at least we know, well, z-hat 15, somehow is close to z-star, which is 16. Probably we will say,"X-hat is good, or at least we have some quantification about the gap," and that would be nice. That was lucky in some sense, because we happen to get the objective function directly. Suppose we have a slightly different problem. Now, we want to maximize 3x_1 plus 4x_2 plus 8x_3. If that's the case, then we may still multiply the first constraint by 2, multiply the second constraint by 1, and then try to add them together. We're going to get 4x_1 plus 5x_2 plus 8x_3. This is still going to be less than or equal to 16. Because we know all these variables are non-negative, so your original objective function, cannot be greater than your 4x_1 plus 5x_2 plus 8x_3. In that case, 16 is still an upper bound. But it would be much more likely that 16 is not a tight upper bound, and maybe, we may find a better one. Maybe we should not try 2 and 1 as the coefficients for our multiplication. Maybe we should try for example 1 and 1. But unfortunately 1 and 1 is not good enough. Maybe we may look for some other set of coefficients to do the combination of these two constraints, so that the result is closer to our objective function. Well, we may try it. We may try to change coefficients multiplied on the two constraints to try to create a better upper bound. Pretty much, we are trying to do different linear combinations. We want to look for y_1 and y_2 as the coefficients, so that, once we use y_1 and y_2 to combine these two constraints, somehow we you will be able to find an upper bound for this one. Well, if we want to do that, the first thing is that, we need our y_1 and y_2 to be non-negative, so that after the multiplication, after the summation, we still get less then or equal 2, which gives us an upper bound. Then we need something else. Previously we know this is 3, this is 4, this is 8. Somehow we need to compare them with these coefficients. We need to do that. We need to make sure that 3 is less than or equal to the first coefficient 4x_1, at the left-hand side of that inequality. Four need to be upper bounded by 2y_1 plus y_2. Eight must be upper bounded by this. If all these things happens, if all these things are applied, then we know the z-star cannot be greater than 6y_1 plus 4y_2. Immediately we realize one thing, this is to solve another linear program. If we try our best to look for an upper bound, we minimize 6y_1 plus 4y_2 subject to all these constraints. We need to make sure that our y_1 and y_2 are non-negative, so that after we do the combination, we still preserve the direction for inequality. We need to make sure that our y_1 and y_2 satisfies all these conditions so that 3 is less than or equal to the outcome, 4 is less than or equal to the outcome, and and so on. As long as we are able to satisfy these five constraints, we look for the best, the smallest is 6y_1 plus 4y_2. That would be the best upper bound. The best estimation we may obtain. This is the motivation of doing all the things. Given original program, which we call it a primal program, we construct another program which is called the dual program. The way to find a good upper bound is to solve another linear program. Actually, this idea applies to any linear program. Let's see more examples.
